Fan-Type Conditions for Collapsible Graphs

A graph \(G\) is collapsible if for every even subset \(R \subseteq V(G)\), there is a spanning connected subgraph of \(G\) whose set of odd degree vertices is \(R\). A graph is supereulerian if it contains a spanning closed trail. It is known that every collapsible graph is supereulerian. A graph \(G\) of order \(n\) is said to satisfy a Fan-type condition if \(\max\{d(u),d(v)\} \geq \frac{n}{(g-2)p} – \epsilon\) for each pair of vertices \(u,v\) at distance two, where \(g \in \{3,4\}\) is the girth of \(G\), and \(p \geq 2\) and \(\epsilon \geq 0\) are fixed numbers. In this paper, we study the Fan-type conditions for collapsible graphs and supereulerian graphs.