Spanning Trees of a Claw-Free Graph Whose Reducible Stems Have Few Leaves

DOI10.1556/012.2023.01538arXiv2112.04102OpenAlexW4386478563MaRDI QIDQ6155584FDOQ6155584

Authors: Pham Hoang Ha 

Publication date: 5 June 2023

Published in: Studia Scientiarum Mathematicarum Hungarica (Search for Journal in Brave)

Abstract: Let $T$ be a tree, a vertex of degree one is a leaf of $T$ and a vertex of degree at least three is a branch vertex of $T$. For two distinct vertices $u,v$ of $T$, let $P_T[u,v]$ denote the unique path in $T$ connecting $u$ and $v.$ For a leaf $x$ of $T$, let $y_x$ denote the nearest branch vertex to $x$. For every leaf $x$ of $T$, we remove the path $P_T[x,y_x)$ from $T$, where $P_T[x,y_x)$ denotes the path connecting $x$ to $y_x$ in $T$ but not containing $y_x$. The resulting subtree of $T$ is called the {it reducible stem } of $T$. In this paper, we first use a new technique of Gould and Shull to state a new short proof for a result of Kano et al. on the spanning tree with a bounded number of leaves in a claw-free graph. After that, we use that proof to give a sharp sufficient condition for a claw-free graph having a spanning tree whose reducible stem has few leaves.

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

Recommendations

• Spanning trees whose stems have at most \(k\) leaves.
• Spanning trees whose reducible stems have a few branch vertices.
• Spanning trees with few peripheral branch vertices in a connected claw-free graph
• Spanning trees of connected \(K_{1,t}\)-free graphs whose stems have a few leaves
• Spanning trees with a bounded number of leaves in a claw-free graph.

zbMATH Keywords

claw-free graphleafspanning treereducible stem

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

This page was built for publication: Spanning Trees of a Claw-Free Graph Whose Reducible Stems Have Few Leaves

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