超双爪无关图的可折叠性(英文)

Collapsible super-biclaw-free graphs

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

A super-claw is a graph isomorphic to the complete bipartite graph K1,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.