Open access peer-reviewed chapter - ONLINE FIRST

Reconstruction of Graphs

By Sivaramakrishnan Monikandan

Submitted: March 3rd 2021Reviewed: June 4th 2021Published: August 7th 2021

DOI: 10.5772/intechopen.98726

Downloaded: 47

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 Eand Fare two sets, each containing melements such that there is defined a distance function μfor every pair of distinct points, with values either 1or 2, and μpp=0. If, for every subset of n1points of E, there exists an isometric system of m1points of Fand the number of distinct subsets isometric to any given subset of m1points is the same in Eand in F,then does Eand Fisometric?

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 Gand Hbe graphs with VG=v1,v2,,vnand 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 cardof G. The collection of all cards of Gis called the deckof Gand 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 DGaccording to the number of isomorphic subgraphs that Gcontains. Therefore DGis 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 Hwith deck DH=DGis called a reconstructionof G. If every reconstruction of Gis isomorphic to G, then Gis said to be reconstructible. A graph that is not reconstructible is given by GK2because, if His the graph consisting of two isolated vertices, then clearly His a reconstruction of Gbut it is not isomorphic to G. A property pdefined on a class Fof graphs is called a recognizable propertyif pG=pHwhenever GFand His a reconstruction of G.A classCof graphs is said to be recognizableif for all graphs Gin C, any reconstruction of Gmust be in C. A parameterθ=θGis said to be reconstructibleif for all reconstructions Hof G, θH=θG. In other words θGis reconstructible if it can be determined uniquely from the deck of G.A classCof graphs is said to be reconstructibleif every graph in Cis reconstructible. A class Cof graphs is said to be weakly reconstructibleif for all graphs Gin C, any graph in Cthat is a reconstruction of Gis isomorphic to G.

Theorem 1.3.If Gis a pq-graph with p3, then pand qare reconstructible.

Proof.It is trivial to determine the number p, which is necessarily one greater than the order of any subgraph Gv. Also, pis 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 qidenote the size of Gi. Consider an arbitrary edge eof G, say e=vjvk. Then ebelongs to p2of the subgraphs Gi, namely all except Gjand Gk.

Hence,

i=1pqi

counts each edge p2times. That is,

i=1pqi=p2q

Therefore,

q=i=1pqip2

Corollary 1.4.Given a graph Gvin the deck of G=pq, the degree of vand the degrees of the neighbors of vin Gare reconstructible.

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

Let dbe the degree sequence of Gvbut with the degree of vinserted in its correct position. The nonzero entries of the vector difference ddoccur in positions corresponding to neighbors of vin 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 Gvshown in Figure 2 of some unspecified graph G. From these subgraphs we determine p,q, and degvifor 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 graphG.

Theorem 1.6.The connectivityκGof a graphGis reconstructible.

Proof.A graph Gis disconnected if and only if κG=0. If Gis connected and let κG= k1. Then there exists a set of k-vertices, say v1,v2,,vkin VGsuch that Gv1v2vkis disconnected and the removal of any set of fewer than k-vertices from Gdo not separable G.It follows that κGvi=k1for i=1,2,,kand κGvk1for 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, κGis reconstructible.

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

Proof.Let G¯v1G¯v2G¯vnbe the given deck of G¯.Then G¯v1¯G¯v1¯G¯vn¯=Gv1Gv2Gvn.Therefore, DGis known. Since Gis reconstructible, Gcan be obtained uniquely (up to isomorphism) from DGHence Gand 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 DGit can be determined whether Gis regular and if it is, its degree ris reconstructible.

Thus without loss of generality, we may assume that Gis an rregular graph with VG=v1,v2,,vp,p3. Take any Gviin the deck. The only way to reconstruct a regular graph of degree rfrom Gviis to add a new vertex vijoining it to all the vertices of degree d1in Gv. Hence Gis uniquely reconstructible.

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

Proof.Let Gbe a connected graph. By theorem Gcontains at least two vertices that are not cut-vertices. Let v1and v2be two vertices that are not cut-vertices. Then, clearly Gv1and Gv2are connected.

Conversely, assume that there exists vertices v1,v2VGsuch that both Gv1and Gv2are connected. Thus, in Gv1and also in G, vertex v2is connected to vi,i3. Moreover, v1is connected to each vi,i3in Gv2and thus in G. Hence every pair of vertices of Gare connected and so Gis connected.

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

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

Proof.We have already noted that disconnectedness in graphs of order at least 3is a recognizable property. Thus, we assume without loss of generality that Gis a disconnected graph with VG=v1,v2,vp,p3. Further, let Gi=Gvifor i=1,2,p. Hence, if Gcontains an isolated vertex, then Gis reconstructible. Assume that Ghas no isolated vertices. Among all the components of all the graphs in DG, let Cbe one with maximal number of vertices. Then Cmust be a component of G. Let v0be a vertex of Cthat is not a cut vertex. Consider all graphs in DGthat have the least number of components isomorphic to C. Among these, let Gvbe the one with the largest number of components isomorphic to C=v0. Then the only way to form Gfrom Gvis by replacing one component Cv0by C.

Theorem 1.12.Separable graphs Gwithout end vertices are reconstructible.

Proof.If the given deck of Gcontains two connectred cards and one disconnected cards, then Gmust 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 Gare identified as the the largest end blocks in all cards Gv.Let Bbe the one of the largest end blocks of Gand the unique cut vertex in Bis indicated in that card Gv.If any non-cut vertex wof Bis deleted from B,then new rooted blocks are produced. Suppose that among the blocks so produced B1is the largest, B2the next largest (or another largest) and so on. Among all such vertex-deletions Bw,some of them must produce a maximum number, say k1of B1‘s. Among all those vertex-deletions Bwproducing k1of B1‘s, some of them must produce a maximum number, say k2of B2‘s, and so forth.

Now consider a card Gushowing 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 Guwill 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 Dbe some smallest end block of G.Now choose a connected card Gvin which there is a smaller number of end blocks Dthan in G.Then Gvmust have resulted from deletion of a vertex from D.Since Ghas no end vertices, the leftovers Dvis a nontrivial subgraph of G.That leftovers can be identified by considering first the smallest connected subgraph, say Dof Gvcontaining all end blocks smaller than D.If Dhas D1vertices, it is the leftovers of D.Otherwise, add to Dthe (unique) block which joins it to the rest of G.Continue adding blocks in that way until the resulting subgraph B contains D1vertices. Then Gcan be recovered by replacing Bby D,using the same cut vertex of attachment. Hence Gis reconstructible.

Definition 1.13.For graphs Fand Gwe denote by sFGthe number of non-identical subgraphs F0of Gsuch that VF0VG,EF0EGand F0F.

In his thesis [1], Paul J. Kelly proved that for any two graphs Fand Gwith VF<VG,the number of subgraphs of Gisomorphic to Fis reconstructible from the deck of G.Greenwell extended this result as follows: Let Pdenote a graphical property. If Fis a subgraph of Ghaving property P, then the number of subgraphs of Gthat are isomorphic to Fand maximal with respect to property Pis reconstructible from the deck of G.

Theorem 1.14.(Kelly’s Lemma) Let Fand Gbe graphs of orders p1and prespectively, where p1<p. Then the number sFGis recognizable from the subgraphs Gv,vVG.

Proof.Each subgraph of Gisomorphic to Foccurs in exactly pp1subgraphs Gv,vVG. Therefore,

pp1sFG=vVGsFGv

Since the numerator of the right hand side of this equation is recognizable and pand p1are known, sFGis recognizable. Also,

sFG=vVGpp1

3. Counting theorem

Let Pdenote a graphical property (such as being connected, being n-connected for some n2or being planar, for example).Let Gbe a given graph, and let Fbe a graph such that Fhas property Pand FG, that is, sFG1. By an FGchain with respect toP,we mean a sequence of pairwise nonisomorphic subgraphs of Gsuch that each subgraph has property Pand

FF0F1F2FnG

where VF0VF1VFnVGand EF0EF1EFnEG.

The chain F0F1F2Fnis said to have length n. Two FGchains with respect to a property Pare called isomorphicif they have the same length and corresponding terms are isomorphic graphs. The rankof Fin G(with respect to P) is the maximum length among all FGchains with respect to P.

Let Fbe a subgraph of a graph Gsuch that Fhas a graphical property P. Then Fis said to be a maximal subgraph with respect toPif VFVGand EFEG, and if, whenever His a subgraph of Ghaving property Psuch that VFVHVGand EFEHEG, it follows that F=H. For example, if P1is the property of being connected, then a subgraph Fof a graph Gis a maximal subgraph with respect to P1if and only if Fis a component of G. If P2denotes the property of being a block, then Fis a maximal subgraph with respect to P2if and only if Fis a block of G.

Let Pdenote a graphical property and let Gbe a given graph. If Fis a subgraph of Ghaving property P, then by 54mPFGwe mean the number of subgraphs of Gthat are isomorphic to Fand maximal with respect to property P. For example, if P2denotes the property of being a block and FK3, then for the graph Gof Figure 3, it follows that sFG=6and mPFG=2.

Figure 3.

The number of subgraphs with a specific property.

Theorem 1.15.(Counting Theorem).Let Gbe a graph of order at least 3, and let Pbe a graphical property. Suppose that each subgraph of Gwith property Phas order less than of G. If for each subgraph Fof Gwith property Pand for each graph F0Fsuch that VF0VGand EF0EG, there is a unique subgraph Hof Gthat is maximal with respect to Psuch that VF0VHand EF0EH, then for each subgraph Fof Ghaving property P, the number mPFGis recognizable.

Proof.Let Fbe a subgraph of Gsuch that Fhas property P.

By hypothesis, the order of Fis less than the order of G. Denote the rank of Fin Gby r.

We show that

mPFG=n=0r1nsFF1sF1F2sFn1FnsFnGE1

where the inner sum is taken over all pairwise nonisomorphic FGchains F0F1Fnof 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 Gthat is isomorphic to Fis, in fact, a subgraph that is maximal with respect to P. Thus mPFG=sFGand (Eq. (1)) holds in the case where r=0. Let rbe a positive integer, and assume that (Eq. (1)) is true for all subgraphs Fof Gwith property Pand having rank less than r. Let Fbe a subgraph of Ghaving property Pand rank rin G. By hypothesis, for each graph F0Fsuch that VF0VGand EF0EG, there is a unique subgraph Hof Gthat is maximal with respect to Psuch that VF0VHand EF0EH. Thus, the number of subgraphs of Gisomorphic to Fthat are subgraphs of maximal subgraphs isomorphic to His given by sFH.mPHG. Hence, if we sum these numbers over all nonisomorphic subgraphs Hof Ghaving property P, then we obtain the total number of subgraphs of Gisomorphic to F. In symbols,

sFG=sFH.mPHG

where the sum is taken over all nonisomorphic subgraphs Hof Ghaving property P. Since sFH=1if HF, we have

mPFG=sFGHFsFH.mPHGE2

In (Eq. (2)) it suffices to consider only those subgraphs Hof Ghaving property Pfor which sFH>0. Since any such subgraph Hhas 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 H0H1Hmof Hof Ghaving property Psuch that sFH>0and 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 F0F1Fnof 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 Gbe a connected graph with two or more blocks. Then the blocks of Gare 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 Ghas two or more blocks if and only if Gvis disconnected for at least one vertex of G, that is, vis a cut-vertex of G. Thus let Gbe a connected graph with two or more blocks. Then each subgraph Fof Gthat is a block has order less than that of G. Furthermore, for each F0Fsuch that VF0VGand EF0EG, there is a unique subgraph Hof Gthat is maximal with respect to the property P2of being a block (that is, a unique block Hof G) such that VF0VHand EF0EH. Therefore by Theorem 1.15, the number mP2FGis the number of blocks of Gisomorphic to F.

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 vof a tree Gis called a peripheralif it is an end-vertex of a diametrical path of Gthat is peripheral if its eccentricity ev=diamG. By a branch of a central treewe mean a maximal subtree of Gin which the central vertex is an end vertex. A branch of a bicentral treeof Gis a maximal subtree of Gcontaining the central edge and in which the central edge is incident with an end vertex. A radial branchis a branch that contains a peripheral vertex of the tree. A tree is called basicif it has exactly two branches, exactly one of which is a path. The branch that is a path is called the stemof 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 Gcan be determined from its subgraphs Gv,vVG, it can be recognized whether a pqgraph Gis connected and q=p1, that is, it can be recognized whether Gis a tree. Therefore, we assume that Gis a tree. If no vertex of Ghas degree exceeding 2, then Gis a path. Hence, paths are reconstructible. Thus, we assume that Gis not a path.That is, Ghas vertices of degree 3or more. Then a diametrical path of such a tree Gnecessarily has order less than G. From Theorem 1.14, it follows that the number of paths of various lengths in Gis recognizable. This implies that the diameter is a recognizable parameter.

Since the diameter of a tree equals either 2ror 2r1according as the tree is central or bicentral, where ris the radius. It further follows that the radius is recognizable and whether Gis central or bicentral is recognizable. We have already mentioned that the number of diametrical paths in Grecognizable. Now, a vertex uis peripheralif and only if degGu=1and Guhas fewer paths of length diamGthan does G. Hence the number of peripheral vertices is recognizable.

A central tree Gwith central vertex vhas degGvbranches, 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 ris 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 1or Type 2and is 2r1if the subtree is of Type 3. The length aand bof the indicated paths satisfy 1ar1and 1br1. The lengths cand dsatisfy 1cr2and 1dr2. If a non-basic tree contains a subtree of Type 1, 2or 3as 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 Gis recognizable when Gitself is of Type 1,2or 3.

Figure 4.

Nonbasic trees.

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

Claim:1Basic trees are reconstructible.

Let Gbe a central basic tree, and consider those subgraphs Gvwhich are bicentral(basic) tree. For each such tree Gv, let mvdenote the least distance from a vertex of degree 3or more in Gvto a vertex incident with the central edge of Gv. Among all such numbers mv, let mv1be one of minimum value. By adding v1to Gv1and joining v1to the end-vertex of the stem of Gv1, the tree Gis obtained. Suppose that Gis a bicentral basic tree. Consider all those subgraphs Gvwhich are central(basic) trees. One of these trees, say Gvp, has a vertex of degree greater than 2closest to the central vertex. By adding vpto Gvpand joining vpto the end-vertex of the stem of Gvp, the tree Gis produced.

Claim:2Nonbasic trees are reconstructible.

Let Gbe a nonbasic tree. If Fis a subtree of Gthat is maximal with respect to the property Pof being a basic tree having the same diameter as G, then we call Fa maximal basic subtree of G. Clearly, every subtree of Gwith property Phas order less than that of Gand 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 Gisomorphic to a given basic subtree Fof Ghaving the same diameter as Gis recognizable.

We now determine the radial branches of G. If no subtree of Ghas property P, then each radial branch of Gis a path (of length radG) and the number of radial branches equals the number of peripheral vertices in G. If, on the other hand, Ghas basic subtrees with the same diameter as that of G, then Ghas radial branches that are not paths. In fact, every maximal basic subtree of Ggives rise to such a branch. Let H1,H2,,Htbe nonisomorphic subtrees of Gwith property Psuch that every maximal basic subtree Fof Gis isomorphic to some Hi, 1it, and such that mPHiG>0for i=1,2,,t. For convenience, let mi=mPHiG. For each i, 1it, consider a maximal basic subtree Fof Gthat is isomorphic to Hi. The tree Fhas one radial branch Bthat is not a path. If Ghas nperipheral vertices and Bcontains kiperipheral vertices (of Fand hence of G), then Bis the top of nkimaximal basic subtrees of Gisomorphic to Hi(namely, one for each of the nkistems produced from the other nkiperipheral vertices). Thus, the number miof maximal basic subtrees isomorphic to Hiequals inki, where iis the number of radial branches of Gisomorphic to B. Therefore, i=mi/nki, where mi, niand kiare recognizable. The number of radial branches of Gthat 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 Gis a central nonbasic tree. This can be accomplished though, by observing that, in this case, the nonradial branches of Gare the nonradial branches of Gv, where.

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

  2. vis a nonperipheral end vertex of a radial branch.

If no vertex vas described in iand iiexist, then all radial branches of Gare paths and the nonradical branches of Gare the nonradical branches of Gvwith the exception of with the exception of one path of length radG1, in Gv, where vis 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=Gvifor some graph Gwith VG=v1,v2,,v16.

Figure 5.

Deck of a tree.

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

We observe that Ghas vertices of degree exceeding 2(since, for example, G1does) so that Gis not a path. Hence a diametrical path of Ghas 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 2ror 2r1, where ris the radius of the tree, depending on whether the tree is central or bicentral, it follows that r=radG=3and that Gis a central tree.

In order to calculate the number nof 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 FP7and p1=7. We obtain

sP7G=vVGsP7Gv167=459=5

Thus a vertex v1of Gis a peripheral vertex if and only if Gv1is a tree and Gv1has fewer than five diametrical paths. The subgraphs G1,G2,G11,and G12satisfy these criteria so that the number nof peripheral vertices of Gis four.

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

Figure 6.

A type1subtree ofG.

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 Gthat is maximal with respect to the property Pof being a basic subtree of Gand having diameter 6), we begin by finding the maximal basic subtrees of G. By inspecting the graph, we see that only subtrees of Ghaving property Pare trees H1,H2and H3shown in Figure 7. Therefore every maximal basic subtree of Gis isomorphic to one of H1,H2and H3.

Figure 7.

The basic subtrees ofGhaving diameter6.

The number mPH1Gof maximal basic subtrees of Gisomorphic to H1can 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 sH1Gis the number of subtrees of Gisomorphic to H1. By using Kelly’s lemma with p1=9, we have

sH1G=vVGsH1Gv169=147=2.

Therefore there are two maximal basic subtrees of Gisomorphic to H1.

In order to compute mPH2G, we observe that, up to isomorphism, there are two H2Gchains, namely H2and H2H1, where H1is 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 H3and H3H1, where H1is 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=1and 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 Ghas exactly two maximal basic subtrees each of which is isomorphic to H1.

If His a maximal basic subtree of G, then HH1has one non-path radial branch B, and Bis isomorphic to the graph shown in Figure 8, where vcorresponds to the central vertex of G.

Figure 8.

The unique non-path radial branch ofG.

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

At this point we conclude that Gcontains exactly one radial branch that is not a path, namely B. All other radial branches of Gare necessarily paths. Since the branch Bcontains 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 Ghave thus been determined, as shown in Figure 9.

Figure 9.

The radial branches ofG.

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

Figure 10.

The treeGreconstructed.

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,F2and F3such that the reconstruction conjecture is true if it true for the families F1,F2and F3. These families are quite restrictive in that each has diameter two or three. First of all, it is proved that these families F1,F2and F3are 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 Ghas diameter greater than three then the diameter of G¯is less than three.

Proof.Let Gbe a connected with diameter greater than 3.

Then there exists u,vVGsuch that duv>3. Clearly the graph G¯will contain the edge uv. In G¯any vertex different from uand vis adjacent to uor to vor to both since there is no path of length 3connecting uand vin G.

Let xand ybe any two vertices different from uand v. If they have uor vas a common neighbor in G¯, then xuyor xvyis a path connecting them in G¯. Otherwise, they must be adjacent in G¯since neighbors of uand neighbors of vare not adjacent in G.

Now define.

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

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

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

For i0n2,pvHiis the number of pairs of non-adjacent vertices of Hsuch that, for each pair, there are exactly ipaths of length two between the two vertices, and pavHiis the number of pairs of adjacent vertices of Hsuch that, for each pair, there are exactly ipaths of length two between the two vertices.

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

Proof.If pvHn2>0or pavHn2>0,then Hmust contain at least one pair of vertices, say uv,such that there are n2paths of length two between uand v,which means vertices uand vare adjacent to all other remaining n2vertices of H.Hence, in H¯,no vertices other than uand vare adjacent to them. Therefore, in H¯,either uand vare 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 uvbe a pair of vertices in the graph Hsuch that duv=2and let there be exactly kpaths of length two uv1vuv2vuvkvbetween uand v. Then, both in Huand Hv,the pair uvwill not appear at all. In each of the kcards Hvi,where i=1,2,,k,this pair uvappears as having k1paths of length two. In the remaining nkcards, this pair will appear as having kpaths of length two.

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

Theorem 1.21.ParameterspvHiandpavHiare reconstructible for alli0n2.

Proof. First we prove that the parameters pvHiare reconstructible and that of pavHifollows 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 n2independent linear equations of n1parameters pvH0,pvH1,,pvHn3and pvHn2.

Case 1.Suppose pvHn2>0.

Now, by Theorem 1.19, H¯is disconnected. So H¯and hence His 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=0apart from the n1equations stated in Theorem 1.20(a). Now we have n1linearly independent equations with n1unknowns namely pvH0,pvH1,,pvHn3and 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 diamH1and pvH0=0, then diamH=2 since pvHi(where i0n2) is the number of pairs of non-adjacent vertices of Hsuch that, for each pair, there are exactly ipaths of length two between the two vertices. If pvH0>0, then diamH>2.

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

