CaltechTHESIS
A Caltech Library Service

# 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 Sp to be one with both ends small vertices and all other internal vertices big vertices; define "asymmetric" path of length p Ap 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 Ss(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 Ss's following from end to end. We can show first s - 3-chain and then s - 2-chain cannot exist. Hence Ss's are disjoint. Think of Ss's as "lines" in some geometry. Define two more "distance" functions s1 and s2 such that s1 "represents" the distance from a point to a line and s2 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 v1 and v2 such that every edge joins v1 and v2. 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 Bi'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, Bi 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.

Item Type: Thesis (Dissertation (Ph.D.)) Mathematics California Institute of Technology Physics, Mathematics and Astronomy Mathematics Public (worldwide access) Hall, Marshall Dilworth, Robert P. (chair)DePrima, Charles R.Franklin, Joel N.Ryser, Herbert J.Hall, Marshall 12 April 1981 CaltechTHESIS:05082018-173157065 https://resolver.caltech.edu/CaltechTHESIS:05082018-173157065 10.7907/13y7-7f13 No commercial reproduction, distribution, display or performance rights in this work are provided. 10865 CaltechTHESIS Melissa Ray 09 May 2018 17:34 16 Apr 2021 22:22

## Thesis Files  Preview
PDF - Final Version
See Usage Policy.

80MB

Repository Staff Only: item control page