On the reconstruction of graph invariants |
| |
| Affiliation: | 1. Computer Laboratory, University of Cambridge, Cambridge, UK;2. Department of Computer Science, University College London, London, UK;1. Department of Mathematics, University of Isfahan, Isfahan 81746-73441, Iran;2. School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran;1. Mathematics Department, United States Naval Academy, Annapolis, MD, USA;2. Mathematics Department, Louisiana State University, Baton Rouge, LA, USA;3. Mathematical Sciences Department, University of Texas at Dallas, Dallas, TX, USA;1. Department of Mathematics, The George Washington University, Washington, D.C. 20052, USA;2. Department of Mathematics, United States Naval Academy, Annapolis, MD, 21402, USA;3. Department of Economics, Mathematics and Statistics, Birkbeck, University of London, London WC1E 7HX, United Kingdom |
| |
| Abstract: | The reconstruction conjecture has remained open for simple undirected graphs since it was suggested in 1941 by Kelly and Ulam. In an attempt to prove the conjecture, many graph invariants have been shown to be reconstructible from the vertex-deleted deck, and in particular, some prominent graph polynomials. Among these are the Tutte polynomial, the chromatic polynomial and the characteristic polynomial. We show that the interlace polynomial, the U-polynomial, the universal edge elimination polynomial ξ and the colored versions of the latter two are reconstructible.We also present a method of reconstructing boolean graph invariants, or in other words, proving recognizability of graph properties (of colored or uncolored graphs), using first order logic. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
