Combinatorical and Algebraic Structures Seminar
Session details
Date: | 6.1.2009 |
Speaker: | Angela Mestre, Doppler Institute |
Title: | On the vertex and edge reconstruction conjectures |
Abstract: | We review the well known vertex-reconstruction and edge-reconstruction conjectures due to S. Ulam and F. Harary, respectively. They state that every graph $G=(V,E)$ (resp. every simple graph $G=(V,E)$) with at least three vertices (resp. four edges) is uniquely constructed by the set of vertex-erased graphs $\{G-v: v \in V\}$ (resp. edge-erased graphs $\{G-e: e\in E\}$). Moreover, we express the multiplicities of the vertex-erased graphs $G-v$ (resp. edge erased-graphs $G-e$) in terms of the orders of the groups of automorphisms of the graphs $G$ and $G-v$ (resp. $G-e$), and give some examples. |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož