
doi: 10.1007/bf02189088
The concept of collapsible graphs introduced by the author in J. Graph Theory 12, 29-44 (1988), is here used to study the existence of spanning Eulerian subgraphs. The following result is given: Let \(p\geq 2\) be a fixed integer, and let G be a connected graph of order n. If \(d(u)+d(v)>2n/p-2\) holds whenever uv\(\not\in E(G)\), and if n is sufficiently large compared to p, then either G has a spanning Eulerian subgraph, or G is contractible to a graph G' of order less than p and with no spanning Eulerian subgraph. The case \(p=2\) was proved by \textit{L. Lesniak-Foster} and \textit{J. E. Williamson} [Can. Math. Bull. 20, 215-220 (1977; Zbl 0357.05060)]. The case \(p=5\) was conjectured by \textit{A. Benhocine, L. Clark, N. Köhler} and \textit{H. J. Veldman} [J. Graph Theory 10, 411-425 (1986; Zbl 0608.05056)] when they proved vitually the case \(p=3\).
Eulerian and Hamiltonian graphs, spanning Eulerian subgraphs, collapsible graphs
Eulerian and Hamiltonian graphs, spanning Eulerian subgraphs, collapsible graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 12 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
