Article in volume
Authors:
Hajo J. Broersma
Department of Applied MathematicsFaculty EEMCSUniversity of TwenteP.O. Box 2177500 AE ENSCHEDETHE NETHERLANDS
email: h.j.broersma@utwente.nl
Title:
Edge degree conditions for dominating and spanning closed trails
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 363-381
Received: 2021-08-16 , Revised: 2022-02-04 , Accepted: 2022-02-08 , Available online: 2022-02-26 , https://doi.org/10.7151/dmgt.2450
Abstract:
Edge degree conditions have been studied since the 1980s, mostly with regard to
hamiltonicity of line graphs and the equivalent existence of dominating closed
trails in their root graphs, as well as the stronger property of being
supereulerian, i.e., admitting a spanning closed trail. For a graph $G$, let
${{\overline \sigma }_2}(G)=\min \{d(u)+d(v)| uv\in E(G)\}$. Chen et al.
conjectured that a 3-edge-connected graph $G$ with sufficientl large order $n$
and $\overline{\sigma}_{2}(G)> \frac{n}{9}-2$ is either supereulerian or
contractible to the Petersen graph. We show that the conjecture is true when
${{\overline \sigma }_2}(G)\geq 2(\lfloor n/15 \rfloor-1)$. Furthermore, we
show that for an essentially $k$-edge-connected graph $G$ with sufficiently
large order $n$, the following statements hold.
- (i) If $k=2$ and ${{\overline \sigma }_2}(G)\geq 2(\lfloor n/8 \rfloor-1)$, then either $L(G)$ is hamiltonian or $G$ can be contracted to one of a set of six graphs which are not supereulerian;
- (ii) If $k=3$ and ${{\overline \sigma }_2}(G)\geq 2(\lfloor n/15 \rfloor-1)$, then either $L(G)$ is hamiltonian or $G$ can be contracted to the Petersen graph.
Keywords:
hamiltonicity, supereulerian, degree sum, line graph
References:
- A. Benhocine, L. Clark, N. Köhler and H.J. Veldman, On circuits and pancyclic line graphs, J. Graph Theory 10 (1986) 411–425.
https://doi.org/10.1002/jgt.3190100317 - J.A. Bondy and U.S.R. Murty, Graph Theory, in: Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).
- R.A. Brualdi and R.F. Shanny, Hamiltonian line graphs, J. Graph Theory 5 (1981) 307–314.
https://doi.org/10.1002/jgt.3190050312 - P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44.
https://doi.org/10.1002/jgt.3190120105 - P.A. Catlin, Z.-Y. Han and H.-J Lai, Graphs without spanning closed trails, Discrete Math. 160 (1996) 81–91.
https://doi.org/10.1016/S0012-365X(95)00149-Q - W.-G. Chen, Z.-H. Chen and M. Lu, Properties of Catlin's reduced graphs and supereulerian graphs, Bull. Inst. Combin. Appl. 75 (2015) 47–63.
- Z.-H. Chen, A degree condition for spanning eulerian subgraphs, J. Graph Theory 17 (1993) 5–21.
https://doi.org/10.1002/jgt.3190170103 - Z.-H. Chen, Hamiltonicity and degrees of adjacent vertices in claw-free graphs, J. Graph Theory 86 (2017) 193–212.
https://doi.org/10.1002/jgt.22120 - Z.-H. Chen and H.-J. Lai, Collapsible graphs and matchings, J. Graph Theory 17 (1993) 597–605.
https://doi.org/10.1002/jgt.3190170506 - Z.-H. Chen and H.-J. Lai, Supereulerian graphs and the Petersen graph \uppercase\expandafter{\romannumeral2}, Ars Combin. 48 (1998) 271–282.
- Z.-H. Chen, H.-J. Lai and M. Zhang, Spanning trails with variations of Chvátal–Erdős conditions, Discrete Math. 340 (2017) 243–251.
https://doi.org/10.1016/j.disc.2016.08.002 - G.A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. (3) 2 (1952) 69–81.
https://doi.org/10.1112/plms/s3-2.1.69 - R.J. Faudree, E. Flandrin and Z. Ryjáček, Claw-free graphs–-A survey, Discrete Math. 164 (1997) 87–147.
https://doi.org/10.1016/S0012-365X(96)00045-3 - R.J. Gould, Recent advances on the Hamiltonian problem: survey \uppercase\expandafter{\romannumeral3}, Graphs Combin. 30 (2014) 1–46.
https://doi.org/10.1007/s00373-013-1377-x - F. Harary and C.St.J.A. Nash-Williams, On Eulerian and Hamiltonian graphs and line graphs, Canad. Math. Bull. 8 (1965) 701–709.
https://doi.org/10.4153/CMB-1965-051-3 - O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55.
https://doi.org/10.2307/2308928 - Y. Shao, Claw-free graphs and line graphs, Ph.D. Thesis (Morgantown, West Virginia University, 2005).
https://doi.org/10.33915/etd.2251 - T. Tian and L. Xiong, Traceability on $2$-connected line graphs, Appl. Math. Comput. 321 (2018) 463–471.
https://doi.org/10.1016/j.amc.2017.10.043 - T. Tian and L. Xiong, $2$-connected Hamiltonian claw-free graphs involving degree sum of adjacent vertices, Discuss. Math. Graph Theory 40 (2020) 85–106.
https://doi.org/10.7151/dmgt.2125 - H.J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994) 229–239.
https://doi.org/10.1016/0012-365X(92)00063-W
Close