Premium
Toughness and spanning trees in K 4 ‐minor‐free graphs
Author(s) -
Ellingham M. N.,
Shan Songling,
Ye Dong,
Zha Xiaoya
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22620
Subject(s) - combinatorics , mathematics , treewidth , trémaux tree , chordal graph , discrete mathematics , 1 planar graph , pathwidth , spanning tree , clique sum , vertex (graph theory) , planar graph , indifference graph , graph , line graph
For an integer k , a k ‐ tree is a tree with maximum degree at most k . More generally, if f is an integer‐valued function on vertices, an f ‐ tree is a tree in which each vertex v has degree at most f ( v ) . Let c ( G ) denote the number of components of a graph G . We show that if G is a connected K 4 ‐minor‐free graph and c ( G − S ) ≤ ∑ v ∈ S( f ( v ) − 1 )for all S ⊆ V ( G ) with S ≠ ∅ ,then G has a spanning f ‐tree. Consequently, if G is a 1 k − 1 ‐tough K 4 ‐minor‐free graph, then G has a spanning k ‐tree. These results are stronger than results for general graphs due to Win (for k ‐trees) and Ellingham, Nam, and Voss (for f ‐trees). The K 4 ‐minor‐free graphs form a subclass of planar graphs, and are identical to graphs of treewidth at most 2, and also to graphs whose blocks are series‐parallel. We provide examples to show that the inequality above cannot be relaxed by adding 1 to the right‐hand side, and also to show that our result does not hold for general planar graphs. Our proof uses a technique where we incorporate toughness‐related information into weights associated with vertices and cutsets.