Graphs with all spanning trees nonisomorphic

DOI10.1016/0012-365X(94)00363-NMaRDI QIDQ1923474zbMATH OpenOpenAlexFDO

Authors Lars Døvling Andersen, Preben Dahl Vestergaard

Publication date 23 March 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(94)00363-n

zbMATH Keywords

spanning trees

Mathematics Subject Classification ID

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

Review text

If a connected graph \(G\) with at least two vertices has the property that all its spanning trees are pairwise nonisomorphic, then every end-block of \(G\) has just one edge. This is one of the main results of this paper. By an easy construction it is shown that any graph is an induced subgraph of a connected graph without two distinct isomorphic spanning trees. Generalizations of this construction lead to some related results.

Recommendations

• Spanning trees with pairwise nonadjacent endvertices
• Publication:4204164
• scientific article; zbMATH DE number 4083675
• Spanning trees with large number of end vertices
• scientific article; zbMATH DE number 3855138

Cites work

• Graphen, worin je zwei Gerüste isomorph sind
• Graphs with one isomorphism class of spanning unicyclic graphs
• Graphs with two isomorphism classes of spanning unicycle subgraphs
• scientific article; zbMATH DE number 3467129 (Why is no real title available?)
• scientific article; zbMATH DE number 4123753 (Why is no real title available?)
• Non-separating induced cycles in graphs
• The graphs, all of whose spanning trees are isomorphic to each other
• Über Graphen mit isomorphen Gerüsten

Cited in

(6)

• Spanning trees with pairwise nonadjacent endvertices
• Graphs with only caterpillars as spanning trees
• scientific article; zbMATH DE number 3855138 (Why is no real title available?)
• scientific article; zbMATH DE number 3991551 (Why is no real title available?)
• scientific article; zbMATH DE number 4123753 (Why is no real title available?)
• Largest non-unique subgraphs

This page was built for publication: Graphs with all spanning trees nonisomorphic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1923474)