Open access peer-reviewed chapter

Reconstruction of Graphs

Written By

Sivaramakrishnan Monikandan

Reviewed: 04 June 2021 Published: 07 August 2021

DOI: 10.5772/intechopen.98726

From the Edited Volume

Recent Applications in Graph Theory

Edited by Harun Pirim

Chapter metrics overview

531 Chapter Downloads

View Full Metrics

Abstract

A graph is reconstructible if it is determined up to isomorphism from the collection of all its one-vertex deleted unlabeled subgraphs. One of the foremost unsolved problems in Graph Theory is the Reconstruction Conjecture, which asserts that every graph G on at least three vertices is reconstructible. In 1980’s, tremendous work was done and many significant results have been produced on the problem and its variations. During the last three decades, work on it has slowed down gradually. P. J. Kelly (1957) first noted that trees are reconstructible; but the proof is quite lengthy. A short proof, due to Greenwell and Hemminger (1973), was given which is based on a simple, but powerful, counting theorem. This chapter deals with the counting theorem and its subsequent applications; also it ends up with a reduction of the Reconstruction Conjecture using distance and connectedness, which may lead to the final solution of the conjecture.

Keywords

  • Reconstruction
  • Counting Theorem
  • Tree
  • Diameter
  • 2-connected

1. Introduction

Probably the foremost unsolved problem in Graph Theory is Ulam’s Conjecture. This problem is due to P.J. Kelly and S.M. Ulam. Kelly’s Ph.D thesis [1] written under S.M.Ulam in 1942 dealt with this. Ulam proposed it as a set theory problem in his famous book “A Collection of Mathematical Problems” [2].

This is how Ulam’s problem was originally stated [2]:

Suppose that E and F are two sets, each containing m elements such that there is defined a distance function μ for every pair of distinct points, with values either 1 or 2, and μpp=0. If, for every subset of n1 points of E, there exists an isometric system of m1 points of F and the number of distinct subsets isometric to any given subset of m1 points is the same in E and in F, then does E and F isometric?

There are many restatements of Ulam’s original conjecture, each dealing with another way of talking about sets. Kelly [3] has given the graph theoretic version of this problem as below and solved it for trees and disconnected graphs, and verified it for graphs on up to six vertices.

Theorem 1.1.(Ulam Conjecture).

Let G and H be graphs with VG=v1,v2,,vn and for n3. If GviHui, for all then GH.

Many graph theorists have found other ways to restate the Ulam Conjecture. But the current version of this problem, popularly known as the Reconstruction Conjecture is the one formulated by Frank Harary [4].

Theorem 1.2. (Reconstruction Conjecture).

Every graph on at least three vertices is uniquely determined up to isomorphism by the collection of its one vertex-deleted subgraphs.

Graphs obeying the above conjecture are said to be reconstructible. Many classes of graphs and some parameters of graphs are already proved to be reconstructible. The papers [5, 6] and the book [7] deal with earlier work done on this problem. P. J. Kelly first proved that trees are reconstructible; but the proof is quite lengthy. A short proof was given by Greenwell and Hemminger using a powerful but simple counting theorem. This chapter deals with the counting theorem and its subsequent applications; also it ends up with a reduction of the Reconstruction Conjecture using distance and connectedness, which may lead to the final solution of the conjecture.

Advertisement

2. Reconstructible parameters and graphs

A vertex-deleted subgraph of a graph G, is called a card of G. The collection of all cards of G is called the deck of G and is denoted by DG.

Note that the graphs in the deck are unlabelled and, if G contains isomorphic vertex-deleted subgraphs, then such subgraphs are repeated in DG according to the number of isomorphic subgraphs that G contains. Therefore DG is a multiset, rather than a set, of isomorphism type of graphs.

Figure 1 shows an example of a graph and its deck.

Figure 1.

Graph and its deck.

A graph H with deck DH=DG is called a reconstruction of G. If every reconstruction of G is isomorphic to G, then G is said to be reconstructible. A graph that is not reconstructible is given by GK2 because, if H is the graph consisting of two isolated vertices, then clearly H is a reconstruction of G but it is not isomorphic to G. A property p defined on a class F of graphs is called a recognizable property if pG=pH whenever GF and H is a reconstruction of G. A classC of graphs is said to be recognizable if for all graphs G in C, any reconstruction of G must be in C. A parameterθ=θG is said to be reconstructible if for all reconstructions H of G, θH=θG. In other words θG is reconstructible if it can be determined uniquely from the deck of G. A classC of graphs is said to be reconstructible if every graph in C is reconstructible. A class C of graphs is said to be weakly reconstructible if for all graphs G in C, any graph in C that is a reconstruction of G is isomorphic to G.

Theorem 1.3. If G is a pq-graph with p3, then p and q are reconstructible.

Proof. It is trivial to determine the number p, which is necessarily one greater than the order of any subgraph Gv. Also, p is equal to the number of subgraphs Gv. To determine q, label these subgraphs by Gi,i=1,2,p, and suppose GiGvi, where viVG. Let qi denote the size of Gi. Consider an arbitrary edge e of G, say e=vjvk. Then e belongs to p2 of the subgraphs Gi, namely all except Gj and Gk.

Hence,

i=1pqi

counts each edge p2 times. That is,

i=1pqi=p2q

Therefore,

q=i=1pqip2

Corollary 1.4. Given a graph Gv in the deck of G=pq, the degree of v and the degrees of the neighbors of v in G are reconstructible.

Proof. The degree of v in G is simply qEGv, and this is reconstructible since q is. Therefore d, the degree sequence in nondecreasing order of G, is reconstructible.

Let d be the degree sequence of Gv but with the degree of v inserted in its correct position. The nonzero entries of the vector difference dd occur in positions corresponding to neighbors of v in G, and their degrees can be read off from d.

Example 1.5. We illustrate Theorem 1.3 and Corollary 1.4 with the six subgraphs Gv shown in Figure 2 of some unspecified graph G. From these subgraphs we determine p,q, and degvi for i=1,2,...6. Clearly p=6. By calculating the qi,i=1,2,...6, we find that q=9. Thus, degv1=degv2=2,degv3=degv4=3, and degv5=degv6=4.

Figure 2.

Deck of the graph G.

Theorem 1.6.The connectivityκGof a graphGis reconstructible.

Proof. A graph G is disconnected if and only if κG=0. If G is connected and let κG = k1. Then there exists a set of k-vertices, say v1,v2,,vk in VG such that Gv1v2vk is disconnected and the removal of any set of fewer than k-vertices from G do not separable G. It follows that κGvi=k1 for i=1,2,,k and κGvk1 for vVG=v1v2vk. Hence for a connected graph G, κGminvVGκGv+1. Since the R.H.S. of the above equation is known from the deck of G, κG is reconstructible.

Theorem 1.7.If a graphGis reconstructible, then the complementG¯ofGis reconstructible.

Proof. Let G¯v1G¯v2G¯vn be the given deck of G¯. Then G¯v1¯G¯v1¯G¯vn¯=Gv1Gv2Gvn. Therefore, DG is known. Since G is reconstructible, G can be obtained uniquely (up to isomorphism) from DG Hence G and so G¯ is known. That is, G¯ is reconstructible.

Theorem 1.8. Regular graphs are reconstructible.

Proof. From the deck of G, the degree sequence is reconstructible. Therefore, from DG it can be determined whether G is regular and if it is, its degree r is reconstructible.

Thus without loss of generality, we may assume that G is an rregular graph with VG=v1,v2,,vp,p3. Take any Gvi in the deck. The only way to reconstruct a regular graph of degree r from Gvi is to add a new vertex vi joining it to all the vertices of degree d1 in Gv. Hence G is uniquely reconstructible.

Theorem 1.9. For graphs of order at least 3, connectedness is a recognizable property. In particular, if G is a graph with VG=v1,v2,,vp,p3, then G is connected if and only if at least two of the subgraphs Gvi are connected.

Proof. Let G be a connected graph. By theorem G contains at least two vertices that are not cut-vertices. Let v1 and v2 be two vertices that are not cut-vertices. Then, clearly Gv1 and Gv2 are connected.

Conversely, assume that there exists vertices v1,v2VG such that both Gv1 and Gv2 are connected. Thus, in Gv1 and also in G, vertex v2 is connected to vi,i3. Moreover, v1 is connected to each vi,i3 in Gv2 and thus in G. Hence every pair of vertices of G are connected and so G is connected.

Remark 1.10. Since connectedness is a recognizable property, it is possible to determine from the subgraphs Gv,vVG, whether a graph G of order at least 3 is disconnected.

Theorem 1.11. Disconnected graphs of order at least 3 are reconstructible.

Proof. We have already noted that disconnectedness in graphs of order at least 3 is a recognizable property. Thus, we assume without loss of generality that G is a disconnected graph with VG=v1,v2,vp,p3. Further, let Gi=Gvi for i=1,2,p. Hence, if G contains an isolated vertex, then G is reconstructible. Assume that G has no isolated vertices. Among all the components of all the graphs in DG, let C be one with maximal number of vertices. Then C must be a component of G. Let v0 be a vertex of C that is not a cut vertex. Consider all graphs in DG that have the least number of components isomorphic to C. Among these, let Gv be the one with the largest number of components isomorphic to C=v0. Then the only way to form G from Gv is by replacing one component Cv0 by C.

Theorem 1.12. Separable graphs G without end vertices are reconstructible.

Proof. If the given deck of G contains two connectred cards and one disconnected cards, then G must be connected and containing a cut vertex and so it separable. Therefore, since the degree sequence of a graph is reconstructible, the class of all separable graphs without end vertices is recognizable. Throughout this proof, blocks mean rooted blocks where roots are the cut vertices of the graph that are in the blocks. The largest end blocks of G are identified as the the largest end blocks in all cards Gv. Let B be the one of the largest end blocks of G and the unique cut vertex in B is indicated in that card Gv. If any non-cut vertex w of B is deleted from B, then new rooted blocks are produced. Suppose that among the blocks so produced B1 is the largest, B2 the next largest (or another largest) and so on. Among all such vertex-deletions Bw, some of them must produce a maximum number, say k1 of B1‘s. Among all those vertex-deletions Bw producing k1 of B1‘s, some of them must produce a maximum number, say k2 of B2‘s, and so forth.

Now consider a card Gu showing a minimum number of blocks B, and a maximum number of blocks B1, B2, and so forth (in that order), all with roots as marked. Then the card Gu will show all blocks of G, except for one B, plus k1B1‘s, k2B2‘s, and so forth. Thus we can find all end blocks of G, with cut vertices marked. Let D be some smallest end block of G. Now choose a connected card Gv in which there is a smaller number of end blocks D than in G. Then Gv must have resulted from deletion of a vertex from D. Since G has no end vertices, the leftovers Dv is a nontrivial subgraph of G. That leftovers can be identified by considering first the smallest connected subgraph, say D of Gv containing all end blocks smaller than D. If D has D1 vertices, it is the leftovers of D. Otherwise, add to D the (unique) block which joins it to the rest of G. Continue adding blocks in that way until the resulting subgraph B contains D1 vertices. Then G can be recovered by replacing B by D, using the same cut vertex of attachment. Hence G is reconstructible.

Definition 1.13. For graphs F and G we denote by sFG the number of non-identical subgraphs F0 of G such that VF0VG,EF0EG and F0F.

In his thesis [1], Paul J. Kelly proved that for any two graphs F and G with VF<VG, the number of subgraphs of G isomorphic to F is reconstructible from the deck of G. Greenwell extended this result as follows: Let P denote a graphical property. If F is a subgraph of G having property P, then the number of subgraphs of G that are isomorphic to F and maximal with respect to property P is reconstructible from the deck of G.

Theorem 1.14. (Kelly’s Lemma) Let F and G be graphs of orders p1 and p respectively, where p1<p. Then the number sFG is recognizable from the subgraphs Gv,vVG.

Proof. Each subgraph of G isomorphic to F occurs in exactly pp1 subgraphs Gv,vVG. Therefore,

pp1sFG=vVGsFGv

