Citation
Lin, HongChuan (1981) On the Reconstruction Problem in Graph Theory. Dissertation (Ph.D.), California Institute of Technology. https://resolver.caltech.edu/CaltechTHESIS:05082018173157065
Abstract
The thesis consists of three chapters. The first chapter introduces the basic notions of graph theory and defines vertexreconstruction and edgereconstruction problem. The second chapter and third chapter are devoted to the edgereconstruction of bidegreed graphs and bipartite graphs respectively.
A bidegreed 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 edgereconstructable), and that G has at most one nonisomorphic edgereconstruction 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 edgereconstructable 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  nchain, which is n S_{s}'s following from end to end. We can show first s  3chain and then s  2chain cannot exist. Hence S_{s}'s are disjoint. Think of S_{s}'s as "lines" in some geometry. Define two more "distance" functions s_{1} and s_{2} such that s_{1} "represents" the distance from a point to a line and s_{2} means the distance between to "skew" lines. With the aid of forced move principle again, we can at last prove every bidegreed graph with at least four edges is edgereconstructable.
A bipartite graph G is a graph whose vertex set V is the disjoint union of two sets v_{1} and v_{2} such that every edge joins v_{1} and v_{2}. 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 edgereconstructability. 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 edgereconstructable, condition B_{i}'s be that number of special chains is edgereconstructable(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 edgereconstructability for all three types of termination. We can then prove every bipartite graph with at least four edges is edgereconstructable.
Item Type:  Thesis (Dissertation (Ph.D.)) 

Subject Keywords:  Mathematics 
Degree Grantor:  California Institute of Technology 
Division:  Physics, Mathematics and Astronomy 
Major Option:  Mathematics 
Thesis Availability:  Public (worldwide access) 
Research Advisor(s): 

Thesis Committee: 

Defense Date:  12 April 1981 
Record Number:  CaltechTHESIS:05082018173157065 
Persistent URL:  https://resolver.caltech.edu/CaltechTHESIS:05082018173157065 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  10865 
Collection:  CaltechTHESIS 
Deposited By:  Melissa Ray 
Deposited On:  09 May 2018 17:34 
Last Modified:  02 Dec 2020 01:14 
Thesis Files

PDF
 Final Version
See Usage Policy. 80MB 
Repository Staff Only: item control page