Large homeomorphically irreducible trees in path‐free graphs

• Published in: Journal of graph theory 2020-03, Vol.93 (3), p.372-394
• Main Authors: Furuya, Michitaka, Tsuchiya, Shoichi
• Format: Article
• Language: English
• Subjects: Apexes; connected dominating set; Graph theory; Graphs; homeomorphically irreducible tree; path‐free graph; Trees (mathematics)
• ISSN: 0364-9024; 1097-0118
• DOI: 10.1002/jgt.22492

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 P4‐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 P5‐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 P6‐free graph of order n≥9 has a HIT of order at least (n+1)/2. (c) Every connected P7‐free graph of order n≥9 has a HIT of order at least (n+3)/3. Furthermore, we focus on a P6‐free graph having large minimum degree, and prove that for a connected P6‐free graph G of order n≥11, if δ(G)≥3, then G has a HIT of order greater than (δ(G)n/δ(G)+1)−1.