On the independent spanning tree conjectures and related problems

Graph theory;Structural graph theory;Independent spanning tree conjecture;Edge-independent spanning tree conjecture;Connectivity;Edge-connectivity;Independent spanning trees;Edge-independent spanning trees;Ear decomposition;Chain decomposition;Graph decomposition;Györi-Lovász theorem

Hoyer, Alexander ; Thomas, Robin Mathematics Tetali, Prasad Warnke, Lutz Yu, Xingxing Vempala, Santosh ; Thomas, Robin

University:Georgia Institute of Technology

Department:Mathematics

关键词: Graph theory;    Structural graph theory;    Independent spanning tree conjecture;    Edge-independent spanning tree conjecture;    Connectivity;    Edge-connectivity;    Independent spanning trees;    Edge-independent spanning trees;    Ear decomposition;    Chain decomposition;    Graph decomposition;    Györi-Lovász theorem;   

Others  :  https://smartech.gatech.edu/bitstream/1853/61777/1/HOYER-DISSERTATION-2019.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

We say that trees with common root are (edge-)independent if, for any vertex in their intersection, the paths to the root induced by each tree are internally (edge-)disjoint. The relationship between graph (edge-)connectivity and the existence of (edge-)independent spanning trees is explored. The (Edge-)Independent Spanning Tree Conjecture states that every k-(edge-)connected graph has k-(edge-)independent spanning trees with arbitrary root. We prove the case k = 4 of the Edge-Independent Spanning Tree Conjecture using a graph decomposition similar to an ear decomposition, and give polynomial-time algorithms to construct the decomposition and the trees. We provide alternate geometric proofs for the cases k = 3 of both the Independent Spanning Tree Conjecture and Edge-Independent Spanning Tree Conjecture by embedding the vertices or edges in a 2-simplex, and conjecture higher-dimension generalizations. We provide a partial result towards a generalization of the Independent Spanning Tree Conjecture, in which local connectivity between the root and a vertex set S implies the existence of trees whose independence properties hold only in S. Finally, we prove and generalize a theorem of Györi and Lovász on partitioning a k-connected graph, and give polynomial-time algorithms for the cases k = 2, 3, 4 using the graph decompositions used to prove the corresponding cases of the Independent Spanning Tree Conjecture.