Since the numerator of the right hand side of this equation is recognizable and p and p1 are known, sFG is recognizable. Also,

sFG=vVGpp1
Advertisement

3. Counting theorem

Let P denote a graphical property (such as being connected, being n-connected for some n2 or being planar, for example).Let G be a given graph, and let F be a graph such that F has property P and FG, that is, sFG1. By an FGchain with respect toP,we mean a sequence of pairwise nonisomorphic subgraphs of G such that each subgraph has property P and

FF0F1F2FnG

where VF0VF1VFnVG and EF0EF1EFnEG.

The chain F0F1F2Fn is said to have length n. Two FGchains with respect to a property P are called isomorphic if they have the same length and corresponding terms are isomorphic graphs. The rank of F in G (with respect to P) is the maximum length among all FGchains with respect to P.

Let F be a subgraph of a graph G such that F has a graphical property P. Then F is said to be a maximal subgraph with respect toP if VFVG and EFEG, and if, whenever H is a subgraph of G having property P such that VFVHVG and EFEHEG, it follows that F=H. For example, if P1 is the property of being connected, then a subgraph F of a graph G is a maximal subgraph with respect to P1 if and only if F is a component of G. If P2 denotes the property of being a block, then F is a maximal subgraph with respect to P2 if and only if F is a block of G.

Let P denote a graphical property and let G be a given graph. If F is a subgraph of G having property P, then by 54mPFG we mean the number of subgraphs of G that are isomorphic to F and maximal with respect to property P. For example, if P2 denotes the property of being a block and FK3, then for the graph G of Figure 3, it follows that sFG=6 and mPFG=2.

Figure 3.

The number of subgraphs with a specific property.

Theorem 1.15.(Counting Theorem). Let G be a graph of order at least 3, and let P be a graphical property. Suppose that each subgraph of G with property P has order less than of G. If for each subgraph F of G with property P and for each graph F0F such that VF0VG and EF0EG, there is a unique subgraph H of G that is maximal with respect to P such that VF0VH and EF0EH, then for each subgraph F of G having property P, the number mPFG is recognizable.

Proof. Let F be a subgraph of G such that F has property P.

By hypothesis, the order of F is less than the order of G. Denote the rank of F in G by r.

We show that

mPFG=n=0r1nsFF1sF1F2sFn1FnsFnGE1

where the inner sum is taken over all pairwise nonisomorphic FGchains F0F1Fn of length n. (Note that all FGchains can be determined since each is contained in some Gv, vVG.)

We verify (Eq. (1)) by induction on r. If r=0, the only FGchain is the trivial F0, where F0F. This implies that each subgraph of G that is isomorphic to F is, in fact, a subgraph that is maximal with respect to P. Thus mPFG=sFG and (Eq. (1)) holds in the case where r=0. Let r be a positive integer, and assume that (Eq. (1)) is true for all subgraphs F of G with property P and having rank less than r. Let F be a subgraph of G having property P and rank r in G. By hypothesis, for each graph F0F such that VF0VG and EF0EG, there is a unique subgraph H of G that is maximal with respect to P such that VF0VH and EF0EH. Thus, the number of subgraphs of G isomorphic to F that are subgraphs of maximal subgraphs isomorphic to H is given by sFH.mPHG. Hence, if we sum these numbers over all nonisomorphic subgraphs H of G having property P, then we obtain the total number of subgraphs of G isomorphic to F. In symbols,

sFG=sFH.mPHG

where the sum is taken over all nonisomorphic subgraphs H of G having property P. Since sFH=1 if HF, we have

mPFG=sFGHFsFH.mPHGE2

In (Eq. (2)) it suffices to consider only those subgraphs H of G having property P for which sFH>0. Since any such subgraph H has rank less than r, the inductive hypothesis can be applied to each term mPHG, yielding

mPFG=sFGsFGm=0rankH1msHH1sH1H2sHmGE3

where the inner sum is taken over all pairwise nonisomorphic HG-chains H0H1Hm of H of G having property P such that sFH>0 and HF. Redistributing the summations in (Eq. (3)), we obtain

mPFG=sFGm=0rankH1msFHsHH1sHmG

or equivalently,

mPFG=n=0r1msFHsHH1sHmGE4

where the inner sum is over all pairwise nonisomorphic FGchains F0F1Fn of length n. However, this is precisely (Eq. (1)). By Theorem 1.14, the right side of (Eq. (4)) is recognizable. Thus the left hand side is recognizable.

Theorem 1.16. Let G be a connected graph with two or more blocks. Then the blocks of G are recognizable.

Proof. First observe that connected graphs with two or more blocks are recognizable. By Theorem 1.9 connectedness is a recognizable property. A connected graph G has two or more blocks if and only if Gv is disconnected for at least one vertex of G, that is, v is a cut-vertex of G. Thus let G be a connected graph with two or more blocks. Then each subgraph F of G that is a block has order less than that of G. Furthermore, for each F0F such that VF0VG and EF0EG, there is a unique subgraph H of G that is maximal with respect to the property P2 of being a block (that is, a unique block H of G) such that VF0VH and EF0EH. Therefore by Theorem 1.15, the number mP2FG is the number of blocks of G isomorphic to F.

Advertisement

4. Trees

Paul J. Kelly first proved that trees are reconstructible; but the proof was quite lengthy. Here we present a short proof due to Greenwell and Hemminger using the counting lemma.

A vertex v of a tree G is called a peripheral if it is an end-vertex of a diametrical path of G that is peripheral if its eccentricity ev=diamG. By a branch of a central tree we mean a maximal subtree of G in which the central vertex is an end vertex. A branch of a bicentral tree of G is a maximal subtree of G containing the central edge and in which the central edge is incident with an end vertex. A radial branch is a branch that contains a peripheral vertex of the tree. A tree is called basic if it has exactly two branches, exactly one of which is a path. The branch that is a path is called the stem of the basic tree; the other branch is called the top.

Theorem 1.17. Every tree of order at least 3 is reconstructible.

