×

Complete family reduction and spanning connectivity in line graphs. (English) Zbl 1502.05217

Summary: Complete families of connected graphs, introduced by P. A. Catlin in the 1980s, have been known useful in the study of certain graphical properties that are closed under taking contractions. We show that given any complete family \(\mathcal{C}\) of connected graphs such that \(\mathcal{C}\) contains graphs with sufficiently many edge-disjoint spanning trees, for any real number \(a\) and \(b\) with \(0 < a < 1\), there exists a finite obstacle family \(\mathcal{F} = \mathcal{F}(a, b, \mathcal{C})\) such that for any simple graph \(G\) on \(n\) vertices satisfying the Ore-type degree condition \[\min \{ d_G(u) + d_G(v) : u, v \in V(G) \text{ and } u v \notin E(G) \} \geq a n + b,\] either \(G \in \mathcal{C}\) or \(G\) can be contracted to a member in \(\mathcal{F} \). This result is applied to the study of spanning connectivity of line graphs. The spanning connectivity is the largest integer \(s\) such that for any \(k\) with \(0 \leq k \leq s\) and for any \(u, v \in V(G)\) with \(u \neq v\), \(G\) has a spanning subgraph \(H\) consisting of \(k\) internally disjoint \((u, v)\)-paths. Z. Ryjáček and P. Vrána [J. Graph Theory 66, No. 2, 152–173 (2011; Zbl 1228.05201)] prove that a fascinating conjecture of Thomassen on hamiltonian line graphs is equivalent to that every essentially 4-edge-connected graph has a 2-spanning-connected line graph. We prove that for any essentially 3-edge-connected graph \(G\) and any positive integer \(s\), if \(G\) satisfies an Ore degree condition lower bounded by an arbitrary linear function in the number of vertices, then \(L(G)\) is \(s\)-spanning-connected with only finitely many contraction obstacles. When \(s = 3\), we determine a finite graph family \(\mathcal{J}^\prime(n)\) such that for every simple graph \(G\) on \(n \geq 156\) vertices with \(\kappa(L(G)) \geq 3\) and satisfying \(d(u) + d(v) \geq \frac{ 2 ( n - 6 )}{ 5}\) for any pair of nonadjacent vertices \(u\) and \(v\), we have either \(\kappa^\ast(L(G)) \geq 3\) or \(G\) is contractible to a member in \(\mathcal{J}^\prime(n)\).

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C75 Structural characterization of families of graphs
05C40 Connectivity

Citations:

