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

AbstractThe 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) 219–221] graphs with cut‐vertices on 14 vertices having the same path layer matrix [A. A. Dobrynin, Vyčisl. sistemy, Novosibirsk 119(1987) 13–33] and graphs without cut‐vertices on 31 vertices having the same path layer matrix [A. A. Dobrynin, J Graph Theory 38(2001) 177–182]. 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: 304–311, 2003