4-regular graphs without cut-vertices having the same path layer matrix

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. Yuansheng, L. Jianhua, and W. Chunli, J Graph Theory 39(2002) 219221] graphs with cut-vertices on 14 vertices having the same path layer matrix [A. A. Dobrynin, VyCisl. sistemy, Novosibirsk 119(1987) 1333] and graphs without cut-vertices on 31 vertices having the same path layer matrix [A. A. Dobrynin, J Graph Theory 38(2001) 177182]. 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. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 304311, 2003