董畅畅,刘娟.超欧拉扩展有向图[J].数学研究及应用,2018,38(2):111~120 |
超欧拉扩展有向图 |
Supereulerian Extended Digraphs |
投稿时间:2017-03-30 修订日期:2018-01-15 |
DOI:10.3770/j.issn:2095-2651.2018.02.001 |
中文关键词: 超欧拉有向图 生成闭迹 欧拉有向图 哈密尔顿有向图 弧-局部半完全有向图 亚-半完全有向图 扩展有向图 |
英文关键词:supereulerian digraph spanning closed trail eulerian digraph hamiltonian digraph arc-locally semicomplete digraph hypo-semicomplete digraph extended digraph |
基金项目:国家自然科学基金(Grant Nos.11761071; 61363020),新疆师范大学硕士研究生科技创新项目(Grant No.XSY201602013),新疆师范大学“十三五”校级重点学科数学招标课题资助(Grant No.17SDKD1107). |
|
摘要点击次数: 1894 |
全文下载次数: 1847 |
中文摘要: |
如果一个有向图$D$包含一个生成欧拉子有向图,则称$D$是超欧拉有向图. Bang-Jensen和Thomass\'{e}猜想:如果一个有向图$D$的弧-强连通度$\lambda(D)$不小于其独立数$\alpha(D)$,那么$D$是超欧拉有向图.本文证明:如果$D$是一个扩展圈,一个扩展哈密尔顿有向图,一个弧-局部半完全有向图,一个扩展弧-局部半完全有向图,两类欧拉有向图的扩展有向图,一个亚-半完全有向图,或是一个扩展亚-半完全有向图,若满足$\lambda(D)\geq \alpha(D)$,则$D$是超欧拉有向图. |
英文摘要: |
A digraph $D$ is supereulerian if $D$ has a spanning eulerian subdigraph. Bang-Jensen and Thomass\'{e} conjectured that if the arc-strong connectivity $\lambda(D)$ of a digraph $D$ is not less than the independence number $\alpha(D)$, then $D$ is supereulerian. In this paper, we prove that if $D$ is an extended cycle, an extended hamiltonian digraph, an arc-locally semicomplete digraph, an extended arc-locally semicomplete digraph, an extension of two kinds of eulerian digraph, a hypo-semicomplete digraph or an extended hypo-semicomplete digraph satisfying $\lambda(D)\geq \alpha(D)$, then $D$ is supereulerian. |
查看全文 查看/发表评论 下载PDF阅读器 |
|
|
|