超双爪无关图的可折叠性

J4 ›› 2010, Vol. 45 ›› Issue (4): 36-38.

超双爪无关图的可折叠性

苏贵福¹, 徐兰², 马蓓蓓¹

1. 新疆大学数学与系统科学学院, 新疆乌鲁木齐 830046；
2. 昌吉学院数学系, 新疆昌吉 831100

收稿日期:2009-10-15 出版日期:2010-04-10 发布日期:2010-05-19

Collapsible super-biclaw-free graphs

SU Gui-fu¹, XU Lan², MA Bei-bei¹

1.College of Mathematics and System Science, Xinjiang University, Urumqi 830046, Xinjiang, China；
2. Mathematics Department of Changji College, Changji 831100, Xinjiang, China

Received:2009-10-15 Online:2010-04-10 Published:2010-05-19
About author:SU Gui-fu(1981-), male, master candidate, engaged in method for solving coloring of graphs. Email: dfnh1983@126.com

摘要/Abstract

摘要：

称图G是一个超爪,如果它同构于完全二部图K_1,2。连接两个超爪的二度顶点而得到的图称为超双爪。一个图称为是超双爪无关图的, 如果它没有导出的超双爪。证明了一个连通超双爪无关图的二部图G, 当δ(G)≥4时是可折叠的, 显然G是超欧拉的。最后, 猜测定理1.1和1.2中的条件δ(G)≥4是最优的。

关键词: 超欧拉图; 可折叠图; 超双爪无关图

Abstract:

A super-claw is a graph isomorphic to the complete bipartite graph K_1,2, and a super-biclaw is defined as the graph obtained from two vertex disjoint super-claws adding an edge between the two vertices of degree 2 in each of the super-claws. A graph is called super-biclaw-free if it has no superbiclaw as an induced sub-graph. In this note, we prove that if G is a connected bipartite super-biclaw-free graph with δ(G)≥4, then G is collapsible, and of course supereulerian. Finally, we give a conjecture that the bound δ(G)≥4 in Theorem 1.1 and Theorem 1.2 is the best possible.

Key words: supereulerian graphs; collapsible graphs; super-biclaw-free graphs

苏贵福1, 徐兰2, 马蓓蓓1. 超双爪无关图的可折叠性[J]. J4, 2010, 45(4): 36-38.

SU Gui-fu1, XU Lan2, MA Bei-bei1. Collapsible super-biclaw-free graphs[J]. J4, 2010, 45(4): 36-38.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed