On the reconstruction of the degree sequence |
| |
Institution: | 1. LRI, Bât. 490, Université Paris-Sud 91405, Orsay cedex, France;2. Equipe Combinatoire, Université Pierre et Marie Curie, Paris, France;3. Lehrstuhl II fü Mathematik, RWTH-Aachen, 52056 Aachen, Germany |
| |
Abstract: | Harary's edge reconstruction conjecture states that a graph G=(V,E) with at least four edges is uniquely determined by the multiset of its edge-deleted subgraphs, i.e. the graphs of the form G−e for e∈E. It is well-known that this multiset uniquely determines the degree sequence of a graph with at least four edges. In this note we generalize this result by showing that the degree sequence of a graph with at least four edges is uniquely determined by the set of the degree sequences of its edge-deleted subgraphs with one well-described class of exceptions. Moreover, the multiset of the degree sequences of the edge-deleted subgraphs always allows one to reconstruct the degree sequence of the graph. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|