Spanning trees with nonseparating paths

DOI10.1016/J.DISC.2015.08.020zbMATH Open1322.05078arXiv1409.4239OpenAlexW1762844847MaRDI QIDQ501078FDOQ501078

Authors: Cristina G. Fernandes, César Hernández-Vélez, Orlando Lee, José C. de Pina 

Publication date: 8 October 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We consider questions related to the existence of spanning trees in 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 any 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.

Full work available at URL: https://arxiv.org/abs/1409.4239

Recommendations

• Nonseparating cycles and planarity of graph-cells
• Non-separating spanning trees and out-branchings in digraphs of independence number 2
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• scientific article; zbMATH DE number 2059947
• scientific article; zbMATH DE number 1953097

zbMATH Keywords

spanning treenonseparating fundamental cyclenonseparating path

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Connectivity (05C40)

Cites Work

• Graph theory
• Graph theory
• Graph Classes: A Survey
• Graphs on surfaces
• The Planar Hamiltonian Circuit Problem is NP-Complete
• A Theorem on Planar Graphs
• How to Draw a Graph
• Non-separating paths in 4-connected graphs
• Graph connectivity after path removal
• Induced paths in 5-connected graphs
• Separation of vertices by a circuit
• Non-separating subgraphs
• Three small cubic graphs with interesting hamiltonian properties
• Non-separating subgraphs after deleting many disjoint paths

Cited In (3)

• Snarks with special spanning trees
• An exact method to generate all nondominated spanning trees
• Title not available (Why is that?)

This page was built for publication: Spanning trees with nonseparating paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501078)