Some work towards the proof of the reconstruction conjecture

(1)

Some work towards the proof of the reconstruction conjecture

S.K. Gupta, Pankaj Mangal, Vineet Paliwal

Department of Computer Science, Indian Institute of Technology, Delhi, India Received 14 January 2002; received in revised form 19 March 2003; accepted 2 April 2003

Abstract

In this paper we de2ne 2ve families of simple graphs {fi,f2,f^,t^ and F=5) such that the reconstruction conjecture is true if reconstruction is proved for either the families $[,$2 m& % or the families F=3;F=4 and F=5. These families are quite restrictive in that each has diameter two or three. Then we prove that families F=1;F=2;F=3;F=4 and F=5 are recognizable by proving that graphs of diameter two and edge-minimal graphs of diameter two are recognizable. The reconstruction conjecture is thus reduced to showing weak reconstructibility for either of the two sets of families.

Keywords: Reconstruction conjecture; Diameter

We shall, for the most part, use the notation and terminology of Bondy and Murthy [1]. Graphs will be 2nite, simple and undirected with order greater than two. Given a graph G with vertex set V(G) = {v1^;v2^;:^::;vⁿ} where | V(G) | = n(> 2), G has edge set E(G) with | E ( G ) | = e. If u;,i)G V(G), we denote by d(vi;vj) the distance between vertices vi and vj in G. By diam(G), we mean the diameter of G. We de2ne the diameter of a disconnected graph as infinity. G denotes the complement of G. A subgraph of G obtained by deleting a vertex vi e V(G) together with its incident edges is referred to as a vertex-deleted subgraph and denoted by G — vi or Gⁱ. The deck of graph G is the family of (unlabelled) vertex-deleted subgraphs of G; these are cards of the deck. A reconstruction of a graph G is a graph H with the same deck as that of G.

A graph G is reconstructible if every reconstruction of G is isomorphic to G. A family f of graphs is recognizable if, for each graph G e f , every reconstruction of G is also in F=, and weakly reconstructible if, for each graph G e f , all reconstructions of G that are in F= are isomorphic to G. A family F= of graphs is reconstructible if, for any graph

(2)

292 S.K. Gupta et al. / Discrete Mathematics 272 (2003) 291-296

G is reconstructible (i.e. if f is both recognizable and weakly reconstructible).

A parameter p de2ned on graphs is reconstructible if, for any graph G, it takes the same value on every reconstruction of G. G is a vertex-minimal graph of diameter two if diam(G) = 2 and 3vf G V(G) such that diam(G — vi) > 2. G is a vertex-critical graph of diameter two if diam(G) = 2 and Vu, e V(G), diam(G — vi) > 2. An edge-deleted subgraph of a graph G is a subgraph G — eij obtained by deleting the edge eij s E(G).

G is an edge-minimal graph of diameter two if diam(G) = 2 and there exists at least one edge eⁱj &E(G), such that diam(G — eⁱj) > 2. G is a non-edge-minimal graph of diameter two if diam(G) = 2 and G is not an edge-minimal graph of diameter two.

The reconstruction conjecture (RC) states that every 2nite, simple, undirected graph with order greater than two is reconstructible [3]. The reader is referred to Bondy and Hemminger [3] and Nash-Williams [2] which are good surveys of the work done on the RC.

There is a fundamental lemma in RC due to Kelly [4].

Kelly's lemma. For any two graphs F and G such that | V(F) | < | V(G) |, the number s(F;G) of subgraphs of G isomorphic to F is reconstructible.

There is a well known theorem in Graph Theory (exercise 1.6.12, [1]).

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

The following two theorems are well known in RC:

Theorem 2. If a graph is reconstructible, then so is its complement [4].

Theorem 3. Disconnected graphs are reconstructible [3].

Now if we de2ne:

(1) F=1: family of graphs containing all graphs G such that diam(G) = 2 and diam(G@) = 2.

(2) F=²: family of graphs containing all graphs G such that diam(G) = 2 and diam(G@) > 2.

(3) F=³: family of graphs containing all graphs G such that diam(G) = 3 and diam(G@) = 3.

(4) F=⁴: family of graphs containing all edge-minimal graphs of diameter two.

(5) F=5: family of graphs containing all non-edge-minimal graphs of diameter two.

Then combining the fact that graphs of diameter one (i.e. complete graphs) are reconstructible with Theorems 12, we can say that the RC will be true if recon- struction will be proved for either the families F=1;F=2 a nd F=3 or families ^3,^4 and

