×

4-regular graphs without cut-vertices having the same path layer matrix. (English) Zbl 1031.05082

Summary: The path layer matrix of a graph \(G\) contains quantitative information about all possible paths in \(G\). The entry (\(i,j\)) of this matrix is the number of paths in \(G\) having initial vertex \(i\) and length \(j\). It is known that there are 4-regular graphs on 44 vertices having the same path layer matrix [Y. Yang, J. Lin, and C. Wang, J. Graph Theory 39, 219-221 (2002; Zbl 1001.05080)], graphs with cut-vertices on 14 vertices having the same path layer matrix [A. A. Dobrynin, Vychisl. Sist. 119, 13-33 (1987; Zbl 0672.05054)], and graphs without cut-vertices on 31 vertices having the same path layer matrix [A. A. Dobrynin, J. Graph Theory 38, 177-182 (2001; Zbl 0991.05069)]. In this article, a pair of 4-regular graphs without cut-vertices on 18 vertices having the same path layer matrix are constructed, improving the upper bound for the least order of 4-regular graphs having the same path layer matrix from 44 to 18 and the upper bound for the least order of graphs without cut-vertices having the same path layer matrix from 31 to 18.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bloom, Graph Theory, Lag?w (1981)
[2] Proceedings of the Graph Theory Conference dedicated to the memory of Professor Kazimierz Kuratowski, Lag?w, Poland, February, 1981,
[3] Lecture Note in Mathematics, Vol. 1018. Springer-Verlar, Berlin, 1983, pp. 179-190.
[4] Dobrynin, Vy?isl. sistemy, Novosibirsk 119 pp 13– (1987)
[5] Dobrynin, J Graph Theory 14 pp 141– (1990)
[6] Dobrynin, Graph Theory Notes NY 23 pp 7– (1992)
[7] Dobrynin, J Graph Theory 17 pp 1– (1993)
[8] Dobrynin, J Graph Theory 38 pp 177– (2001)
[9] and Recent results in the theory of the path layer matrix, Graph Theory Notes of New York XLIII, 48-56 (2002), New York Academy of Sciences.
[10] and A note on tables of distance and path degree sequences for cubic graphs, Presented at Silver Jubilee Conference on Combinatorics (University of Waterloo, Waterloo, Ontario, Canada, June 14-July 2, 1982).
[11] and Distance and path degree sequences for cubic graphs, Mathematical Department, Pace University, New York, 1982.
[12] Halberstam, Graph Theory, Lag?w (1981)
[13] Proceedings of the Graph Theory Conference dedicated to the memory of Professor Kazimierz Kuratowski, ?ag?w, Poland, February, 1981,
[14] Lecture Note in Mathematics, Vol. 1018. Springer-Verlar, Berlin, 1983, pp. 286-289.
[15] Graph Theory, Addison-Wesley, Reading, MA, 1969.
[16] Quintas, Comm Math Chem (MATCH) 12 pp 75– (1981)
[17] Randi?, Comm Math Chem (MATCH) 7 pp 5– (1979)
[18] Randi?, J Chem Inf Compute Sci 19 pp 23– (1979)
[19] and Ordering of graphs as an approach to structure-activity studies, Chemical Applications of Topology and Graph Theory (A collection of papers from a symposium held at the University of Georgia, Athens, 1983), Elsevier, New York, 1983, pp. 192-205.
[20] Design of molecules with desired properties, Concepts and Application of Molecular Similarity, John Wiley & Sons, New York, 1990, pp. 77-145.
[21] Skorobogatov, Comm Math Chem (MATCH) 23 pp 105– (1988)
[22] Slater, J Graph Theory 6 pp 89– (1981)
[23] Yuansheng, J Graph Theory 39 pp 219– (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.