In this thesis, we investigate the contraction reconstruction conjecture. It states that all simple graphs with at least four edges are reconstructible, that is they are uniquely determined from their collection of single edge contraction minors, called the deck. Similar questions have been studied in the past, the vertex reconstruction conjecture being the most famous.
There are usually two steps to show that a class of graph is reconstructible. The first one is to show that the class is recognizable, meaning that it is possible to determine if a graph G belongs to that class by looking at its deck. In order to recognize some classes of graphs, we show that a wide range of graph properties are reconstructible. We investigate the connectivity of graphs, which is useful to recognize disconnected, separable, and 2-connected graphs. We also show that the number of cycles of various lengths, the degree sequence, the number of spanning trees, the planarity, the presence of cliques of various sizes, and the diameter are reconstructible. Knowing the lengths of cycles allows us to recognize the class of bipartite graphs, while knowing the degree sequence allows us to recognize regular graphs.
The second step in showing that a class of graph is reconstructible is called weak reconstruction. We say that a class of graph is weakly reconstructible if no two graphs in that class share the same deck. A class of graphs that is both weakly reconstructible and recognizable is reconstructible. In this thesis, we show that disconnected graphs, bipartite graphs, most separable graphs and most 2-edge connected graphs are reconstructible. We also show that distance regular graphs and some cubic graphs are reconstructible. We quickly delve into the theory of probabilities to give a proof that almost all graphs are reconstructible.
Finally, the relation between edge contraction and graph automorphisms is studied. We study the automorphism group of a graph in relation to those of its cards. We also study the concept of contraction pseudo-similarity. Two edges are contraction pseudo-similar if they are not similar, but their contractions yield isomorphic graphs. We completely characterize the graphs that contain contraction pseudo-similar edges.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/38239 |
| Date | 04 October 2018 |
| Creators | Poirier, Antoine |
| Contributors | Newman, Mike |
| Publisher | Université d'Ottawa / University of Ottawa |
| Source Sets | Université d’Ottawa |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
Page generated in 0.0188 seconds