Proof. First we note that trees are recognizable. Since the order, size and connectedness of a graph G can be determined from its subgraphs Gv,vVG, it can be recognized whether a pq graph G is connected and q=p1, that is, it can be recognized whether G is a tree. Therefore, we assume that G is a tree. If no vertex of G has degree exceeding 2, then G is a path. Hence, paths are reconstructible. Thus, we assume that G is not a path.That is, G has vertices of degree 3 or more. Then a diametrical path of such a tree G necessarily has order less than G. From Theorem 1.14, it follows that the number of paths of various lengths in G is recognizable. This implies that the diameter is a recognizable parameter.

Since the diameter of a tree equals either 2r or 2r1 according as the tree is central or bicentral, where r is the radius. It further follows that the radius is recognizable and whether G is central or bicentral is recognizable. We have already mentioned that the number of diametrical paths in G recognizable. Now, a vertex u is peripheral if and only if degGu=1 and Gu has fewer paths of length diamG than does G. Hence the number of peripheral vertices is recognizable.

A central tree G with central vertex v has degGv branches, at least two of which are radial, while a bicentral tree has exactly two branches, both of which are radial. A tree (which is not a path) having radius r is basic if and only if it contains no subgraph of Type 1,2,or 3, as shown in Figure 4. The central vertices are drawn as solid circles. In each case, the indicated u-v path is a diametrical path of the original tree: its length is 2r if the subtree is of Type 1 or Type 2 and is 2r1 if the subtree is of Type 3. The length a and b of the indicated paths satisfy 1ar1 and 1br1. The lengths c and d satisfy 1cr2 and 1dr2. If a non-basic tree contains a subtree of Type 1, 2 or 3 as a proper subtree, then this is recognizable by Theorem 1.14. Thus, in order to show that all nonbasic trees are recognizable, we need only show that a non-basic tree G is recognizable when G itself is of Type 1,2 or 3.

Figure 4.

Nonbasic trees.

A tree G of order p is of Type 1 if and only if it contains a path of length 2r=p2, one 3vertex, and the only subgraph Gv with three components is isomorphic to 2PrK1. A tree G of order p is of Type 2 if and only if it contains a path of length 2r=p3, has exactly two 3vertices, and in the two subgraphs Gv with three components, the size of any component that is a path at most r2. Finally, a tree G of order p is of Type 3 if and only if it contains a path of length 2r1=p3, has exactly two 3vertices, and each subgraph Gv with three components is isomorphic to Pr+1Pr1K1 or in each such Gv, the size of any component that is a path at most r2. Thus nonbasic trees of Types 1,2 and 3 are recognizable. Since nonbasic trees are recognizable, basic trees are also recognizable.

Claim:1 Basic trees are reconstructible.

Let G be a central basic tree, and consider those subgraphs Gv which are bicentral(basic) tree. For each such tree Gv, let mv denote the least distance from a vertex of degree 3 or more in Gv to a vertex incident with the central edge of Gv. Among all such numbers mv, let mv1 be one of minimum value. By adding v1 to Gv1 and joining v1 to the end-vertex of the stem of Gv1, the tree G is obtained. Suppose that G is a bicentral basic tree. Consider all those subgraphs Gv which are central(basic) trees. One of these trees, say Gvp, has a vertex of degree greater than 2 closest to the central vertex. By adding vp to Gvp and joining vp to the end-vertex of the stem of Gvp, the tree G is produced.

Claim:2 Nonbasic trees are reconstructible.

Let G be a nonbasic tree. If F is a subtree of G that is maximal with respect to the property P of being a basic tree having the same diameter as G, then we call F a maximal basic subtree of G. Clearly, every subtree of G with property P has order less than that of G and is a subtree of a unique maximal basic subtree of G. So, if such subtrees exist, by Theorem 1.14, the number of maximal basic subtrees of G isomorphic to a given basic subtree F of G having the same diameter as G is recognizable.

We now determine the radial branches of G. If no subtree of G has property P, then each radial branch of G is a path (of length radG) and the number of radial branches equals the number of peripheral vertices in G. If, on the other hand, G has basic subtrees with the same diameter as that of G, then G has radial branches that are not paths. In fact, every maximal basic subtree of G gives rise to such a branch. Let H1,H2,,Ht be nonisomorphic subtrees of G with property P such that every maximal basic subtree F of G is isomorphic to some Hi, 1it, and such that mPHiG>0 for i=1,2,,t. For convenience, let mi=mPHiG. For each i, 1it, consider a maximal basic subtree F of G that is isomorphic to Hi. The tree F has one radial branch B that is not a path. If G has n peripheral vertices and B contains ki peripheral vertices (of F and hence of G), then B is the top of nki maximal basic subtrees of G isomorphic to Hi(namely, one for each of the nki stems produced from the other nki peripheral vertices). Thus, the number mi of maximal basic subtrees isomorphic to Hi equals inki, where i is the number of radial branches of G isomorphic to B. Therefore, i=mi/nki, where mi, ni and ki are recognizable. The number of radial branches of G that are paths equals ni=1tiki. Since bicentral nonbasic trees have only radial branches, it follows that such trees are reconstructible. However, we still construct any nonradial branches that may exist if G is a central nonbasic tree. This can be accomplished though, by observing that, in this case, the nonradial branches of G are the nonradial branches of Gv, where.

  1. v is a peripheral vertex of a radial branch containing at least two peripheral vertices,or.

  2. v is a nonperipheral end vertex of a radial branch.

If no vertex v as described in i and ii exist, then all radial branches of G are paths and the nonradical branches of G are the nonradical branches of Gv with the exception of with the exception of one path of length radG1, in Gv, where v is a peripheral vertex.

We now illustrate some of the ideas involved in the proof of Theorem 1.17 by considering the subgraphs of Figure 5, where Gi=Gvi for some graph G with VG=v1,v2,,v16.

Figure 5.

Deck of a tree.

Clearly, G has order p=16 and, by Theorem 1.3, size q=15. Since G1 and G2, for example, are connected it follows by Theorem 1.9 that G is connected. Therefore, we recognize G as a tree. Hence, by Theorem 1.17 that G is recognizable. Therefore, we now proceed to reconstruct G..

