已为您找到该学者10条结果 成果回收站
【期刊论文】Largest planar graphs and largest maximal planar graphs of diameter two☆
杨元生, Yuansheng Yang a, *, Jianhua Lin b, Yongjie Dai a
Journal of Computational and Applied Mathematics 144(2002)349-358,-0001,():
-1年11月30日
Let fk (∆) be the maximum number of vertices in a planar graph with diameter k and maximum degree ∆. Let gk (∆) be the maximum number of vertices in a maximal planar graph with diameter k and maximum degree ∆. Seyffarth has shown that g2(∆)=「3∆/2+1」 for ∆≥8. Hell and Seyffarth have shown that g2(∆)=「3∆/2+1」 for ∆≥8. We compute the exact maximum number of vertices in a planar graph and a maximal planar graph with diameter two and maximum degree ∆, for ∆<8.
Maximum degree, Planar graph, Maximal planar graph
-
27浏览
-
0点赞
-
0收藏
-
0分享
-
170下载
-
0
-
引用
【期刊论文】On Kotzig's conjecture concerning graphs with a unique regular path-connectivity☆
杨元生, Yuansheng Yang a, *, Jianhua Lin b, Chunli Wang a, Kaifeng Li a
Discrete Mathematics 211(2000)287-298,-0001,():
-1年11月30日
Kotzig (see Bondy and Murty, Graph Theory with Applications, North-Holland, Amsterdam, 1976) conjectured that there exists no graph with the property that every pair of vertices is connected by a unique path of length k, k>2. Kotzig (Graph Theory and Related Topics, Academic Press, New York, 1979, pp. 358-367) has proved this conjecture for 2<k<9. Xing and Hu (Discrete Math. 135 (1994) 387-393) have proved it for k>11. Here we prove this conjecture for the remaining cases k=9, 10, 11.
Regular path-connectivity, Eulerian graph
-
28浏览
-
0点赞
-
0收藏
-
0分享
-
258下载
-
0
-
引用
【期刊论文】Three forbiddensubgraphs for line graphs
杨元生, Yuansheng Yang a, *, , Jianhua Lin b, Chunli Wang a
Discrete Mathematics 252(2002)287-292,-0001,():
-1年11月30日
We construct a set of three graphs with the property that a 3-connected graph with minimum degree at least 7 is a line graph if and only if it does not contain any of the three graphs as an induced subgraph. We also show that the number of excluded subgraphs cannot be reduced no matter what connectivity is specified.
Line graph, Forbidden subgraph
-
27浏览
-
0点赞
-
0收藏
-
0分享
-
197下载
-
0
-
引用
【期刊论文】The crossing number of C(n; {1, 3})☆
杨元生, YangYuansheng, Lin Xiaohui, Lu Jianguo, Hao Xin
Discrete Mathematics 289(2004)107-118,-0001,():
-1年11月30日
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).
Circulant graph, Crossing number, Generalized Petersen graph
-
38浏览
-
0点赞
-
0收藏
-
0分享
-
172下载
-
0
-
引用
【期刊论文】Extremal Graphs Without Three-Cycles, Four-Cycles or Five-Cycles*
杨元生, Yang Yuansheng, Lin Xiaohui, Dong Guocheng, Zhao Yongxiang
,-0001,():
-1年11月30日
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.
extremal graph,, forbidden subgraph,, cage,, girth
-
34浏览
-
0点赞
-
0收藏
-
0分享
-
264下载
-
0
-
引用