Graph whose edges are in small cycles. (English) Zbl 0761.05059
Summary: In 1987 P. Paulraja conjectured the following: (i) If every edge of a 2-connected graph \(G\) lies in a cycle of length at most 4 in \(G\), then \(G\) has a dominating closed trail. (ii) If, in addition, \(\delta(G)\geq 3\), then \(G\) has a closed spanning trail.
Collapsible graphs were defined and studied by P. A. Catlin [J. Graph Theory 12, No. 1, 29-44 (1988; Zbl 0659.05073)]. Catlin showed that if \(H\) is a collapsible subgraph of \(G\), then \(G\) has a spanning closed trail if and only if \(G/H\), the graph obtained from \(G\) by contracting \(H\), has a spanning closed trail. P. A. Catlin [Combinatorics, graph theory, and computing, Proc. 18th Southeast Conf., Boca Raton/Fl. 1987, Congr. Numerantium 58, 233-246 (1987; Zbl 0647.05037)] conjectured that a graph satisfying the hypothesis of (ii) is collapsible. In this paper, all three conjectures are proved.
Collapsible graphs were defined and studied by P. A. Catlin [J. Graph Theory 12, No. 1, 29-44 (1988; Zbl 0659.05073)]. Catlin showed that if \(H\) is a collapsible subgraph of \(G\), then \(G\) has a spanning closed trail if and only if \(G/H\), the graph obtained from \(G\) by contracting \(H\), has a spanning closed trail. P. A. Catlin [Combinatorics, graph theory, and computing, Proc. 18th Southeast Conf., Boca Raton/Fl. 1987, Congr. Numerantium 58, 233-246 (1987; Zbl 0647.05037)] conjectured that a graph satisfying the hypothesis of (ii) is collapsible. In this paper, all three conjectures are proved.
MSC:
| 05C38 | Paths and cycles |
| 05C40 | Connectivity |
| 05C75 | Structural characterization of families of graphs |
Keywords:
small cycles; 2-connected graph; dominating closed trail; closed spanning trail; collapsible graphs; collapsible subgraphReferences:
| [1] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Elsevier: Elsevier Amsterdam · Zbl 1134.05001 |
| [2] | Catlin, P. A., A reduction method to find spanning eulerian subgraphs, J. Graph Theory, 12, 29-44 (1988) · Zbl 0659.05073 |
| [3] | Catlin, P. A., Supereulerian graph, Collapsable graphs and 4-cycles, Congr. Numer., 56, 223-246 (1987) |
| [4] | H.-J. Lai, Reduction towards collapsibility, submitted.; H.-J. Lai, Reduction towards collapsibility, submitted. · Zbl 0843.05089 |
| [5] | Lai, H.-J., Contractions and eulerian subgraphs, (Ph.D. Thesis (1988), Wayne State University) |
| [6] | Paulraja, P., On graphs admitting spanning eulerian subgraphs, Ars Combin., 24, 57-65 (1987) · Zbl 0662.05044 |
| [7] | Paulraja, P., Research Problem. 85, Discrete Math., 64, 109 (1987) |
| [8] | Paulraja, P., Research Problem. 86, Discrete Math., 64, 317 (1987) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
