Open AccessAn Extension of a Theorem of Henneberg and Laman
Author(s) -
András Frank,
László Szegő
Publication year - 2001
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
DOI - 10.1007/3-540-45535-3_12
Subject(s) - constructive , characterization (materials science) , generalization , disjoint sets , discrete mathematics , extension (predicate logic) , mathematics , computer science , combinatorics , process (computing) , programming language , nanotechnology , mathematical analysis , materials science , operating system
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom