Graphs and Combinatorics Дискретная математика и комбинаторика

Spanning Trees with Few Branch Vertices in a Chair-Free Graph

Janee Schrader, Warren Shull
Springer Nature · 2025-08-26 · DOI 10.1007/s00373-025-02945-2

Аннотация

Abstract If one edge of a claw is subdivided, the resulting graph is called a chair . Spanning trees in claw-free graphs have been widely studied, but we are unable to find prior results on spanning trees in chair-free graphs. We show two sufficient conditions for a connected chair-free graph to have a spanning tree with a bounded number of branch vertices. First, a connected chair-free graph has a spanning tree with at most k branch vertices if its independence number is at most $$ 2k+2 $$ . Second, if a connected chair-free graph of order n has a spanning tree with at most 4 leaves and the degree sum of any five independent vertices is at least $$ n-2 $$ , then the graph has a spanning tree with at most one branch vertex. Similarities and differences between claw-free and chair-free graphs are discussed, and several related conjectures are proposed.

Читать у издателя →