Large homeomorphically irreducible trees in path‐free graphs
- 22 August 2019
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 93 (3) , 372-394
Abstract
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 ‐free graph of order has a HIT of order at least , and Diemunsch et al [Discrete Appl. Math. 185 (2015), pp. 71–78] proved that every connected ‐free graph of order has a HIT of order at least . 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 satisfies the condition that every connected ‐free graph has a HIT of order , then is a path of order at most . (b) Every connected ‐free graph of order has a HIT of order at least . (c) Every connected ‐free graph of order has a HIT of order at least . Furthermore, we focus on a ‐free graph having large minimum degree, and prove that for a connected ‐free graph of order , if , then has a HIT of order greater than .Keywords
Funding Information
- JSPS KAKENHI Grant (JP19K14584, JP18K13449)
This publication has 9 references indexed in Scilit:
- A characterization of -free graphs with a homeomorphically irreducible spanning treeDiscrete Applied Mathematics, 2015
- A New Characterization of $P_k$ P k -Free GraphsAlgorithmica, 2015
- Forbidden subgraphs and the existence of a spanning tree without small degree stemsDiscrete Mathematics, 2013
- Homeomorphically irreducible spanning treesJournal of Combinatorial Theory, Series B, 2013
- Homeomorphically Irreducible Spanning Trees in Locally Connected GraphsCombinatorics, Probability and Computing, 2012
- Graphs with homeomorphically irreducible spanning treesJournal of Graph Theory, 1990
- SPANNING TREES IN POLYTOPAL GRAPHSAnnals of the New York Academy of Sciences, 1979
- Graphs with homeomorphically irreducible spanning trees1974
- On a property of the class of n-colorable graphsJournal of Combinatorial Theory, Series B, 1974