Spanning trees with pairwise nonadjacent endvertices

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

doi:10.1016/S0012-365X(96)00306-8

Spanning trees with pairwise nonadjacent endvertices

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

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

13 Citations (Scopus)

199 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 language	Undefined
Pages (from-to)	219-222
Number of pages	4
Journal	Discrete mathematics
Volume	170
Issue number	170
DOIs	https://doi.org/10.1016/S0012-365X(96)00306-8
Publication status	Published - 1997

Keywords

METIS-140784
IR-30145

Access to Document

10.1016/S0012-365X(96)00306-8

Bohme97spanningFinal published version, 209 KB

Cite this

@article{97c296e402a34dada6beac0e925d7f17,

title = "Spanning trees with pairwise nonadjacent endvertices",

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.",

keywords = "METIS-140784, IR-30145",

author = "T. B{\"o}hme and T. Bohme and Broersma, \{Haitze J.\} and F. Gobel and A.V. Kostochka and M. Stiebitz",

year = "1997",

doi = "10.1016/S0012-365X(96)00306-8",

language = "Undefined",

volume = "170",

pages = "219--222",

journal = "Discrete mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "170",

}

TY - JOUR

T1 - Spanning trees with pairwise nonadjacent endvertices

AU - Böhme, T.

AU - Bohme, T.

AU - Broersma, Haitze J.

AU - Gobel, F.

AU - Kostochka, A.V.

AU - Stiebitz, M.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

KW - METIS-140784

KW - IR-30145

U2 - 10.1016/S0012-365X(96)00306-8

DO - 10.1016/S0012-365X(96)00306-8

M3 - Article

SN - 0012-365X

VL - 170

SP - 219

EP - 222

JO - Discrete mathematics

JF - Discrete mathematics

IS - 170

ER -