Forbidden subgraphs restricting vertices of degree two in a spanning tree

Michitaka Furuya¹ ; Shoichi Tsuchiya²

¹Tokyo University of Science
²Senshu University

The electronic journal of combinatorics, Tome 31 (2024) no. 3

Résumé

For a tree $T$, let $V_{2}(T)$ denote the set of vertices of $T$ having degree $2$. Let $G$ be a connected graph. A spanning tree $T$ of $G$ with $V_{2}(T)=\emptyset $ is called a homeomorphically irreducible spanning tree (or a HIST) of $G$. We focus on two relaxations of HISTs as follows:(1) A spanning tree $T$ of $G$ such that the maximum order of components of the subgraph of $T$ induced by $V_{2}(T)$ is bounded.(2) A spanning tree $T$ of $G$ such that $|V_{2}(T)|$ is bounded.A spanning tree satisfying (1) was recently introduced by Lyngsie and Merker, and a spanning tree satisfying (2) is known as a tool for constructing a HIST. In this paper, we define an SP-system, which is a useful concept for finding a spanning tree satisfying (1) or (2) (or both). To demonstrate how the concept works, we characterize forbidden subgraph conditions forcing connected graphs to have such spanning trees.

Détail

DOI : 10.37236/11920

Classification : 05C05, 05C75
Mots-clés : homeomorphically irreducible spanning tree