Spanning Eulerian subgraphs and Catlin’s reduced graphs. (English) Zbl 1351.05136
P. A. Catlin [Congr. Numerantium 76, 173–181 (1990; Zbl 0862.05058)] posed the following conjecture that is still open.
Conjecture 1. Every 3-edge-connected graph of order at most 17 has a spanning Eulerian subgraph or it can be contractible to the Petersen graph.
The second author and H.-J. Lai [Ars Comb. 48, 271–282 (1998; Zbl 0962.05035)] proved Conjecture 1 is true for those graphs of order at most 11 and even more they showed that every connected graph of order at most 11 and of minimum degree at least 3 has a reduction of order at most two of the Petersen graph. In this paper, the authors improve this result and show the following.
Theorem 2. Every 3-edge-connected graph \(G\) of order at most 15 with its reduction \(G'\) satisfies exactly one of the following conditions.
Theorem 3. Let \(G\) be a 3-edge-connected graph of order \(n\) satisfying exactly one of the following conditions
Finally, the authors posed the following conjecture that is a refinement of Conjecture 1.
Conjecture 4. Every 3-edge-connected simple graph of order \(n\) at most 17 has a spanning Eulerian subgraph or its reduction is either the Petersen graph \(P\) or those graph obtained from \(P\) by replacing one vertex of \(P\) by two graphs, respectively.
Conjecture 1. Every 3-edge-connected graph of order at most 17 has a spanning Eulerian subgraph or it can be contractible to the Petersen graph.
The second author and H.-J. Lai [Ars Comb. 48, 271–282 (1998; Zbl 0962.05035)] proved Conjecture 1 is true for those graphs of order at most 11 and even more they showed that every connected graph of order at most 11 and of minimum degree at least 3 has a reduction of order at most two of the Petersen graph. In this paper, the authors improve this result and show the following.
Theorem 2. Every 3-edge-connected graph \(G\) of order at most 15 with its reduction \(G'\) satisfies exactly one of the following conditions.
- –
- If the order of \(G\) is at most 13, then either \(G\) has a spanning Eulerian subgraph or \(G^\prime\) is the Petersen graph.
- –
- If the order of \(G\) is at most 14, then either \(G\) has a spanning Eulerian subgraph, or \(G^\prime\) has order 14 that can be contractible to the Petersen graph.
- –
- If the order of \(G\) is 15, \(G\) has no spanning Eulerian subgraph and not in the graphs above, then \(G=G^\prime\) and \(G\) is both 2-connected and essentially 4-edged-connected graph with girth at least 5 and its vertex set being composed of vertices of degree 3 and 4 (of size 3 and independent).
Theorem 3. Let \(G\) be a 3-edge-connected graph of order \(n\) satisfying exactly one of the following conditions
- –
- the sum of degrees of two nonadjacent vertices in \(G\) is \(\frac {2n-29}{15}\),
- –
- the size of a maximum matching of \(G\) is at most 6,
- –
- the independence number is at most 5.
Finally, the authors posed the following conjecture that is a refinement of Conjecture 1.
Conjecture 4. Every 3-edge-connected simple graph of order \(n\) at most 17 has a spanning Eulerian subgraph or its reduction is either the Petersen graph \(P\) or those graph obtained from \(P\) by replacing one vertex of \(P\) by two graphs, respectively.
Reviewer: Liming Xiong (Beijing)
MSC:
05C45 | Eulerian and Hamiltonian graphs |
05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
05C40 | Connectivity |