On the Reconstruction Problem in Graph Theory

Citation

Lin, Hong-Chuan (1981) On the Reconstruction Problem in Graph Theory. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/13y7-7f13. https://resolver.caltech.edu/CaltechTHESIS:05082018-173157065

Abstract

The thesis consists of three chapters. The first chapter introduces the basic notions of graph theory and defines vertex-reconstruction and edge-reconstruction problem. The second chapter and third chapter are devoted to the edge-reconstruction of bi-degreed graphs and bipartite graphs respectively.

A bi-degreed graph G is a graph with two degrees d > δ. By elementary arguments we can assume d = δ + 1 and there are at least two vertices of degree δ. Call vertices of degree d "big" vertex and degree δ "small" vertex. Define "symmetric" path of length p S_p to be one with both ends small vertices and all other internal vertices big vertices; define "asymmetric" path of length p A_p to be one with one end a small vertex and all others big vertices. If s(G) is the minimum distance between two small vertices in G, we can show that s(G) is "independent" of G (i.e. it is edge-reconstructable), and that G has at most one nonisomorphic edge-reconstruction H. From this, the concept of "forced move" posed by Dr. Swart is obvious. Using the principle of forced move (and sometimes also "forced edge" posed by Dr. Swart as well), it's easy to derive a few interesting properties, like say G is edge-reconstructable if s(G) is even or if two S_s(G)'s intersect at an internal vertex, etc. Write s for s(G). When s is odd, consider the concept of s - n-chain, which is n S_s's following from end to end. We can show first s - 3-chain and then s - 2-chain cannot exist. Hence S_s's are disjoint. Think of S_s's as "lines" in some geometry. Define two more "distance" functions s₁ and s₂ such that s₁ "represents" the distance from a point to a line and s₂ means the distance between to "skew" lines. With the aid of forced move principle again, we can at last prove every bi-degreed graph with at least four edges is edge-reconstructable.

A bipartite graph G is a graph whose vertex set V is the disjoint union of two sets v₁ and v₂ such that every edge joins v₁ and v₂. By elementary reduction we can assume G to be connected. We define special chains inductively so that it starts at a vertex of minimum degree and always goes to a neighbor or minimum degree. Special chains will be the main tool to prove edge-reconstructability. By G's finiteness, we note they will "terminate" somewhere, and we have three types of termination for them. Let condition A•s be that degree sequence of special chain is edge-reconstructable, condition B_i's be that number of special chains is edge-reconstructable(and some more general variations); condition P's be that the "last vertices" of two special chains be not adjacent; we can prove that all A, B_i and P's should hold inductively in an interlocked way. (This is a big task). Then condition P's can be used to prove G's edge-reconstructability for all three types of termination. We can then prove every bipartite graph with at least four edges is edge-reconstructable.

Thesis Files