We observe that G has vertices of degree exceeding 2 (since, for example, G1 does) so that G is not a path. Hence a diametrical path of G has order less than that of G, so by determining the lengths of all paths in the subgraphs Gv, the maximum such length is the diameter of G. The maximum is 6 (which occurs in G1, for example) so that diamG=6. Since the diameter of a tree is either 2r or 2r1, where r is the radius of the tree, depending on whether the tree is central or bicentral, it follows that r=radG=3 and that G is a central tree.

In order to calculate the number n of peripheral vertices of G, we first calculate the number of diametrical paths. This can be done with the aid of Kelly’s Lemma, in which FP7 and p1=7. We obtain

sP7G=vVGsP7Gv167=459=5

Thus a vertex v1 of G is a peripheral vertex if and only if Gv1 is a tree and Gv1 has fewer than five diametrical paths. The subgraphs G1,G2,G11, and G12 satisfy these criteria so that the number n of peripheral vertices of G is four.

We next determine whether G is a basic or nonbasic (central) tree. Observe that the Type 1 tree of Figure 6 is a subtree of at least one subgraph Gv (in fact, T is a subtree of all Gi,i6). Therefore T is a proper subtree of G and G is nonbasic.

Figure 6.

A type 1 subtree of G.

We now determine the radial branches of G. Since every radial branch that is not a path is the top of some maximal basic subtree of G (that is, a subtree of G that is maximal with respect to the property P of being a basic subtree of G and having diameter 6), we begin by finding the maximal basic subtrees of G. By inspecting the graph, we see that only subtrees of G having property P are trees H1,H2 and H3 shown in Figure 7. Therefore every maximal basic subtree of G is isomorphic to one of H1,H2 and H3.

Figure 7.

The basic subtrees of G having diameter 6.

The number mPH1G of maximal basic subtrees of G isomorphic to H1 can be computed with the aid of (Eq. (1)) of Theorem 1.15. By investigating the subgraphs, we see that there is only one H1Gchain (up to isomorphism), namely the trivial chain H1. Thus by (Eq. (1)), mPH1G=1sH1G, where sH1G is the number of subtrees of G isomorphic to H1. By using Kelly’s lemma with p1=9, we have

sH1G=vVGsH1Gv169=147=2.

Therefore there are two maximal basic subtrees of G isomorphic to H1.

In order to compute mPH2G, we observe that, up to isomorphism, there are two H2Gchains, namely H2 and H2H1, where H1 is shown in Figure 7. By (Eq. (1)),

mPH2G=10sH2G+11sH2H1sH1G.

Again using Kelly’s Lemma, we have

sH2G=vVGsH2Gv168=328=4

One observes that sH2H1=2. Also we have already seen that sH1G=2. So mPH2G=42.2=0. Therefore there are no maximal basic subtrees of G isomorphic to H2.

In order to compute mPH3G, we observe that, up to isomorphism, there are two H3Gchains, namely H3 and H3H1, where H1 is shown in Figure 7. By (Eq. (1)),

mPH3G=10sH3G+11sH3H1sH1G.

Again using Kelly’s Lemma, we have

sH3G=vVGsH3Gv168=168=2

One observes that sH3H1=1 and we have already seen that sH1G=2. So mPH3G=22.1=0. Therefore there are no maximal basic subtrees of G isomorphic to H3.

Thus G has exactly two maximal basic subtrees each of which is isomorphic to H1.

If H is a maximal basic subtree of G, then HH1 has one non-path radial branch B, and B is isomorphic to the graph shown in Figure 8, where v corresponds to the central vertex of G.

Figure 8.

The unique non-path radial branch of G.

Since B contains two of the four peripheral vertices of G, each radial branch isomorphic to B is the top of 42=2 maximal basic subtrees isomorphic to H1. Thus the number of radial branches isomorphic to B equals 1, since mPH1G=2.

At this point we conclude that G contains exactly one radial branch that is not a path, namely B. All other radial branches of G are necessarily paths. Since the branch B contains two of the four peripheral vertices possessed by G. It follows that each of the remaining two peripheral vertices corresponds to a radial branch that is a path. All radial branches of G have thus been determined, as shown in Figure 9.

Figure 9.

The radial branches of G.

Since the tree constructed thus far has order 12 and G has order 16, G contains nonradial branches. These can be determined by noticing that G1, for example, is obtained by the deletion of a peripheral vertex of G belonging to the radial branch B. Since B is isomorphic to the graph shown in Figure 9 and contains more than one peripheral vertex of G, the nonradial branches of G1 are precisely the nonradial branches of G. Combining this observation with our information in Figure 9, we have constructed the tree G shown in Figure 10.

Figure 10.

The tree G reconstructed.

Advertisement

5. Diameter two or three

In 2003, S. K. Gupta [8] defined three families of simple graphs of diameter two or three and proved that the reconstruction conjecture is true if reconstruction is proved for either these three families. Already the digraph reconstruction conjecture was disproved [9]. So the proof of the reconstruction conjecture depends on any property on graphs that does not hold for digraphs. Since the diameter is one such property of graphs, graph theorists thought that the final proof of the reconstruction conjecture may hold in this line of direction. Gupta’s reduction of the reconstruction conjecture is presented next.

Gupta defined three disjoint families of simple graphs, namely F1,F2 and F3 such that the reconstruction conjecture is true if it true for the families F1,F2 and F3. These families are quite restrictive in that each has diameter two or three. First of all, it is proved that these families F1,F2 and F3 are recognizable by showing that graphs of diameter two are recognizable. The reconstruction conjecture is thus reduced to showing weak reconstructibility for the three families.

Theorem 1.18. If a graph G has diameter greater than three then the diameter of G¯ is less than three.

Proof. Let G be a connected with diameter greater than 3.

Then there exists u,vVG such that duv>3. Clearly the graph G¯ will contain the edge uv. In G¯ any vertex different from u and v is adjacent to u or to v or to both since there is no path of length 3 connecting u and v in G.

Let x and y be any two vertices different from u and v. If they have u or v as a common neighbor in G¯, then xuy or xvy is a path connecting them in G¯. Otherwise, they must be adjacent in G¯ since neighbors of u and neighbors of v are not adjacent in G.

