Spanning trees with pairwise nonadjacent endvertices

T. Böhme, T. Bohme, Haitze J. Broersma, F. Gobel, A.V. Kostochka, M. Stiebitz

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)
67 Downloads (Pure)

Abstract

A spanning tree of a connected graph G is said to be an independency tree if all its endvertices are pairwise nonadjacent in G. We prove that a connected graph G has no independency tree if and only if G is a cycle, a complete graph or a complete bipartite graph the color classes of which have equal cardinality.
Original languageUndefined
Pages (from-to)219-222
Number of pages4
JournalDiscrete mathematics
Volume170
Issue number170
DOIs
Publication statusPublished - 1997

Keywords

  • METIS-140784
  • IR-30145

Cite this