With The Same Path Layer Matrix Cut Vertex Regular Graph

As an important branch of applied mathematics, graph theory has a history of more than two hundred years. Especially, with the occurrence and development of computer, graph theory has developed rapidly.The subject of graphs with 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 / and with the length of j. The path layer matrix is closely related to graph isomorphism. Graphs with small order are isomorphism, if and only if they have the same path layer matrix. It was verified in the case of p(G) < 11. It is known that there exist graphs on 14 vertices having the same path layer matrix.It is also known that there are 4-regular graphs on at most 44 vertices, 5-regular graphs on at most 48 vertices, and 6-regular graphs on at most 51 vertices having the same path layer matrix (Yang Yuansheng, J Graph Theory 39(2002), 219-221).The graphs having the same path layer matrix which were constructed earlier, all have cut-vertices. In 1999, Dobrynin constructed a pair of 3-regular graphs without cut-vertices on 36 vertices and a pair of 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, the base-graph that Dobrynin has used in his construction, is further studied. The characteristic of the base-graph is clarified. Then the construction method of base-graphs is improved. At the same time, the accuracy of the method constructing the graphs with the same path layer matrix by the means of crossing connection through the base-graph is proved theoretically.A series of better algorithms including MakeGraphs, Path Vector, and HasCutPoint etc, are successfully designed to resolve the key problems in the construction of new base-graphs.With above algorithms, a pair of 4-regular graphs without cut-vertices on 18 vertices having the same path layer matrix are successfully constructed. As a result, it improves 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. The article has been contributed to J. Graph Theory.