Now define.

  1. C1: class of all graphs H such that diamH=diamH¯=2.

  2. C2: class of all graphs H such that diamH=2 and diamH¯>2.

  3. C3: class of all graphs H such that diamH=diamH¯=3.

For i0n2,pvHi is the number of pairs of non-adjacent vertices of H such that, for each pair, there are exactly i paths of length two between the two vertices, and pavHi is the number of pairs of adjacent vertices of H such that, for each pair, there are exactly i paths of length two between the two vertices.

Theorem 1.19. If pvHn2>0 or pavHn2>0 then H¯ is disconnected.

Proof. If pvHn2>0 or pavHn2>0, then H must contain at least one pair of vertices, say uv, such that there are n2 paths of length two between u and v, which means vertices u and v are adjacent to all other remaining n2 vertices of H. Hence, in H¯, no vertices other than u and v are adjacent to them. Therefore, in H¯, either u and v are isolated vertices or they together form a component isomorphic to K2. Thus, H¯ is disconnected.

Theorem 1.20.

ai=1npvHij=j+1pvHj+1+nj+2pvHjj0n3
bi=1npavHij=j+1pavHj+1+nj+2pavHjj0n3

Proof. (a) Let uv be a pair of vertices in the graph H such that duv=2 and let there be exactly k paths of length two uv1vuv2vuvkv between u and v. Then, both in Hu and Hv, the pair uv will not appear at all. In each of the k cards Hvi, where i=1,2,,k, this pair uv appears as having k1 paths of length two. In the remaining nk cards, this pair will appear as having k paths of length two.

(b) Proof is similar to Part(a) but taking uv as a pair of adjacent vertices.

Theorem 1.21.ParameterspvHiandpavHiare reconstructible for alli0n2.

Proof. First we prove that the parameters pvHi are reconstructible and that of pavHi follows similarly.

From the given deck of H, the left hand side of Theorem 1.20(a) is known for j0n3. Thus, from Theorem 1.20(a), we have n2 independent linear equations of n1 parameters pvH0,pvH1,,pvHn3 and pvHn2.

Case 1. Suppose pvHn2>0.

Now, by Theorem 1.19, H¯ is disconnected. So H¯ and hence H is reconstructible. Then each parameter pvHi (where i0n2) is clearly reconstructible.

Case 2: Suppose pvHn2=0.

In this case, we have an additional linearly independent equation pvHn2=0 apart from the n1 equations stated in Theorem 1.20(a). Now we have n1 linearly independent equations with n1 unknowns namely pvH0,pvH1,,pvHn3 and pvHn2. The unique solution set of these equations will provide the values of the parameters pvH0,pvH1,,pvHn2.

Theorem 1.22.Graphs of diameter two are recognizable.

Proof. Graphs of diameter one are precisely complete graphs and so they are recognizable. If diamH1 and pvH0= 0, then diamH= 2 since pvHi (where i0n2) is the number of pairs of non-adjacent vertices of H such that, for each pair, there are exactly i paths of length two between the two vertices. If pvH0> 0, then diamH>2.

The number of pairs of vertices of H such that distance between vertices of each pair is greater than two (or pvH0) is reconstructible.

Theorem 1.23. Families C1,C2 and C3 are recognizable.

Proof. Given the deck of some graph H, H=Hii1n, we can get the deck of H¯, H=Hi¯i1n. We can recognize whether diamH=1 or not (as complete graphs are recognizable). If diamH1 and pvH0=0, then diamH=2. If pvH0>0, then diamH>2. So we can recognize both H and H¯ whether they have diameter equal to one or two or greater than two. So, C1 and C2 are recognizable. We have, if diamH>2 and diamH¯>2 then diamH=3 and diamH¯=3. Also, GC3 if and only if diamH>2 and diamH¯>2. Hence C3 is also recognizable.

The next well known result is useful while proving the reduction of the Reconstruction Conjecture.

Theorem 1.24 ([10]). If a graph H has diameter greater than three then the diameter of H¯ is less than three.

Theorem 1.25 ([11]). If a graph H has radius greater than three then the radius of H¯ is less than three.

Theorem 1.26 (Gupta et al. [8]). The Reconstruction Conjecture is true if and only if all graphs H with diamH=2 and all graphs H with diamH=diamH¯=3 are reconstructible.

Proof. The necessity is obvious. For sufficiency, let H be a graph. If H is disconnected, then it is reconstructible. So, we can take that H is connected. If diamH=2 or diamH=diamH¯=3, then H is reconstructible by hypothesis. Hence we may assume that diamH=1 or, by Theorem 1.24, diamH¯2. If diamH=1 or diamH¯=1, then H is reconstructible (because graphs with diameter one are precisely complete graphs). Hence we assume diamH¯=2. Now H¯ is reconstructible by assumption. Hence H is reconstructible by Theorem 1.7.

Theorem 1.27.Graphs onnvertices having ann1-vertex are reconstructible.

Proof. Since the degree sequence of H is reconstructible, we can recognizable whether the graph has a vertex of degree n1 or not. Therefore the claim of under consideration is recognizable, weakly reconstructible. In a card Hv, where degHv = n1, annexing a new vertex to Hv and joining it all the vertices of Hv; the graph H in this way is unique. Hence H is reconstructible.

Lemma 1.28.Separable graphsHwith diamH=2 are reconstructible.

Proof. We know that, graphs G with diamH=2 are recognizable. A connected graph is separable if and only if one of its cards is disconnected. Now H has no non-end block, as otherwise H has diameter greater than 2. So all the blocks of H are end-blocks. Hence H has only one cut vertex, say v. Since diamH=2, v must be adjacent to all other vertices of H. Hence H is reconstructible.

Yang Yongzhi [2] proved the following reduction of the Reconstruction Conjecture in 1988. Yongzhi achieved this significant reduction of the RC by proving the reconstructibility of a new class of graphs called P-graphs. Yongzhi observed that reconstructibility of P-graphs turns out to be of great use while shuttling between a graph and its complement in order to reconstruct it.

Figure 11.

A P-graph on 9 vertices.