Theorem 1.23.Families C1,C2and C3are 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=1or not (as complete graphs are recognizable). If diamH1and pvH0=0, then diamH=2. If pvH0>0, then diamH>2. So we can recognize both Hand H¯whether they have diameter equal to one or two or greater than two. So, C1and C2are recognizable. We have, if diamH>2and diamH¯>2then diamH=3and diamH¯=3. Also, GC3if and only if diamH>2and diamH¯>2. Hence C3is also recognizable.

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

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

Theorem 1.25([11]). If a graph Hhas 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 Hwith diamH=2and all graphs Hwith diamH=diamH¯=3are reconstructible.

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

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

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

Lemma 1.28.Separable graphsHwith diamH=2 are reconstructible.

Proof.We know that, graphs Gwith diamH=2 are recognizable. A connected graph is separable if and only if one of its cards is disconnected. Now Hhas no non-end block, as otherwise Hhas diameter greater than 2. So all the blocks of Hare end-blocks. Hence Hhas only one cut vertex, say v. Since diamH=2, vmust be adjacent to all other vertices of H. Hence His 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 uas in (ii) of Definition 1.31 is guaranteed by the existence of a connected card obtained by deleting a p2vertex 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 Gbe a separable graph on p(12) vertices. If Ghas no end vertex then Gis reconstructible (by Theorem 1.12).

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

We have two subcases.

Case 1. The graph Ghas at least two end vertices.

NowG¯hasatleasttwop2vertices.E6

Let u1and u2be 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 Gis reconstructible by Theorem 1.31.

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

(ii) If yis adjacent to u1(say), then in G¯y, u2is adjacent to all the vertices hence no vertex other than u2can be a cut vertex of G¯y. Also if u2were a cut vertex of G¯y, then u1and all its p3neighbors in G¯yare confined to a single block with p2vertices and the only other vertex of G¯ymust be an end vertex adjacent to u2. Thus G¯has two end vertices, leading to a contradiction. Hence G¯yhas 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¯yand joining it to a p3-vertex).

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

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

Case 2.1. The vertices wand yare nonadjacent in G.

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

If degq=p3then FwK3(because Ghas only one end vertex). Consider a 2-vertex deleted card Gzwith exactly two end vertices (the deleted 2-vertex cannot be from Bwqas every 2-vertex in Bwqis adjacent to wand qso that no additional end vertex is created). Such a Gzwill have an automorphism that interchanges the two end vertices, interchanges the two bases and fixes all other vertices. Hence all augmentations of Gzby introducing a 2-vertex so that the resulting graph has only one end vertex and only one end-block isomorphic to K3are isomorphic.

If degqp3then degq<p3(because Fw3). Now in the cards Gvthat are connected and have at least one end vertex (cards for which the deleted vertex is not one of w,yand q), the vertices w,yand qare identifiable as the only cut vertex of degree p3,the only end vertex nonadjacent with wand the base of yrespectively. Among these cards Gv, if we choose one, say G1such that.

  1. wand qare in the same block, and.

  2. the block containing wand qhas maximum number of vertices,

then the non-end block of G1is Bwq. Hence Bwqis known with wand qlabeled.

The only end vertex-deleted card in the deck is Gyand its only cut vertex is w.Since Bwqis known with wand qlabeled, there is an isomorphism αfrom Bwqon to a block of Gysuch that αw=w. The graph Gαobtained from Gyby adding a vertex and joining it only with αqis 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 Gis known up to isomorphism.

Case 2.2. The vertices wand yare adjacent in G.

Now in G¯, wis the only end vertex and yis 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,2and 3are 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 Gbe 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 Gof types (a) and (b) below.

adiamG=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.

bdiamG>3.

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

Theorem 1.34.All graphs are reconstructible if and only if all 2-connected graphs Gsuch 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 Gbe a connected graph with radG3. Then radG¯2. If possible, let G¯have endvertices. Then Ghas an n2-vertex say v. Hence vis adjacent to all but one vertex, say vof G. Hence vis adjacent to at least one neighbor of vin G(as Gis 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 Gwith radG= 2 are reconstructible.

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

Now let radG3. Then radG¯2and 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 Gsuch that radG=2are 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 Gsuch 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.

DOWNLOAD FOR FREE

chapter PDF

© 2021 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Sivaramakrishnan Monikandan (August 7th 2021). Reconstruction of Graphs [Online First], IntechOpen, DOI: 10.5772/intechopen.98726. Available from:

chapter statistics

47total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us