Forbidden subgraphs and the existence of a spanning tree without small degree stems

DOI10.1016/j.disc.2013.05.020zbMath1281.05049OpenAlexW2036601215MaRDI QIDQ390302

Shoichi Tsuchiya, Michitaka Furuya

Publication date: 23 January 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2013.05.020

zbMATH Keywords

forbidden subgraph\([2HIST-extendabilityhomeomorphically irreducible spanning tree (HIST)k\)-spanning tree (\([2]k\)-ST)]

Mathematics Subject Classification ID

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

Related Items (3)

Characterization of graphs of diameter 2 containing a homeomorphically irreducible spanning tree ⋮ Spanning trees without adjacent vertices of degree 2 ⋮ A characterization of \(P_5\)-free graphs with a homeomorphically irreducible spanning tree

Cites Work

• Unnamed Item
• Forbidden triples and traceability: A characterization
• Characterizing forbidden pairs for hamiltonian properties
• Forbidden induced subgraphs for perfect matchings
• A pair of forbidden subgraphs and perfect matchings.
• On a property of the class of n-colorable graphs
• Homeomorphically Irreducible Spanning Trees in Locally Connected Graphs
• Graphs with homeomorphically irreducible spanning trees
• Graph classes characterized both by forbidden subgraphs and degree sequences

This page was built for publication: Forbidden subgraphs and the existence of a spanning tree without small degree stems