Premium
4‐regular graphs without cut‐vertices having the same path layer matrix
Author(s) -
Yuansheng Yang,
Xiaohui Lin,
Zhiqiang Chen,
Weiming Lu
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10147
Subject(s) - combinatorics , mathematics , wheel graph , path graph , vertex (graph theory) , path (computing) , discrete mathematics , graph , graph power , line graph , computer science , programming language
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) 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