×

A characterization of \(P_5\)-free graphs with a homeomorphically irreducible spanning tree. (English) Zbl 1311.05129

Summary: A spanning tree with no vertices of degree two is called a homeomorphically irreducible spanning tree (or a HIST) of a graph. In M. Furuya and S. Tsuchiya [Discrete Math. 313, No. 20, 2206–2212 (2013; Zbl 1281.05049)], the sets of forbidden subgraphs that imply the existence of a HIST in a connected graph of sufficiently large order were characterized. In this paper, we focus on characterizing connected \(P_5\)-free graphs which have a HIST. As applications of our main result, we also characterize forbidden pairs that imply the existence of a HIST.

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C05 Trees

Citations:

Zbl 1281.05049
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albertson, M. O.; Berman, D. M.; Hutchinson, J. P.; Thomassen, C., Graphs with homeomorphically irreducible spanning trees, J. Graph Theory, 14, 247-258 (1990) · Zbl 0744.05013
[2] Bacsó, G.; Tuza, Z., Dominating cliques in \(P_5\)-free graphs, Period. Math. Hungar., 21, 303-308 (1990) · Zbl 0746.05065
[3] Chartrand, G.; Lesniak, L., Graphs & Digraphs (2005), Chapman and Hall/CRC: Chapman and Hall/CRC Boca Raton, Florida, U.S.A · Zbl 1057.05001
[4] Chen, G.; Ren, H.; Shan, S., Homeomorphically irreducible spanning trees in locally connected graph, Combin. Probab. Comput., 21, 107-111 (2012) · Zbl 1238.05054
[5] Cozzens, M. B.; Kelleher, L. L., Dominating cliques in graphs, Discrete Math., 86, 101-116 (1990) · Zbl 0722.05040
[6] Fujita, S.; Kawarabayashi, K.; Lucchesi, C. L.; Ota, K.; Plummer, M.; Saito, A., A pair of forbidden subgraphs and perfect matchings, J. Combin. Theory Ser. B, 96, 315-324 (2006) · Zbl 1090.05057
[7] Furuya, M.; Tsuchiya, S., Forbidden subgraphs and the existence of a spanning tree without small degree stems, Discrete Math., 313, 2206-2212 (2013) · Zbl 1281.05049
[8] Joffe, P., Some properties of 3-polytopal graphs (1982), CUNY, (Ph.D. dissertation)
[9] Nakamoto, A.; Tsuchiya, S., HISTs of triangulations on surfaces, AKCE Int. J. Graphs Comb., 10, 1-14 (2013) · Zbl 1302.05042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.