Fan-Type Conditions for Collapsible Graphs

Abstract

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)\}\ge \frac{n}{(g-2)p}–ϵ$ for each pair of vertices $u,v$ at distance two, where $g\in \{3,4\}$ is the girth of $G$, and $p\ge 2$ and $ϵ\ge 0$ are fixed numbers. In this paper, we study the Fan-type conditions for collapsible graphs and supereulerian graphs.