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