TR-2001-05

An extension of a theorem of Henneberg and Laman (A revised version is available as TR-2002-05)

András Frank, László Szegő



Abstract

We give a constructive characterization of graphs which are the union of 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.


Keywords:
Graph, Constructive characterization, Rigidity, Packing and covering by trees


Bibtex entry:

@techreport{egres-01-05,
AUTHOR = {Frank, Andr{\'a}s and Szeg{\H o}, L{\'a}szl{\'o}},
TITLE = {An extension of a theorem of {H}enneberg and {L}aman (A revised version is available as TR-2002-05)},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2001},
NUMBER = {TR-2001-05}
}


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