Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Spanning Trees With Nonseparating Paths
Author: Fernandes
Cristina G.; Hernandez-Velez
Cesar; Lee
Orlando; de Pina
Jose C.
Abstract: We consider questions related to the existence of spanning trees in connected graphs with the property that, after the removal of any path in the tree, the graph remains connected. We show that, for planar graphs, the existence of trees with this property is closely related to the Hamiltonicity of the graph. For graphs with a 1- or 2-vertex cut, the Hamiltonicity also plays a central role. We also deal with spanning trees satisfying this property restricted to paths arising from fundamental cycles. The cycle space of a graph can be generated by the fundamental cycles of every spanning tree, and Tutte showed that, for a 3-connected graph, it can be generated by nonseparating cycles. We are also interested in the existence of a fundamental basis consisting of nonseparating cycles. (C) 2015 Elsevier B.V. All rights reserved.
Subject: Non-separating Subgraphs
Citation: Spanning Trees With Nonseparating Paths. Elsevier Science Bv, v. 339, p. 365-374 Jan-2016.
Rights: embargo
Identifier DOI: 10.1016/j.disc.2015.08.020
Date Issue: 2016
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
wos_000364265000039.pdf429.22 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.