杨元生
图论难题的计算及算法研究
个性化签名
- 姓名:杨元生
- 目前身份:
- 担任导师情况:
- 学位:
-
学术头衔:
博士生导师
- 职称:-
-
学科领域:
计算机软件
- 研究兴趣:图论难题的计算及算法研究
主要研究方向:图论难题的计算及算法研究,其特点是将有效的计算机算法与数学证明结合起来,在理论上提出了图的同构的必要条件和图的着色限制条件,给出了较好的多项式时间算法,并应用于各种图论应用难题的研究中,将前人关于图论难题拉姆赛数、极图、找笼问题等的研究成果大大向前推进了一步,研究成果得到国际承认。已完成国家自然基金1项,在研2项。已发表论文近40篇,其中多数在国际著名杂志上发表,已有3篇被ACM收录,15篇被SCI索引,9篇被EI索引。在研项目:1.“图的交叉数、应用及算法研究”,国家自然科学基金项目(批准号60143002),项目经费15万,2002.1―2004.12, 项目负责人。2.“具有相同路径层矩阵的图、应用及算法研究 ”,国家自然科学基金(批准号60373096),项目经费22万,2004.1―2006.12, 项目负责人。3.“具有相同路径层矩阵的图、应用及算法研究 ”,高等学校博士学科点专项科研基金基金(20030141003),项目经费6万,2004.1―2006.12, 项目负责人。已完成的项目:1.“部队水路运输决策支持系统”,总后勤部下达的课题,项目经费20万,2001.1―2001.12, 主要参加者,负责研制船上武器配载算法。 此项目已由国家教委鉴定,其中,船上武器配载算法被鉴定为达到国际先进水平;2002年获辽宁省科学技术进步3等奖。2.“全二维气相色谱数据处理软件开发”,中国科学院大连化学物理研究所,项目经费3.6万,2002.5―2002.12, 项目负责人。3.图论难题的计算机算法研究,国家自然科学基金项目(批准号:69473031),1995.1―1997.12, 负责人。
-
主页访问
3216
-
关注数
0
-
成果阅读
316
-
成果数
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评论
-
引用
【期刊论文】The Graphs C(t) 5 are Graceful for t≡0, 3 (mod 4)*
杨元生, Yang Yuansheng, Lin Xiaohui, Yu Chunyan
,-0001,():
-1年11月30日
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.
graceful graph,, vertex labelling,, edge labelling
-
23浏览
-
0点赞
-
0收藏
-
0分享
-
129下载
-
0评论
-
引用
【期刊论文】Harmonious Graphs C2k SC2j+1*
杨元生, Yang Yuanshengm, , Lin Xiaohui, Lu Weiming, Zeng Qingshuang
,-0001,():
-1年11月30日
In this article, we show that the disjoint union C2k UC2j+1 of cycles C2k and C2j+1 (k
Harmonious Graphs,, harmonious labelling,, edge label,, vertex label
-
26浏览
-
0点赞
-
0收藏
-
0分享
-
98下载
-
0评论
-
引用
【期刊论文】4-Regular Graphs Without Cut-Vertices Having the Same Path Layer Matrix
杨元生, Yang Yuansheng, * Lin Xiaohui, Chen Zhiqiang, and Lu Weiming
,-0001,():
-1年11月30日
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.
undirected graph, path, path layer matrix, graph isomorphism
-
33浏览
-
0点赞
-
0收藏
-
0分享
-
98下载
-
0评论
-
引用
【期刊论文】Small Regular Graphs Having the Same Path Layer Matrix
杨元生, Yang Yuansheng, * Lin Jianhua, and Wang Chunli
,-0001,():
-1年11月30日
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.
path layer matrix, degree sequence, regular graph
-
25浏览
-
0点赞
-
0收藏
-
0分享
-
109下载
-
0评论
-
引用
杨元生, , 王丹, 陆维明
软件学报,2002,13(12):1~8,-0001,():
-1年11月30日
利用计算机对图的交叉数进行研究,给出利用分支界限法计算图的交叉数的算法CCN(calculate crossing Number),并利用该算法计算出n≤12的所有四正则图的交叉数,以及n≤16的随机四正则的交叉数。同时计算出n≤12的所有四正则图的平均交叉数Aac(n),和n≤16的随机四正则图的平均交叉数Arc(n),根据计算结果提出四正则图的平均交叉数为O(n2)的猜想。
交叉数, 正则图, 同构, 平面图, 分支界限法
-
55浏览
-
0点赞
-
0收藏
-
0分享
-
104下载
-
0评论
-
引用