Completely independent spanning trees in line graphs

DOI10.1007/S00373-023-02688-YzbMATH Open1519.05048arXiv2209.09565OpenAlexW4385493656MaRDI QIDQ6133659FDOQ6133659

Authors: Toru Hasunuma 

Publication date: 21 August 2023

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: 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 $K_n$ of order $ngeq4$, there are $lfloorfracn+12floor$ completely independent spanning trees in $L(K_n)$ where the number $lfloorfracn+12floor$ is optimal, such that $lfloorfracn+12floor$ completely independent spanning trees still exist in the graph obtained from $L(K_n)$ by deleting any vertex (respectively, any induced path of order at most $fracn2$) for $n=4$ or odd $ngeq5$ (respectively, even $ngeq6$). Concerning the connectivity and the number of completely independent spanning trees, we moreover show the following, where $delta(G)$ denotes the minimum degree of $G$. ${\displaystyle }$ $$ Every $2k$-connected line graph $L(G)$ has $k$ completely independent spanning trees if $G$ is not super edge-connected or $delta(G)geq2k$. ${\displaystyle }$ $$ Every $(4k-2)$-connected line graph $L(G)$ has $k$ completely independent spanning trees if $G$ is regular. ${\displaystyle }$ $$ Every $(k^2+2k-1)$-connected line graph $L(G)$ with $delta(G)geqk+1$ has $k$ completely independent spanning trees.

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

Recommendations

• Completely independent spanning trees in the underlying graph of a line digraph
• Completely independent spanning trees in some regular graphs
• Degree condition for completely independent spanning trees
• Completely independent spanning trees in \(k\)-th power of graphs
• Minimum Degree Conditions and Optimal Graphs for Completely Independent Spanning Trees

zbMATH Keywords

connectivityline graphscomplete graphscompletely independent spanning trees

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Spanning trees: A survey
• On computing a conditional edge-connectivity of a graph
• Edge-connectivity and edge-disjoint spanning trees
• Independent trees in graphs
• Structural properties of subdivided-line graphs
• Minimum Degree Conditions and Optimal Graphs for Completely Independent Spanning Trees
• Dirac's Condition for Completely Independent Spanning Trees
• Ore's condition for completely independent spanning trees
• Two counterexamples on completely independent spanning trees
• Title not available (Why is that?)
• Completely independent spanning trees in torus networks
• Completely independent spanning trees in the underlying graph of a line digraph
• Independent trees in planar graphs
• Finding Four Independent Trees
• Degree condition for completely independent spanning trees
• Note on the connectivity of line graphs
• Packing spanning trees in highly essentially connected graphs
• Constructing dual-CISTs of folded divide-and-swap cubes
• Constructing Completely Independent Spanning Trees in a Family of Line-Graph-Based Data Center Networks

Cited In (7)

• Title not available (Why is that?)
• Completely independent spanning trees in the underlying graph of a line digraph
• Minimum Degree Conditions and Optimal Graphs for Completely Independent Spanning Trees
• Completely independent spanning trees in some regular graphs
• Independent spanning trees on even networks
• Independent spanning trees with small depths in iterated line digraphs
• Every 2-connected \(\{\text{claw}, Z_2\}\)-free graph with minimum degree at least 4 contains two CISTs

This page was built for publication: Completely independent spanning trees in line graphs

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