Eulerian subgraphs and Hamilton-connected line graphs
A graph is super-Eulerian if it has a spanning Eulerian subgraph. A graph \(G\) is Hamilton-connected if for every pair \(u,v\) of distinct vertices of \(G\), there exists a \((u,v)\)-path containing all vertices of \(G\). If \(G\) is a graph, then \(L(G)\) and \(\kappa(G)\) denote the line graph and the connectivity of \(G\), respectively. Let \(C(l,k)\) be the class of 2-edge-connected graphs of order \(n\) such that \(G\in C(l,k)\) if and only if for every edge cut \(S\subseteq E(G)\) with \(| S| \leq 3\), each component of \(G-S\) has order at least \((n-k)/l\). The main results of the authors are the following two theorems. Theorem 1.3. If \(G\in C(6,0)\), then \(G\) is super-Eulerian if and only if \(G\) cannot be contracted to \(K_{2,3}\), \(K_{2,5}\), or \(K_{2,3}(e)\), where \(K_{2.3}(e)\) is obtained from \(K_{2,3}\) by replacing the edge \(e\in E(K_{2,3})\) by a path of length 2. Theorem 1.6. If \(G\in C(6,0)\) and \(n\geq 7\), then \(L(G)\) is Hamilton-connected if and only if \(\kappa(L(G))\geq 3\).
scientific article; zbMATH DE number 2137491