Definition 1.29.A graphGwithpvertices is aP-graph, if.

  1. there exists only two blocks inGand one of them is an edge (denote it byrxwithdx=1),and

  2. there exists a vertexur,du=p2 (Figure 11).

Lemma 1.30.P-graphs are recognizable.

Proof. Since the degree sequence and the number of cut vertices are reconstructible, recognizability of (i) of Definition 1.31 follows immediately. Existence of u as in (ii) of Definition 1.31 is guaranteed by the existence of a connected card obtained by deleting a p2 vertex in the given deck of G..

Every graph must be contained in one of the following disjoint classes of graphs: disconnected graphs (which are reconstructible); separable graphs without end vertices (which are reconstructible); separable graphs with end vertices; and 2-connected graphs. Yongzhi [12] further divided the class of separable graphs with end vertices into P-graphs and other than P-graphs, and proved that the former class of graphs is reconstructible if all 2-connected graphs are reconstructible. We omit the proof as it is very lengthy.

Theorem 1.31. P-graphs are reconstructible if all 2-connected graphs are reconstructible.

Theorem 1.32. Every connected graph is reconstructible if and only if every 2-connected graph is reconstructible.

Proof. The necessity is obvious. For proving the sufficiency part, assume that all 2-connected graphs are reconstructible. Let G be a separable graph on p (12) vertices. If G has no end vertex then G is reconstructible (by Theorem 1.12).

Thus,wecanassume thatGhasanendvertex andap2vertexbecause of Theorems1.12and1.7and the hypothesis.E5

We have two subcases.

Case 1. The graph G has at least two end vertices.

NowG¯hasatleasttwop2vertices.E6

Let u1 and u2 be two p2-vertices in G¯. By (Eq. (6)), G¯ has at most two end vertices and (Eq. (5)) now gives that G¯ has either one or two end vertices.

Case 1.1. The graph G¯ has exactly one end vertex, say y..

Now G¯ is a P-graph (as in (i) and (ii) below) and hence G is reconstructible by Theorem 1.31.

(i) If y is not adjacent to ui,i=1,2, then in G¯y, u1 and u2 are p2-vertices and hence G¯y is a block as G¯y has only p?1 vertices. Hence G¯ is a P-graph.

(ii) If y is adjacent to u1 (say), then in G¯y, u2 is adjacent to all the vertices hence no vertex other than u2 can be a cut vertex of G¯y. Also if u2 were a cut vertex of G¯y, then u1 and all its p3 neighbors in G¯y are confined to a single block with p2 vertices and the only other vertex of G¯y must be an end vertex adjacent to u2. Thus G¯ has two end vertices, leading to a contradiction. Hence G¯y has no cut vertex and G¯ is a P-graph.

Case 1.2. The graph G¯ has exactly two endvertices.

Now the bases of the two endvertices in G¯ are different (otherwise G¯ has at most one p2-vertices, contradicting (Eq. (6))). No vertex other than the bases of the endvertices can have degree p2. Hence G¯ has at most two p2-vertices and (Eq. (6)) now gives that has exactly two p2-vertices, which are the bases of the endvertices. In this case G¯ is clearly recognizable from its degree sequence and is reconstructible by augmenting an end vertex-deleted card G¯y (by adding a vertex to G¯y and joining it to a p3-vertex).

Case 2. The graph G has exactly one end vertex, say y.

If G has more than one p2-vertex, then G is a P-graph and hence is reconstructible by Theorem 1.31. Hence let G have exactly one p2-vertex, say w

Case 2.1. The vertices w and y are nonadjacent in G.

Now we can assume that w is a cut vertex of G as otherwise G is a P-graph and hence is reconstructible. So w and q (the base of y) are the only cut vertices of G. Hence G is the union of three subgraphs Bwq (the non-end block containing w and q), Fw (the union of end-blocks containing w) and the end-block By (K2) containing y.

If degq=p3 then FwK3 (because G has only one end vertex). Consider a 2-vertex deleted card Gz with exactly two end vertices (the deleted 2-vertex cannot be from Bwq as every 2-vertex in Bwq is adjacent to w and q so that no additional end vertex is created). Such a Gz will have an automorphism that interchanges the two end vertices, interchanges the two bases and fixes all other vertices. Hence all augmentations of Gz by introducing a 2-vertex so that the resulting graph has only one end vertex and only one end-block isomorphic to K3 are isomorphic.

If degqp3 then degq<p3 (because Fw3). Now in the cards Gv that are connected and have at least one end vertex (cards for which the deleted vertex is not one of w,y and q), the vertices w,y and q are identifiable as the only cut vertex of degree p3, the only end vertex nonadjacent with w and the base of y respectively. Among these cards Gv, if we choose one, say G1 such that.

  1. w and q are in the same block, and.

  2. the block containing w and q has maximum number of vertices,

then the non-end block of G1 is Bwq. Hence Bwq is known with w and q labeled.

The only end vertex-deleted card in the deck is Gy and its only cut vertex is w. Since Bwq is known with w and q labeled, there is an isomorphism α from Bwq on to a block of Gy such that αw=w. The graph Gα obtained from Gy by adding a vertex and joining it only with αq is a candidate for G. If β is another such isomorphism and Gβ is the corresponding augmented graph, then GαGβ under the mapping ψ where

ψ=βα1onthe vertices ofαBwqαβ1onthe vertices ofβBwqidentityonallother verticeswhenαBwqandβBwqaredifferent blocks ofGyandψ=βα1onthe vertices ofαBwqidentityonallother verticeswhenαBwqandβBwqaredifferent blocks ofGy.

Hence G is known up to isomorphism.

Case 2.2. The vertices w and y are adjacent in G.

Now in G¯, w is the only end vertex and y is the only p2-vertex and they are not adjacent. Hence G¯ is reconstructible as in Case 2.1. This completes the proof.

