Spanning trees with pairwise nonadjacent endvertices

Böhme, T. and Broersma, H.J. and Göbel, F. and Kostochka, A.V. and Stiebitz, M. (1997) Spanning trees with pairwise nonadjacent endvertices. Discrete Mathematics, 170 (1-3). pp. 219-222. ISSN 0012-365X

Preview

PDF
208Kb

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.
Item Type:	Article
Copyright:	© 1997 Elsevier Science
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/30145
Official URL:	http://dx.doi.org/10.1016/S0012-365X(96)00306-8
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 140784