Completely independent spanning trees in line graphs

DOI10.1007/S00373-023-02688-YMaRDI QIDQ6133659zbMATH OpenOpenAlexFDO

Authors Toru Hasunuma

Publication date 21 August 2023

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

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

zbMATH Keywords

connectivityline graphscomplete graphscompletely independent spanning trees

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(9)

• Completely independent spanning trees in the underlying graph of a line digraph
• scientific article; zbMATH DE number 1444313 (Why is no real title available?)
• Independent spanning trees on even networks
• Independent spanning trees with small depths in iterated line digraphs
• Minimum Degree Conditions and Optimal Graphs for Completely Independent Spanning Trees
• Completely independent spanning trees in some regular graphs
• Every 2-connected \(\{\text{claw}, Z_2\}\)-free graph with minimum degree at least 4 contains two CISTs
• Completely independent spanning trees in (partial) \(k\)-trees
• Completely independent spanning trees in \(k\)-th power of graphs

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)