Given t(≥2) cycles Cn of length n≥3, each with a fixed vertex vi0, i=1, 2,…, t, let C(t)n denote the graph obtained from the union of the t cycles by identifying the t fixed vertices(v10=v20=…=vt0). Koh et al. conjectured that C(t)n is graceful if and only if nt≡0,3 (mod 4). The conjecture has been shown true for n=3, 6, 4k. In this paper, the conjecture is shown to be true for n=5.

In this article, we show that the disjoint union C2k UC2j+1 of cycles C2k and C2j+1 (k

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.

The path layer matrix of graph G contains quantitative information about all paths in G. The entry (i,j) in this matrix is the number of simple paths in G having initial vertexi and length j. Some new upper bounds for r-regular graphs with the same path layer matrix are presented for r=4, 5, 6.

利用计算机对图的交叉数进行研究，给出利用分支界限法计算图的交叉数的算法CCN（calculate crossing Number），并利用该算法计算出n≤12的所有四正则图的交叉数，以及n≤16的随机四正则的交叉数。同时计算出n≤12的所有四正则图的平均交叉数Aac（n），和n≤16的随机四正则图的平均交叉数Arc（n），根据计算结果提出四正则图的平均交叉数为O（n2）的猜想。