On the construction problems in graph theory.

Abstract

One of the most difficult unsolved problems in graph theory is the Reconstruction Conjecture. Harary even referred to problems like the Four Colour Problem (now a theorem), the Hamiltonian Circuit Problem, and the Reconstruction Problem as Graphical Diseases, as they affected many researchers. The Reconstruction Conjecture was first proposed by Ulam and his doctoral student Kelly in 1941. It is defined as follows: Let GGG and HHH be two simple graphs with at least three vertices, and suppose they have the same multiset of unlabelled vertex-deleted subgraphs. Then the Reconstruction Conjecture states that the graphs GGG and HHH must be isomorphic. Harary popularized this problem and also posed related problems such as the Edge Reconstruction Conjecture (that every graph with at least four edges can be uniquely reconstructed from its multiset of edge-deleted subgraphs) and the Digraph Vertex Reconstruction Conjecture. After Stockmeyer discovered many infinite families of counterexamples for the digraph vertex reconstruction conjecture, it became known as the Digraph Reconstruction Problem. On the other hand, there has been no significant progress on the Vertex and Edge Reconstruction Conjectures. This dissertation is mainly concerned with the Edge Reconstruction Conjecture and related problems (e.g., Digraph Edge Reconstruction, Edge Reconstruction of a Set of Graphs, h-Edge Reconstruction, etc.), although Vertex Reconstruction Problems are also discussed in the last two chapters. One of the deepest known results on edge reconstruction problems is the Nash-Williams Theorem. Applications and generalizations of this theorem in various directions form a central theme of most parts of this dissertation. Contents of the Dissertation • Chapter 1: Definitions of different reconstruction problems and a survey of the literature. • Chapter 2: Several applications of the Nash-Williams Theorem. Five different classes of graphs - including p-claw-free graphs containing at least one chordless p-cycle, chordal graphs, and free graphs - are proved to be edge reconstructible. The results on p-claw-free and chordal graphs establish the edge reconstructibility of a class of graphs that includes claw-free graphs as a special case. The main techniques used to prove these results are the Nash-Williams Theorem and a method of constructing a sequence of possible reconstructions. We demonstrate that the Nash-Williams Theorem can also be used to tackle the problem of recognizing a class of graphs from the edge deck. It might be possible to extend our method to reconstruct a set of claw-free graphs and K1,rK_{1,r}K1,r-free graphs. Chapter 3 deals with the problem of constructing a set of graphs from the shuffled edge deck. Although this problem is interesting in its own right, we prove that a general solution to such a problem would fully solve the Vertex Reconstruction Conjecture. We prove the set edge reconstructibility of P-free graphs, and also study chordal graphs using a generalization of Nash-Williams’ Theorem for the set edge reconstruction problem, which is proved in Chapter 4. Chapter 4 is devoted to the study of Nash-Williams’ Theorem and its generalizations. We prove an exact analogue of Nash-Williams’ Theorem for graphs GGG and HHH with the same k-edge deleted subgraphs, but not identical (k?1)(k-1)(k?1)-edge deleted subgraphs. We also discuss the n-1 puzzle (analogous to the “15 puzzle”) as a simple example of Nash-Williams’ Theorem. We conjecture a Nash-Williams-type theorem for vertex reconstruction of simple graphs and directed graphs. Some examples are discussed to justify the expectation that this form of the theorem should hold for vertex problems. Using combinatorial arguments, we prove that if every edge has exactly one replacing edge, and every edge set of size two has exactly one replacing edge set, then all reconstructions of the graph are isomorphic to each other. We also prove that directed regular graphs are edge reconstructible. This result proves, as a special case, a result of Harary and Palmer that tournaments are edge reconstructible. Chapter 5 formulates all reconstruction problems as a problem of establishing a strong k-edge (or vertex) hypomorphism between two edge (or vertex) hypomorphic graphs GGG and HHH. A first step toward this goal leads to a stronger form of Kelly’s Lemma for the edge reconstruction problem, which states that we can construct not only the k-edge deleted subgraphs uniquely, but also establish a one-to-one and onto mapping between the k-edge subsets of the edge sets of GGG and HHH, such that a k-edge subset of GGG has the isomorphic line graph as the corresponding k-edge subset of HHH, and the corresponding k-edge deleted subgraphs also have isomorphic line graphs. We discuss the possibility of proving a very strong form of Nash-Williams’ Theorem which implies the edge reconstructibility of all graphs. The original theorem of Nash-Williams is a general property of a family of sets satisfying certain conditions. On the other hand, the expected form of Nash-Williams’ Theorem is also incorporated with the information that the sets in the family are edge hypomorphic graphs.