Publications

A discharging method to find subgraphs having two edge-disjoint spanning trees.

Faculty Author(s): Zhan, Mingquan
Student Author(s): -
Department: MATH
Publication: Ars Combinatoria
Year: 2019
Abstract: For a graph $G$ without loops (but possibly containing parallel edges), let $\tau(G)$ denote the maximum number of edge-disjoint trees in $G$, and for disjoint subsets $A, B \subseteq V(G)$, let $e(A,B)$ denote the number of edges with exactly one endpoint in $A$ and the other in $B$. Furthermore, let a $P_2$-subgraph of $G$ denote a subgraph isomorphic to either $K_{1,2}$ or a 2-cycle. \par The main goal of the authors is to introduce a simple application of the discharging method, well known for its use in coloring problems, to the study of finding subgraphs with edge-disjoint spanning trees. In particular, the authors use the discharging method to prove that for any connected graph $G$ with $\delta(G) \ge 3$, if any $P_2$-subgraph of $G$, call it $H$, satisfies $e(V(H), V(G) - V(H))\ge 10$, then $G$ contains a nontrivial subgraph $T$ with $\tau(T) \ge 2$. \par The authors then use this statement to provide an alternate proof of a result by Li and Yang that every 3-connected, essentially 10-connected, line graph is Hamiltonian connected.
Link: A discharging method to find subgraphs having two edge-disjoint spanning trees.