Forbidden Subgraphs and Weak Locally Connected Graphs

A graph is called H-free if it has no induced subgraph isomorphic to H. A graph is called Nⁱ-locally connected if G[ { x∈ V(G) : 1 ≤ d_G(w, x) ≤ i} ] is connected and N₂-locally connected if G[ { uv: { uw, vw} ⊆ E(G) } ] is connected for every vertex w of G, respectively. In this paper, we prove the following.Every 2-connected P₇-free graph of minimum degree at least three other than the Petersen graph has a spanning Eulerian subgraph. This implies that every H-free 3-connected graph (or connected N⁴-locally connected graph of minimum degree at least three) other than the Petersen graph is supereulerian if and only if H is an induced subgraph of P₇, where P_i is a path of i vertices.Every 2-edge-connected H-free graph other than {K2,2k+1:kis a positive integer} is supereulerian if and only if H is an induced subgraph of P₄.If every connected H-free N³-locally connected graph other than the Petersen graph of minimum degree at least three is supereulerian, then H is an induced subgraph of P₇ or T_{2 , 2 , 3}, i.e., the graph obtained by identifying exactly one end vertex of P₃, P₃, P₄, respectively.If every 3-connected H-free N₂-locally connected graph is hamiltonian, then H is an induced subgraph of K_{1 , 4}. We present an algorithm to find a collapsible subgraph of a graph with girth 4 whose idea is used to prove our first conclusion above. Finally, we propose that the reverse of the last two items would be true.