(3)

F=5. In this article we will prove that graphs of diameter two are recognizable (The- orem 8) and using this we will show that each of these families is recognizable (Theorems 10, 12).

Definition 1. pv(G; i) (where z'e[0,n — 2]) is the number of pairs of non-adjacent vertices of G such that, for each pair, there are exactly i paths of length two between the two vertices.

Definition 2. pav(G^; i) (where i e [0^; n — 2]) is the number of pairs of adjacent vertices of G such that, for each pair, there are exactly i paths of length two between the two vertices.

In Theorem 6, we prove the reconstructibility of the above mentioned parameters.

The equations formed in Theorem 5 to reconstruct these parameters are based on ideas similar to those used in the proof of Kelly's lemma.

Theorem 4. Ifpv(G;n - 2) > 0 or pav(G;n - 2) > 0 then G is disconnected.

Proof. If pv(G^; n — 2) is greater than zero or pav(G^; n — 2) is greater than zero then there should be at least one pair of vertices (VI;VJ) (say) such that there are n — 2 paths of length two between vⁱ and vj. Hence vi and vj are adjacent to each of the remaining vertices of graph G. So in G there will be no edge going from the vertex set V1 = {vi^;vj} to the vertex set V2 = V(G) — V1. So, G is disconnected. • Theorem 5. (a) E?=i pv(G^{i ;}j)=(j+1)pv(G^;j + l ) + ( w - ( j + 2 ) ) p v ( G , j ) V / e [0,w-3],

(b) E?=i pav(Gi^;j) = (j + 1 )pav(G^;j + 1) + (n - (j + 2))pav(G^;j) V/ G [0^;n - 3].

Proof. (a) If {v1 ; v2} is a pair of vertices (as shown in Fig. 1) in the original graph such that d(v1 ; v2 )=2 and there are exactly k paths of length two (v1 v3v2; v1 v4v2... ,v\ ^+2^2) between v1 and v2, then in k cards this pair appears as having k—\ paths of length two (this is the case when any one of the k vertices to which both v1 and v2 are adjacent (v3;v4;:::;vk+1 or vk+2) is deleted from G), in two cards this pair will not appear at all (this is the case when either v1 or v2 is deleted) and in the remaining n — (k + 2) cards this pair will appear as having k paths of length two.

(b) The proof is similar to that of part (a). •

Theorem 6. (a) Parameters pv(G^; i) Vz e [0^;n — 2] are reconstructible.

(b) Parameters pav(G^;i) Vz e [0^;n - 2] are reconstructible.

Proof. (a) Given the deck of G, the L.H.S. of Theorem 5(a) is reconstructible for j G [0;n — 3]. So from Theorem 5(a) we have n — 2 independent linear equations of n — 1 parameters pv(G;0);pv(G; 1 ); : : : ; pv(G;n - 2).

Case 1: pv(G; n — 2) > 0. G is disconnected (from Theorem 4). So G is recon- structible (by Theorem 3). Therefore, G is reconstructible (by Theorem 2). As G is reconstructible, each parameter pv(G^; i) (where z'e [0^;n — 2]) is reconstructible.

(4)

Fig. 1.

Case 2: pv(G^; n — 2) = 0. In this case we have an additional linearly independent equation pv(G; n — 2) = 0 apart from the equations from Theorem 5(a). So now we have n — 1 linearly independent equations to 2nd out the values of n — 1 parameters pv(G^;0)^;pv(G^; 1 )^{; : : : ;}p v ( G , n - 2).

(b) The proof is similar to that of part (a). •

Theorem 7. The number of pairs of vertices of G such that distance between vertices of each pair is greater than two (or pv(G;0)) is reconstructible.

Proof. The proof follows directly from Theorem 6(a). • Theorem 8. Graphs of diameter two are recognizable.

Proof. We can recognize whether diam(G) = 1 or not (as complete graphs are recog- nizable). If diam(G) ^ 1 and pv(G^;0) = 0, then diam(G) = 2 (from De2nition 1). If pv(G^;0) > 0, then diam(G) > 2 (from De2nition 1). •

Theorem 9. Vertex-minimal graphs of diameter two and vertex-critical graphs of di- ameter two are recognizable.

Proof. Immediate from Theorem 8.

Theorem 10. Families F=1^;F=2 and F=3 are recognizable.

(5)

Proof. Given the deck of some graph G, G== {Gi | i G [1;n]}, we can get the deck of G@, (jj = {G, \ i G [1;n]}. So we can recognize both G and G whether they have diameter equal to one or two (by Theorem 8) or greater than two. So, F=1 and F=² are recognizable. Gef^ iL diam(G) > 2 and diam(G@) > 2 (as from Theorem 1, if diam(G) > 2 and diam(G@) > 2 then diam(G) = 3 and diam(G@) = 3). So, F=3 is also recognizable. •

Theorem 11. G is an edge-minimal graph of diameter two if diam(G) = 2 and pv(G^; 1) + p a v ( G , 0 ) > 0 .

Proof. If G is an edge-minimal graph of diameter two, then by de2nition, there is at least one edge ey(=(u;, Vj))eE(G) such that diam(G-e,y) > 2. Removing eij from G can aLect its diameter only in two possible cases.

Case 1: There is at least one vertex vk G V(G) — vi — vj 3 (vk;vj) ^ E(G) and vkvivj is the only path of length two from vk to vj in G or (vk,Vf) ^ E(G) and vkvjvi is the only path of length two from vk to vi in G. In this case pv(G; 1) > 0.

Case 2: There is no path of length two between vi and vj. In this case p a v ( G , 0 ) > 0 . D

Theorem 12. Families F=⁴ and F=⁵ are recognizable.

Proof. The proof follows immediately from Theorems 6, 8 and 11. •

In Conclusion, in some particular cases like if pv(G; 0) is either one or two, then we can say that diam(G) = 3 (because if diam(G) > 3 then there are at least three pairs of distinct vertices such that the distance between vertices is greater than two. So, in that case the value of pv(G; 0) will be at least three). Similarly, with some work we can show that diameter is reconstructible in some particular cases but to avoid complications, we have presented only the work which might be helpful in the proof of the RC. Now to prove the RC it is enough to prove weak reconstructibility for either the families F=1^;F=2^{a n}d F=3 or the families ^3,^4 and F=⁵.

In this article, to prove the recognizability of families ff\,tf2, $3,?4 and F=5, we have just used the parameters pv(G; 0), pv(G; 1) and pav(G; 0) while the reconstruction of parameters pv(G^;i) (i G [2^;n — 2]) and pav(G^;i) (i G [1^;n — 2]) is not used anywhere.

It is open to explore the dependencies of these parameters with some other graph parameters as it might be helpful in proving their reconstructibility.

It should be noted that the family of vertex-minimal graphs of diameter two (F=⁶) is a subfamily of F=4 (Let G e f j , then 3u,G V(G) such that diam(G — vi) > 2. Then there is a pair of non-adjacent vertices (vj;vk) in G such that vjvivk is the only path of length two between these vertices. So, pv(G^; 1) > 0 and G e f t (Theorem 11). Super- 2cially, one would expect that edge-minimal implies vertex-minimal, since we could remove either vertex of the edge. The 4-cycle demonstrates that, at least for graphs of diameter two, this is not the case, and that rf⁴ ^ F=⁶.) and family of vertex-critical graphs of diameter two (F=7) is a subfamily of $5. Also, from our Theorem 9, to prove

(6)

reconstructibility of F=6 or F=7, it remains to show their weak reconstructibility. There- fore, in short of proving weak reconstructibility of F=4, one can consider proving weak reconstructibility of F=6 or F=⁷ as a step towards the proof of the RC. In a similar way, short of proving weak reconstructibility of F=1 tf2, $•$, =4 or F=5, one can di- vide it further into some subfamilies (as per convenience) and can try to prove weak reconstructibility of those subfamilies after proving their recognition.

The authors are thankful to Prof. Amitabh Tripathi and Dinesh Kumar of Depart- ment of Mathematics at IIT-Delhi for their help and useful comments. The authors are grateful to Prof. P.K. Stockmeyer for helpful remarks. The authors are also grateful to the referees for their critical comments which have resulted in substantial improvement of this manuscript.

References

[1] J.A. Bondy, U.S.R. Murthy, Graph Theory with Applications, Elsevier, Amsterdam, 1976.

[2] C.St.J.A. Nash-Williams, The reconstruction problem, Selected Topics in Graph Theory, Academic Press, New York, 1979.

[3] J.A. Bondy, R.L. Hemminger, Graph reconstruction—a survey, J. Graph Theory 1 (1977) 227-268.

[4] P.J. Kelly, A congruence theorem for trees, Paci2c J. Math. 7 (1957) 961-968.