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

Calculating the crossing number of a given graph is, in general, an elusive problem. As Garey and Johnson have proved, the problem of determining the crossing number of an arbitrary graph is NP-complete (Crossing number is NP-complete, SIAM J. Alg. Disc. Meth. 4 (1983) 312-316). The crossing numbers of very few families of graphs are known exactly. Richter and Salazar (The crossing number of P(N, 3), Graphs and Combinatorics 18 (2) (2002) 381-394) have studied the crossing number of the generalized Petersen graph P(n, 3) and proved that cr(P (3h, 3))=h (h≥4); cr(P (3h+1, 3))=h+3 (h≥3); cr(P (3h+2, 3))=h+2 (h≥3). In this paper, we study the crossing number of the circulant graph C(n; {1, 3}) and prove that cr(C(n; {1, 3}))=「n/3」+n mod 3 (n≥8).

Given a set of graphs Ψ={G1, G2, …, Gk}, let ex(n; Ψ) denote the greatest size of a graph with order n that contains no subgraph isomorphic to some Gi, 1≤i≤k. One of the main classes of problems in extremal graph theory, known as Tuŕan-type problems, is for given n, Ψ to determine explicitly the function ex (n, Ψ), or to find its asymptotic behavior. Yang Yuansheng investigated the values of ex(n, Ψ) for Ψ={C4} (UTILITAS MATHEMATICA, 41 (1992), 204-210), Garnick investigated them for Ψ={C3, C4} (Journal of Graph Theory, vol.17, no.5 (1993), 633-645) and Alabdullatif investigated them for Ψ={Cn-k+1, …, Cn and Ψ={Pn-k+1,…, Pn}, (1≤k≤n-2) (Bull. Inst. Combin. Appl., 25 (1999)41-52). This paper investigates the values of ex (n, Ψ) forΨ={C3, C4, C5}, n≤42.

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.

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