“Reconstruction Conjecture for digraphs” is already disproved by Stockmeyer [9]. So a proof for the Reconstruction Conjecture will depend on some property for graphs which does not extend to digraphs. Such properties are called significant properties (from the reconstruction angle) by Stockmeyer. One such property which arises out of distance in complement is given by Theorems 1.7 and 1.24. So far, in digraphs, there is no definition of complement and diameter such that Theorem 1.7 and 1.24 are simultaneously true. So reductions of the Reconstruction Conjecture obtained using the above theorems apply only for graphs and deserve attention. One reduction was proved in the last chapter (Theorem 1.26) by Gupta et al. [8] using Theorems 1.7 and 1.24. Reconstructibility of the subfamilies of 2-connected graphs in the families 1,2 and 3 are sufficient for the truth of the Reconstruction Conjecture.

Theorem 1.33 ([13]).All 2-connected graphs are reconstructible if and only if all 2-connected graphsGsuch that diamG=2 or diamG= diamG¯=3 are reconstructible.

Proof. The necessity is obvious. For sufficiency, let G be a 2-connected graph. Since graphs of diameter one are precisely complete graphs, this, together with hypothesis, leaves us to reconstruct only 2-connected graphs G of types (a) and (b) below.

a diamG=3 but diamG¯ is different from 3.

If diamG¯>3, then by Theorem 1.24, diamG<3, giving a contradiction. Hence diamG¯=2. Hence G¯ is reconstructible, by Lemma 1.28 if it is separable and by hypothesis otherwise.

b diamG>3.

Now, by Theorem 1.24, diamG¯<3 and so diamG¯=2, since G is connected. Therefore G¯ and hence G is reconstructible by hypothesis.

Theorem 1.34. All graphs are reconstructible if and only if all 2-connected graphs G such that diamG=2 or diamG = diamG¯ = 3 are reconstructible.

Proof. Follows by Theorems 1.32 and 1.33.

Advertisement

6. Radius two

Theorem 1.35.IfGis connected and radG3, then radG¯2andG¯has no endvertices.

Proof. Let G be a connected graph with radG3. Then radG¯2. If possible, let G¯ have endvertices. Then G has an n2-vertex say v. Hence v is adjacent to all but one vertex, say v of G. Hence v is adjacent to at least one neighbor of v in G (as G is connected). Hence dvw2,wVG. Hence radG2, giving a contradiction. This completes the proof.

Theorem 1.36. All 2-connected graphs are reconstructible if and only if all 2-connected graphs G with radG = 2 are reconstructible.

Proof. The necessity is obvious. For sufficiency, let G be any 2-connected graph. It is enough to show that G or G¯ is reconstructible. If radG=1, then G has a vertex adjacent to all other vertices and hence G is reconstructible. If radG=2, then G is reconstructible by hypothesis.

Now let radG3. Then radG¯2 and G¯ has no endvertices by Theorem 1.35. If radG¯=1, then G¯ is reconstructible as it has a vertex adjacent to all other vertices. When radG¯=2, G¯ is disconnected, separable without end vertices or 2-connected. Therefore G¯ is reconstructible by Theorem 1.11, Theorem 1.28 or the hypothesis.

Theorem 1.37 ([13]). All graphs are reconstructible if and only if all 2-connected graphs G such that radG=2 are reconstructible.

Proof. By Theorem 1.32, we have all graphs are reconstructible if and only if all 2-connected graphs are reconstructible. We also know that all 2-connected graphs are reconstructible if and only if all 2-connected graphs G such that radG = 2.

As 2-connected graphs are recognizable, the families of 2-connected graphs in the hypothesis of Theorems 1.34 and 1.37 are recognizable. Thus, to settle the Reconstruction Conjecture, it is enough to prove that neither of these two families contains a pair of non-isomorphic graphs having the same deck. However, radius of a graph is not yet proved to be reconstructible.

Many classes of blocks which are cartesian, lexicographic or strong products of graphs have been shown to be weakly reconstructible [6, 7]. Several other families of graphs already proved to be reconstructible contain 2-connected graphs. As there are a number of results on the structure of special classes of graphs of diameter 2, they may lead to the reconstruction of more classes of graphs and further narrow down the classes of graphs to be reconstructed to prove the Reconstruction Conjecture. These narrowed down classes must contain counterexamples to the Reconstruction Conjecture if at all there exists one.

References

  1. 1. P. J. Kelly, On Isometric Transformations, Ph.D. Thesis, University of Wisconsin, 1942
  2. 2. S. M. Ulam, A collection of mathematical problems, Wiley Interscience, New York (1960) p. 29
  3. 3. P.J. Kelly, A congruence theorem for trees, Pacific J. Math. 7 (1957) 961-968
  4. 4. F. Harary, On the reconstruction of a graph from a collection of subgraphs, in: Theory of Graphs and its Applications (M.Fieldler, ed.) Prague, 1964. 47-52; reprinted, Academic Press, New York, 1964
  5. 5. J. A. Bondy and R. L. Hemminger, Graph reconstruction - a survey, J. Graph Theory 1 (1977) 227–268
  6. 6. J. A. Bondy, A graph reconstructor’s manual, in Surveys in Combinatorics (Proceedings of the 13th British Combinatorics Conference) London Math. Soc., Lecture Note Ser. 166 (1991) 221–252
  7. 7. J. Lauri and R. Scapellato, Topics in Graph Automorphisms and Reconstruction, London Math. Soc. Student Texts 54, 2003
  8. 8. S. K. Gupta, P. Mangal and V. Paliwal, Some work towards the proof of the reconstruction conjecture, Discrete Math. 272 (2003) 291–296
  9. 9. P. K. Stockmeyer, The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1 (1977) 19-25
  10. 10. F.Harary and R.W. Robinson, The diameter of a graph and its complement, American Math. Monthly, 92 (1985), 211-212
  11. 11. D.B.West, Introduction to Graph Theory, Second Edition, Prentice-Hall, Inc. 2005
  12. 12. Y. Yongzhi, The Reconstruction Conjecture is true if all 2-connected graphs are reconstructible, J. Graph. Theory, 12 (2) (1988), 237-243
  13. 13. S. Ramachandran and S. Monikandan, Graph reconstruction conjecture: Reductions using complement, connectivity and distance, Bull. Inst. Combin. Appl. 56 (2009) 103–108

Written By

Sivaramakrishnan Monikandan

Reviewed: 04 June 2021 Published: 07 August 2021