On the spanning trees of weighted graphs

Ernst W. Mayr; C. Greg Plaxton

doi:10.1007/BF01305236

On the spanning trees of weighted graphs

Ernst W. Mayr
, C. Greg Plaxton

Johann Wolfgang Goethe University
Department of Computer Science

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

18 Scopus citations

Abstract

Given a weighted graph, let W₁, W₂, W₃,... denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree of weight W₁ is at most k-1 edge swaps away from some spanning tree of weight W_k. Three other conjectures posed by Kano are proven for two special classes of graphs. Finally, we consider the algorithmic complexity of generating a spanning tree of weight W_k.

Original language	English
Pages (from-to)	433-447
Number of pages	15
Journal	Combinatorica
Volume	12
Issue number	4
DOIs	https://doi.org/10.1007/BF01305236
State	Published - Dec 1992
Externally published	Yes

Keywords

AMS subject classification code (1991): 05C05, 05C85, 68R10

Access to Document

10.1007/BF01305236

Cite this

@article{e54905027b864197aec0ee87b84b7607,

title = "On the spanning trees of weighted graphs",

abstract = "Given a weighted graph, let W1, W2, W3,... denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree of weight W1 is at most k-1 edge swaps away from some spanning tree of weight Wk. Three other conjectures posed by Kano are proven for two special classes of graphs. Finally, we consider the algorithmic complexity of generating a spanning tree of weight Wk.",

keywords = "AMS subject classification code (1991): 05C05, 05C85, 68R10",

author = "Mayr, \{Ernst W.\} and Plaxton, \{C. Greg\}",

year = "1992",

month = dec,

doi = "10.1007/BF01305236",

language = "English",

volume = "12",

pages = "433--447",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "4",

}

TY - JOUR

T1 - On the spanning trees of weighted graphs

AU - Mayr, Ernst W.

AU - Plaxton, C. Greg

PY - 1992/12

Y1 - 1992/12

N2 - Given a weighted graph, let W1, W2, W3,... denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree of weight W1 is at most k-1 edge swaps away from some spanning tree of weight Wk. Three other conjectures posed by Kano are proven for two special classes of graphs. Finally, we consider the algorithmic complexity of generating a spanning tree of weight Wk.

AB - Given a weighted graph, let W1, W2, W3,... denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree of weight W1 is at most k-1 edge swaps away from some spanning tree of weight Wk. Three other conjectures posed by Kano are proven for two special classes of graphs. Finally, we consider the algorithmic complexity of generating a spanning tree of weight Wk.

KW - AMS subject classification code (1991): 05C05, 05C85, 68R10

UR - https://www.scopus.com/pages/publications/0042876213

U2 - 10.1007/BF01305236

DO - 10.1007/BF01305236

M3 - Article

AN - SCOPUS:0042876213

SN - 0209-9683

VL - 12

SP - 433

EP - 447

JO - Combinatorica

JF - Combinatorica

IS - 4

ER -

On the spanning trees of weighted graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this