Premium
Large homeomorphically irreducible trees in path‐free graphs
Author(s) -
Furuya Michitaka,
Tsuchiya Shoichi
Publication year - 2020
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.22492
Subject(s) - combinatorics , mathematics , distance hereditary graph , induced subgraph , graph , discrete mathematics , graph factorization , factor critical graph , complement graph , block graph , line graph , graph power , pathwidth , vertex (graph theory)
A subgraph of a graph is a homeomorphically irreducible tree (HIT) if it is a tree with no vertices of degree two. Furuya and Tsuchiya [Discrete Math. 313 (2013), pp. 2206–2212] proved that every connected P 4 ‐free graph of order n ≥ 5 has a HIT of order at least n − 1 , and Diemunsch et al [Discrete Appl. Math. 185 (2015), pp. 71–78] proved that every connected P 5 ‐free graph of order n ≥ 6 has a HIT of order at least n − 2 . In this paper, we continue the study of HITs in path‐free graphs and bring to a conclusion proving the following three results: (a) If a connected graph F satisfies the condition that every connected F ‐free graph G has a HIT of order Ω ( ∣ V ( G ) ∣ ) , then F is a path of order at most 7 . (b) Every connected P 6 ‐free graph of order n ≥ 9 has a HIT of order at least ( n + 1 ) / 2 . (c) Every connected P 7 ‐free graph of order n ≥ 9 has a HIT of order at least ( n + 3 ) / 3 . Furthermore, we focus on a P 6 ‐free graph having large minimum degree, and prove that for a connected P 6 ‐free graph G of order n ≥ 11 , if δ ( G ) ≥ 3 , then G has a HIT of order greater than ( δ ( G ) n / δ ( G ) + 1 ) − 1 .