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ő

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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2001},
NUMBER	=	{TR-2001-05}

}