TR-2002-05

Constructive characterizations for packing and covering with trees (Revised version of TR-2001-05)

András Frank, László Szegő

Published in:
Discrete Applied Mathematics. 131 (2003) 347-371.



Abstract

We give a constructive characterization of undirected graphs which contain k spanning trees after adding any new edge. This is a generalization of a theorem of Henneberg and Laman who gave the characterization for k=2. We also give a constructive characterization of graphs which have k edge-disjoint spanning trees after deleting any edge of them.


Bibtex entry:

@techreport{egres-02-05,
AUTHOR = {Frank, Andr{\'a}s and Szeg{\H o}, L{\'a}szl{\'o}},
TITLE = {Constructive characterizations for packing and covering with trees (Revised version of TR-2001-05)},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-05}
}


Last modification: 5.6.2018. Please email your comments to Tamás Király!