Abstract
Let \(\mathrm {lct}(G)\) be the minimum size of a set of vertices that intersects every longest cycle of a 2-connected graph G. Let \(\mathrm {tw}(G)\) be the tree-width of G and \(\omega (G)\) be the size of a maximum clique in G. We show that \(\mathrm {lct}(G)\le \mathrm {tw}(G)-1\) for every G, and that \(\mathrm {lct}(G)\le \max \{1, {\omega (G){-}3}\}\) if G is chordal. Those results imply as corollaries that all longest cycles intersect in 2-connected series-parallel graphs and in 3-trees. We also strengthen the latter result and show that all longest cycles intersect in 2-connected graphs of tree-width at most 3, also known as partial 3-trees.
J. Gutiérrez—Research supported by FAPESP (Proc. 2015/08538-5).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Grötschel, M.: On intersections of longest cycles. In: Bollobás, B. (ed.) Graph Theory and Combinatorics, pp. 171–189 (1984)
Thomassen, C.: Hypohamiltonian graphs and digraphs. In: Alavi, Y., Lick, D.R. (eds.) Theory and Applications of Graphs. LNM, vol. 642, pp. 557–571. Springer, Heidelberg (1978). https://doi.org/10.1007/BFb0070410
Rautenbach, D., Sereni, J.S.: Transversals of longest paths and cycles. SIAM J. Discret. Math. 28(1), 335–341 (2014)
Jobson, A., Kzdy, A., Lehel, J., White, S.: Detour trees. Discret. Appl. Math. 206, 73–80 (2016)
van Aardt, S.A., Burger, A.P., Dunbar, J.E., Frick, M., Llano, B., Thomassen, C., Zuazua, R.: Destroying longest cycles in graphs and digraphs. Discret. Appl. Math. 186(Suppl. C), 251–259 (2015)
Fernandes, C., Gutiérrez, J.: Hitting all longest cycles in a graph. In: Anais do XXXVII congresso da sociedade brasileira de computação, pp. 87–90 (2017)
Balister, P., Győri, E., Lehel, J., Schelp, R.: Longest paths in circular arc graphs. Comb. Probab. Comput. 13(3), 311–317 (2004)
Cerioli, M., Lima, P.: Intersection of longest paths in graph classes. Electron. Notes Discret. Math. 55, 139–142 (2016)
Chen, F.: Nonempty intersection of longest paths in a graph with a small matching number. Czechoslov. Math. J. 65(140), 545–553 (2015)
Chen, G., Ehrenmüller, J., Fernandes, C., Heise, C., Shan, S., Yang, P., Yates, A.: Nonempty intersection of longest paths in seriesparallel graphs. Discret. Math. 340(3), 287–304 (2017)
de Rezende, S., Fernandes, C., Martin, D., Wakabayashi, Y.: Intersecting longest paths. Discret. Math. 313, 1401–1408 (2013)
Golan, G., Shan, S.: Nonempty intersection of longest paths in \(2{K_2}\)-free graphs. https://arxiv.org/abs/1611.05967 (2016)
Klavžar, S., Petkovšek, M.: Graphs with nonempty intersection of longest paths. Ars Comb. 29, 43–52 (1990)
Zamfirescu, T.: On longest paths and circuits in graphs. Math. Scand. 38(2), 211–239 (1976)
Cerioli, M.R., Fernandes, C.G., Gómez, R., Gutiérrez, J., Lima, P.T.: Transversals of longest paths. Electron. Notes Discret. Math. 62(Suppl. C), 135–140 (2017). IX Latin and American Algorithms, Graphs and Optimization, LAGOS 2017
Cerioli, M.R., Fernandes, C.G., Gómez, R., Gutiérrez, J., Lima, P.T.: Transversals of longest paths (2017). https://arxiv.org/abs/1712.07086
Chen, G., Faudree, R.J., Gould, R.J.: Intersections of longest cycles in k-connected graphs. J. Comb. Theory Ser. B 72(1), 143–149 (1998)
Hippchen, T.: Intersections of longest paths and cycles. Ph.D. thesis, Georgia State University (2008)
Jendrol, S., Skupień, Z.: Exact numbers of longest cycles with empty intersection. Eur. J. Comb. 18(5), 575–578 (1997)
Stewart, I.A., Thompson, B.: On the intersections of longest cycles in a graph. Exp. Math. 4(1), 41–48 (1995)
Diestel, R.: Graph Theory. GTM, vol. 173, 4th edn. Springer, Heidelberg (2017)
Bodlaender, H.: A partial \(k\)-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1), 1–45 (1998)
Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16(1), 47–56 (1974)
Heinz, M.: Tree-decomposition: graph minor theory and algorithmic implications. Master’s thesis, Technischen Universität Wien (2013)
Fomin, F., Thilikos, D.: New upper bounds on the decomposability of planar graphs. J. Graph Theory 51(1), 53–81 (2006)
Alon, N., Seymour, P., Thomas, R.: A separator theorem for nonplanar graphs. J. Am. Math. Soc. 3, 801–808 (1990)
Shabbir, A., Zamfirescu, C., Zamfirescu, T.: Intersecting longest paths and longest cycles: a survey. Electron. J. Graph Theory Appl. 1, 56–76 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Gutiérrez, J. (2018). Transversals of Longest Cycles in Chordal and Bounded Tree-Width Graphs. In: Bender, M., Farach-Colton, M., Mosteiro, M. (eds) LATIN 2018: Theoretical Informatics. LATIN 2018. Lecture Notes in Computer Science(), vol 10807. Springer, Cham. https://doi.org/10.1007/978-3-319-77404-6_41
Download citation
DOI: https://doi.org/10.1007/978-3-319-77404-6_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-77403-9
Online ISBN: 978-3-319-77404-6
eBook Packages: Computer ScienceComputer Science (R0)