Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Open Access

Edge Degree Conditions for Dominating and Spanning Closed Trails

Accepted: 08 Feb 2022
Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

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 σ¯2(G)=min{ d(u)+d(v)|uvE(G) } {\bar \sigma _2}\left( G \right) = \min \left\{ {d\left( u \right) + d\left( v \right)|uv \in E\left( G \right)} \right\} . Chen et al. conjectured that a 3-edge-connected graph G with sufficientl large order n and σ¯2(G)>n9-2 {\bar \sigma _2}\left( G \right) > {n \over 9} - 2 is either supereulerian or contractible to the Petersen graph. We show that the conjecture is true when σ¯2(G)2( n/15 1) {\bar \sigma _2}\left( G \right) \ge 2\left( {\left\lfloor {n/15} \right\rfloor - 1} \right) . 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 σ¯2(G)2( n/8 1) {\bar \sigma _2}\left( G \right) \ge 2\left( {\left\lfloor {n/8} \right\rfloor - 1} \right) , 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 σ¯2(G)2( n/15 1) {\bar \sigma _2}\left( G \right) \ge 2\left( {\left\lfloor {n/15} \right\rfloor - 1} \right) , then either L(G) is hamiltonian or G can be contracted to the Petersen graph.

MSC 2010

[1] 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.319010031710.1002/jgt.3190100317 Search in Google Scholar

[2] J.A. Bondy and U.S.R. Murty, Graph Theory, in: Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).10.1007/978-1-84628-970-5 Search in Google Scholar

[3] R.A. Brualdi and R.F. Shanny, Hamiltonian line graphs, J. Graph Theory 5 (1981) 307–314. https://doi.org/10.1002/jgt.319005031210.1002/jgt.3190050312 Search in Google Scholar

[4] P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44. https://doi.org/10.1002/jgt.319012010510.1002/jgt.3190120105 Search in Google Scholar

[5] 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-Q10.1016/S0012-365X(95)00149-Q Search in Google Scholar

[6] 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. Search in Google Scholar

[7] Z.-H. Chen, A degree condition for spanning eulerian subgraphs, J. Graph Theory 17 (1993) 5–21. https://doi.org/10.1002/jgt.319017010310.1002/jgt.3190170103 Search in Google Scholar

[8] 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.2212010.1002/jgt.22120 Search in Google Scholar

[9] Z.-H. Chen and H.-J. Lai, Collapsible graphs and matchings, J. Graph Theory 17 (1993) 597–605. https://doi.org/10.1002/jgt.319017050610.1002/jgt.3190170506 Search in Google Scholar

[10] Z.-H. Chen and H.-J. Lai, Supereulerian graphs and the Petersen graph II, Ars Combin. 48 (1998) 271–282. Search in Google Scholar

[11] Z.-H. Chen, H.-J. Lai and M. Zhang, Spanning trails with variations of Chvátal– Erd˝os conditions, Discrete Math. 340 (2017) 243–251. https://doi.org/10.1016/j.disc.2016.08.00210.1016/j.disc.2016.08.002 Search in Google Scholar

[12] 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.6910.1112/plms/s3-2.1.69 Search in Google Scholar

[13] 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-310.1016/S0012-365X(96)00045-3 Search in Google Scholar

[14] R.J. Gould, Recent advances on the Hamiltonian problem: survey III, Graphs Combin. 30 (2014) 1–46. https://doi.org/10.1007/s00373-013-1377-x10.1007/s00373-013-1377-x Search in Google Scholar

[15] 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-310.4153/CMB-1965-051-3 Search in Google Scholar

[16] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55. https://doi.org/10.2307/230892810.2307/2308928 Search in Google Scholar

[17] Y. Shao, Claw-free graphs and line graphs, Ph.D. Thesis (Morgantown, West Virginia University, 2005). https://doi.org/10.33915/etd.225110.33915/etd.2251 Search in Google Scholar

[18] 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.04310.1016/j.amc.2017.10.043 Search in Google Scholar

[19] 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.212510.7151/dmgt.2125 Search in Google Scholar

[20] 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-W10.1016/0012-365X(92)00063-W Search in Google Scholar

• A Note About Monochromatic Components in Graphs of Large Minimum Degree

Recommended articles from Trend MD