Zbl 1228.05201
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beineke, L., Derived Graphs and Digraphs, Beiträge zur Graphentheorie (1968), Teubner: Teubner Leipzig · Zbl 0179.29204
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer New York · Zbl 1134.05001
[3] Catlin, P. A., A reduction method to find spanning Eulerian subgraphs, J. Graph Theory, 12, 29-44 (1988) · Zbl 0659.05073
[4] Catlin, P. A., The reduction of graph families closed under contraction, Discrete Math., 160, 67-80 (1996) · Zbl 0867.05081
[5] Catlin, P. A.; Lai, H.-J., Spanning trails jointing two given edges, (Alavi, Y.; Chartrand, G.; Ollermann, O. R.; Schwenk, A. J., Graph Theory, Combinatorics, and Application, vol. 1 (1991)), 207-222 · Zbl 0841.05067
[6] Catlin, P. A.; Han, Z.; Lai, H.-J., Graphs without spanning Eulerian subgraphs, Discrete Math., 160, 81-91 (1996) · Zbl 0859.05060
[7] Catlin, P. A.; Hobbs, A. M.; Lai, H.-J., Graph families operations, Discrete Math., 230, 71-97 (2001) · Zbl 0969.05060
[8] Chen, W. G.; Chen, Z. H., Spanning Eulerian subgraphs and Catlin’s reduced graphs, J. Comb. Math. Comb. Comput., 96, 41-63 (2016) · Zbl 1351.05136
[9] Chen, Y.; Chen, Z.-H.; Lai, H.-J.; Li, P.; Wei, E., On spanning disjoint paths in line graphs, Graphs Comb., 29, 1721-1731 (2013) · Zbl 1290.05094
[10] Harary, F.; Nash-Williams, C. St. J.A., On Eulerian and Hamiltonian graphs and line graphs, Can. Math. Bull., 8, 701-709 (1965) · Zbl 0136.44704
[11] Hsu, D. F., On container width and length in graphs, groups, and networks, IEICE Trans. Fund., E77-A, 668-680 (1994)
[12] Hsu, L.-H.; Lin, C.-K., Graph Theory and Interconnection Networks (2009), CRC Press: CRC Press Boca Raton, London and New York · Zbl 1168.05002
[13] Huang, P.; Hsu, L., The spanning connectivity of the line graphs, Appl. Math. Lett., 24, 1614-1617 (2011) · Zbl 1219.05083
[14] Kučzel, R.; Xiong, L., Every 4-connected line graph is Hamiltonian if and only if it is Hamiltonian connected (2004), U.W.B. Pilsen, in: R. Kučzel, Hamiltonian properties of graphs, Ph.D. Thesis
[15] Lai, H.-J.; Lai, H. Y., Duality of graph families, Discrete Math., 110, 165-177 (1992) · Zbl 0772.05084
[16] Lai, H.-J.; Shao, Y.; Yu, G.; Zhan, M., Hamiltonian connectedness in 3-connected line graphs, Discrete Appl. Math., 157, 982-990 (2009) · Zbl 1169.05344
[17] Li, P.; Lai, H.-J.; Liang, Y., Characterization of removable elements with respect to having k disjoint bases in a matroid, Discrete Appl. Math., 160, 2445-2451 (2012) · Zbl 1251.05028
[18] Li, P.; Lai, H.-J., On mod \((2 s + 1)\)-orientations of graphs, SIAM J. Discrete Math., 28, 1820-1827 (2014) · Zbl 1314.05105
[19] Li, P.; Li, H.; Chen, Y.; Fleischner, H.; Lai, H.-J., Supereulerian graphs with width s and s-collapsible graphs, Discrete Appl. Math., 200, 79-94 (2016) · Zbl 1329.05181
[20] Li, P.; Wang, K.; Zhan, M.; Lai, H.-J., Strongly spanning trailable graphs with short longest paths, Ars Comb., 137, 3-39 (2018) · Zbl 1474.05234
[21] Li, D.; Lai, H.-J.; Zhan, M., Eulerian subgraphs and Hamiltonian connected line graphs, Discrete Appl. Math., 145, 422-428 (2005) · Zbl 1057.05053
[22] Liu, Q.; Hong, Y.; Gu, X.; Lai, H.-J., Note on edge-disjoint spanning trees and eigenvalues, Linear Algebra Appl., 458, 128-133 (2014) · Zbl 1295.05146
[23] Lovász, L. M.; Thomassen, C.; Wu, Y.; Zhang, C.-Q., Nowhere-zero 3-flows and modulo k-orientations, J. Comb. Theory, Ser. B, 103, 587-598 (2013) · Zbl 1301.05154
[24] Matthews, M. M.; Sumner, D. P., Hamiltonian results in \(K_{1 , 3}\)-free graphs, J. Graph Theory, 8, 139-146 (1984) · Zbl 0536.05047
[25] Nash-Williams, C. St. J.A., Decompositions of finite graphs into forests, J. Lond. Math. Soc., 39, 12 (1964) · Zbl 0119.38805
[26] Ryjáček, Z., On a closure concept in claw-free graphs, J. Comb. Theory, Ser. B, 70, 217-224 (1997) · Zbl 0872.05032
[27] Ryjáček, Z.; Vrána, P., Line graphs of multigraphs and Hamiltonian-connectedness of claw-free graphs, J. Graph Theory, 66, 152-173 (2011) · Zbl 1228.05201
[28] Shao, Y., Claw-free Graphs and Line Graphs (2005), West Virginia University, Ph.D. Dissertation
[29] Thomassen, C., Reflections on graph theory, J. Graph Theory, 10, 309-324 (1986) · Zbl 0614.05050
[30] Xiong, W.; Xu, J.; Miao, Z.; Wu, Y.; Lai, H.-J., Supereulerian width of dense graphs, Discrete Math., 340, 2995-3001 (2017) · Zbl 1370.05120
[31] Yao, X.; Li, X.; Lai, H.-J., Degree conditions for group connectivity, Discrete Math., 310, 1050-1058 (2010) · Zbl 1231.05160
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.