Hitting all longest cycles in a graph
Resumo
Let lct(G) be the minimum size of a set of vertices that contains at least one vertex in every longest cycle of a graph G. We show that lct(G) = 1 if G is a 3-tree, and that lct(G) ≤ 2 if G is a 2-connected partial 3-tree.
Referências
Arnborg, S., Proskurowski, A., and Corneil, D. (1990). Forbidden minors characterization of partial 3-trees. Discrete Mathematics, 80(1):1–19.
Bodlaender, H. (1998). A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1):1–45.
Brandstädt, A., Le, V., and Spinrad, J. (1999). Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.
De Rezende, S., Fernandes, C., Martin, D., and Wakabayashi, Y. (2013). Intersecting longest paths. Discrete Mathematics, 313:1401–1408.
Diestel, R. (2010). Graph Theory, volume 173 of Graduate texts in mathematics. Springer, 4th edition.
Heinz, M. (2013). Tree-decomposition: Graph minor theory and algorithmic implications. Master’s thesis, Technischen Universität Wien.
Jobson, A., Kézdy, A., Lehel, J., and White, S. (2016). Detour trees. Discrete Applied Mathematics, 206:73–80.
Rautenbach, D. and Sereni, J.-S. (2014). Transversals of longest paths and cycles. SIAM Journal of Discrete Mathematics, 28(1):335–341.
Thomas, R. and Yu, X. (1994). 4-Connected projective-planar graphs are Hamiltonian. Journal of Combinatorial Theory, Series B, 62(1):114–132.
Thomassen, C. (1978). Hypohamiltonian graphs and digraphs. In Alavi, Y. and Lick, D. R., editors, Proceedings of the International Conference of the Theory and Applications of Graphs (1976), volume 642 of Lecture Notes in Mathematics, pages 557–571. Springer.
Tutte, W. (1956). A theorem on planar graphs. Transactions of the American Mathematical Society, 82:99–116.
Bodlaender, H. (1998). A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1):1–45.
Brandstädt, A., Le, V., and Spinrad, J. (1999). Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.
De Rezende, S., Fernandes, C., Martin, D., and Wakabayashi, Y. (2013). Intersecting longest paths. Discrete Mathematics, 313:1401–1408.
Diestel, R. (2010). Graph Theory, volume 173 of Graduate texts in mathematics. Springer, 4th edition.
Heinz, M. (2013). Tree-decomposition: Graph minor theory and algorithmic implications. Master’s thesis, Technischen Universität Wien.
Jobson, A., Kézdy, A., Lehel, J., and White, S. (2016). Detour trees. Discrete Applied Mathematics, 206:73–80.
Rautenbach, D. and Sereni, J.-S. (2014). Transversals of longest paths and cycles. SIAM Journal of Discrete Mathematics, 28(1):335–341.
Thomas, R. and Yu, X. (1994). 4-Connected projective-planar graphs are Hamiltonian. Journal of Combinatorial Theory, Series B, 62(1):114–132.
Thomassen, C. (1978). Hypohamiltonian graphs and digraphs. In Alavi, Y. and Lick, D. R., editors, Proceedings of the International Conference of the Theory and Applications of Graphs (1976), volume 642 of Lecture Notes in Mathematics, pages 557–571. Springer.
Tutte, W. (1956). A theorem on planar graphs. Transactions of the American Mathematical Society, 82:99–116.
Publicado
02/07/2017
Como Citar
FERNANDES, Cristina G.; GUTIÉRREZ, Juan.
Hitting all longest cycles in a graph. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 33-36.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2017.3185.
