2022/09/20 by Toru Hasunuma, Hasunuma, Toru
Computer Science · #05C05 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2209.09565
openalex publication_date 2022/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Completely independent spanning trees in a graph G are spanning trees of G such that for any two distinct vertices of G, the paths between them in the spanning trees are pairwise edge-disjoint and internally vertex-disjoint. In this paper, we present a tight lower bound on the maximum number of completely independent spanning trees in L(G), where L(G) denotes the line graph of a graph G. Based on a new characterization of a graph with k completely independent spanning trees, we also show that for any complete graph Kn of order n ≥ 4, there are \lfloor (n+1)/(2) \rfloor completely independent spanning trees in L(Kn) where the number \lfloor (n+1)/(2) \rfloor is optimal, such that \lfloor (n+1)/(2) \rfloor completely independent spanning trees still exist in the graph obtained from L(Kn) by deleting any vertex (respectively, any induced path of order at most (n)/(2)) for n = 4 or odd n ≥ 5 (respectively, even n ≥ 6). Concerning the connectivity and the number of completely independent spanning trees, we moreover show the following, where δ(G) denotes the minimum degree of G. \bullet Every 2k-connected line graph L(G) has k completely independent spanning trees if G is not super edge-connected or δ(G) ≥ 2k. \bullet Every (4k-2)-connected line graph L(G) has k completely independent spanning trees if G is regular. \bullet Every (k2+2k-1)-connected line graph L(G) with δ(G) ≥ k+1 has k completely independent spanning trees.