Different Configurations Of The Same Path Layer Matrix Of R-regular Graphs

Graph theory is one of the most important branches of applied mathematics. Its wide application accelerates its development. Especially in the recent years, with the occurrence and development of computer technology, graph theory has made great progress and obtained wonderful achievement.The subject of graphs having the same path layer matrix, which we are researching, arises from the drug design. The path layer matrix of a graph G contains quantitative information about all possible paths in G. The entry (i,_j) of this matrix represents the number of paths in G starting from vertex i and with the length of j. The path layer matrix is closely related to graph isomorphism.Let f(r) denote the least order p(r) of nonisomorphic r-regular graphs having the same path layer matrix. The work of calculating f(r) when r is arbitrary is a significative but difficult thing. In 1990, Dobrynin constructed a series of nonisomorphic r-regular graphs having the same path layer matrix and proved for each r 3 there exist nonisomorphic r-regular graphs having the same path layer matrix (A. A. Dobrynin.Regular graphs having the same path layer matrix. J Graph Theory, 1990,14:141-148). In his article, Dobrynin put forward the following result: f(r) 18r + 36 (r = 2m, m 3), f(r) 20r + 48 (r = 4m + 3, m 1), f(r) 20r + 64 (r = 4m + 5, m 0). In 2002, the result is improved to f(5) 48, f(6) 51 by Yang Yuansheng and other people(Yang Yuansheng, Lin Jianhua, Wang Chunli.Small regular graphs having the same path layer matrix. J Graph Theory, 2002, 39:219-221).But before this paper, nobody has given uniform method to construct nonisomorphic graphs having the same path layer matrix better than Dobrynin's. The upper bound of f(r) where r is arbitrary has not been improved either. A deep research of path layer matrix has been worked on in this paper. A new construction method is put forward which uses the property of 3-similar graph and complete 2-partite graph and as a result a series of nonisomorphic r-regular graph having the same path layer matrix has been successfully constructed. Also the entire mathematics proof has been given in this paper. Thus the upper bound of f(r) is improved to f(r) 2r + 20(r = 3,5), f(r) 5r +11(r = 6,8,10),f(r) < 2r + 8 (r = 7,9 or r 11). This result is much better than before. The article has been contributed to Graphs and Combinatorics.