# A Note on the Adversary Degree Associated Reconstruction Number of Graphs

Authors: S. Monikandan; S. Sundar Raj; C. Jayasekaran; A. P. Santhakumaran
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

A vertex-deleted subgraph of a graphG is called a card of G. A card of G with which the degree of the deleted vertex is also given is called a degree associated card (or dacard) of G. The degree associated reconstruction number drn (G) of a graph G is the size of the smallest collection of dacards of G that uniquely determines G. The adversary degree associated reconstruction number of a graphG, adrn(G), is the minimum number k such that every collection of k dacards of G that uniquely determines G. In this paper, we show that adrn of wheels and complete bipartite graphs on at least 4 vertices is 2 or 3.


---

## Body

## 1. Introduction

All graphs considered are simple, finite, and undirected. We will mostly follow the standard graph theoretic terminology of [1]. A vertex-deleted subgraph or cardG-v of a graph G is the unlabeled graph obtained from G by deleting the vertex v and all edges incident with v. The ordered pair (d(v),G-v) is called a degree associated card or dacard of the graph G where d(v) is the degree of v in G. The deck (dadeck) of a graph G is its collection of cards (dacards). Ulam's Conjecture [2], also called Reconstruction Conjecture (RC), asserts that every graph on at least three vertices is determined uniquely (up to isomorphism) by its deck. Graphs that obey RC are called reconstructible.For a reconstructible graphG, Harary and Plantholt [3] have defined the reconstruction numberrn(G) to be the size of the smallest subcollection of the deck of G which is not contained in the deck of any other graph H; H≇G. Myrvold [4] referred to this number as ally-reconstruction number of G. Myrvold [5] also studied adversary reconstruction number of G which is the smallest k such that no subcollection of the deck of G of size k is contained in the deck of any other graph H;  H≇G.An extension of RC to digraphs, theDigraph Reconstruction Conjecture, was disproved when Stockmeyer exhibited [6] several infinite families of counter-examples. In view of this, Ramachandran [7] studied the degree (degree triple) associated reconstruction of graphs (digraphs). For a vertex v of a digraph, the ordered triple (r,s,t) is called the degree triple of v where r, s, and t are, respectively, the number of unpaired outarcs, unpaired inarcs, and symmetric pairs of arcs incident with v. A graph (digraph) is called degree associated reconstructible if it can be determined uniquely from its dadeck. For a degree associated reconstructible graph (digraph) G, the degree (degree triple) associated reconstruction number, drn(G), of G is the size of the smallest subcollection of the dadeck of G which is not contained in the dadeck of any other graph (digraph) H;  H≇G. Barrus and West [8] have shown that drn(G)=2 for all caterpillars except stars and one 6-vertex example, and that drn(G)≥3 for all vertex-transitive graphs G (not complete or edgeless).The following weakening of the reconstruction problem has also been considered by Harary and Plantholt [3]. A graph G, in a given class of graphs 𝒞, is called class-reconstructible if whenever H∈𝒞 has the same deck as G, then G≅H. If a graph is degree associated reconstructible then it is class-reconstructible, and vice-versa, where the class is the class of graphs with a given number m of edges.In this paper, we study the parameteradversary degree associated reconstruction number adrn(G) of a graph G. For a reconstructible graph G from its dadeck, adrn(G) is the minimum number k such that every collection of k dacards of G is not contained in the dadeck of any other graph H;  H≇G. From their definitions, it is clear that drn(G)≤adrn(G) for any graph G; the equality holds for vertex-transitive graphs (where all the dacards are necessarily identical). In this paper, we show that adrn is 2 or 3 for wheels and complete bipartite graphs on at least 4 vertices.


## 2.adrn of Standard Graphs

Sincedrn(G) and adrn(G) are exactly equal for any vertex-transitive graph G, the next theorem follows from [7].Theorem 1.
(i)adrn(Kn)=1.
(ii)adrn(Kn,n)=3 for n>1.
(iii)adrn(Cn)=3 for n≥4, where Cn is a cycle on n vertices.It is clear, from the definition ofadrn, that adrn(Kn)=adrn(K¯n)=1. In fact, it is true that the adrn of the complement of a graph is equal to the adrn of the graph.Lemma 2.
For any graphG, adrn(G¯)=adrn(G)≥drn(G).Proof.
The latter inequality follows immediately from the definitions ofdrn and adrn. To prove the first equality, let G be a graph of order n; let adrn(G)=s. Then, there exists a graph H(≇G) such that G and H have s-1 dacards in common. If (di,Gi) is a dacard of G, then (n-1-di,G¯i) is a dacard of G¯ and vice-versa. The graph H¯(≇G¯) has therefore s-1 dacards in common with those of G¯. Consequently, we have adrn(G¯)≥s.
On the other hand, ifadrn(G¯)>s, then there exists a graph T(≇G¯) such that T has s dacards of G¯. It follows that the graph T¯(≇G) has s dacards of G. Therefore, adrn(G)>s, giving a contradiction. Hence, adrn(G¯)=s=adrn(G).Anextension of a dacard (d(v),G-v) of G is a graph obtained from the dacard by adding a new vertex x and joining it with d(v) vertices of the dacard, and it is denoted by H(d(v),G-v) (or simply by H). Throughout this paper, H and x are used in the sense of this definition.For a graphG, to prove adrn(G)=k, we proceed as follows.   (i)
First, find the dadeck ofG.(ii)
Determine next all possible extensions of every dacard ofG.(iii)
Finally, show that every extension other thanG has at most k-1 dacards in common with those of G, and that at least one extension has precisely k-1 dacards in common with those of G.A vertex of degreem is called an m-vertex. We call a neighbour of degree r of a vertex v by an r-neighbour of v. The unionG∪H of graphs G and H is the graph with vertex set V(G)∪V(H) and edge set E(G)∪E(H). The join G+H of disjoint graphs G and H is the graph obtained from G∪H by joining each vertex of G to each vertex of H.Remark 3.
Note that if a dacard of a graphG is vertex-transitive and the degree associated with the dacard is one or else the degree associated with the dacard equals the number of vertices in the dacard, then the dacard has a unique extension (up to isomorphism), and, hence, drn(G)=1.Since the wheelWn on n(≥4) vertices has an (n-1)-vertex, the dacard (obtained by deleting the (n-1)-vertex of Wn) has a unique extension, and so drn(Wn)=1 by Remark 3. We now show that adrn(Wn)=3 for n>4.Theorem 4.
IfWn is a wheel on n(≥4) vertices, then
(1)adrn(Wn)={1,ifn=4,3,otherwise.Proof.
The dadeck ofWn=K1+Cn-1 consists of one copy of the dacard (n-1,Cn-1) and n-1 copies of the dacard (3,K1+Pn-2), where v is a vertex of Cn-1. Let H(3,K1+Pn-2) be an extension of the dacard (3,K1+Pn-2). We consider four cases depending on the value of n.
Case  1. n=4. Now, all the four dacards are isomorphic and they are (3,C3). Since it has a unique extension, it follows that adrn(W4)=1.
Case  2. n=5. In the dacard (3,K1+P3), there are two 2-vertices and two 3-vertices. If we join the newly added vertex x to the two 2-vertices and a 3-vertex, then the extension H is isomorphic to Wn. Therefore, we join the newly added vertex x to a 2-vertex and the two 3-vertices. The extension H so has one 2-vertex, two 3-vertices, and two 4-vertices (Figure 1). The dacard of the extension H corresponding to each of the two 3-vertices is (3,K1+P3). The extension H has thus only two dacards in common to those of Wn, and, hence, adrn(W5)=3.
Case  3. n=6. In the dacard (3,K1+P4), there are exactly two 2-vertices, one 4-vertex, and two 3-vertices.
Case  3.1. Join x to none of the two 2-vertices.
The extensionH has one vertex of degree 3, two vertices of degree 2, two vertices of degree 4, and one vertex of degree 5 (Figure 2). The dacard corresponding to the 3-vertex of the extension H is clearly in common with that of Wn. The dacard of H obtained by deleting the 5-vertex has endvertices, and, hence, it is not a dacard of Wn. The extension H has thus only one dacard in common with that of Wn.
Case  3.2. Join x to one 2-vertex and two 3-vertices.
The extensionH has two vertices of degree 3, one vertex of degree 2, and three vertices of degree 4. The dacard corresponding to each of the two 3-vertices is a dacard of Wn. The extension H has thus only two dacards in common with those of Wn.
Case  3.3. Join x to one 2-vertex (say y), one 3-vertex (say z), and the unique 4-vertex.
Case  3.3.1. Vertices y and z are nonadjacent.
InH, y is a 3-vertex and z is a 4-vertex. The dacards of H corresponding to x and the 3-vertex other than y are dacards of Wn. The dacard corresponding to y of H is not a dacard of Wn, since the subgraph of H obtained by deleting y has three 2-vertices. The dacard corresponding to the 5-vertex of H is not a dacard of Wn. The extension H has thus only two dacards in common with those of Wn.
Case  3.3.2. Vertices y and z are adjacent.
The dacards corresponding to the 3-verticesx and y in H are dacards of Wn. The dacard corresponding to the other 3-vertex is not a dacard of Wn, since the 3-vertex is adjacent to a 2-vertex in H. Also in H, the 5-vertex is adjacent to a 2-vertex, and so the dacard corresponding to the 5-vertex is not a dacard of Wn. The extension H has thus only two dacards in common with those of Wn.
Case  3.4. Join x to two 2-vertices and a 3-vertex or 4-vertex (say y).
Ify is the 4-vertex, then H is isomorphic to Wn. Otherwise, H has four 3-vertices and two 4-vertices. The dacards of H corresponding to x and the 3-vertex z not adjacent to y are dacards of Wn. But the dacard obtained from H by deleting a 3-vertex other than x and z has no 4-vertex, and so it is not a dacard of Wn. Thus, H has only two dacards in common with those of Wn.
Case  4. n≥7. The dacard (3,K1+Pn-2) has two vertices of degree 2, n-4 (≥3) vertices of degree 3, and one vertex of degree n-2 (≥5). If the newly added vertex x is not joined to the (n-2)-vertex, then the extension H cannot have more than one dacard in common with that of Wn. If x is joined to the (n-2)-vertex and the two 2-vertices, then H is isomorphic to Wn. Therefore, it is enough to consider the case in which x is joined to the (n-2)-vertex and not joined to at least one 2-vertex.
Case  4.1. Join x to the (n-2)-vertex, one 2-vertex, and one 3-vertex.
The extensionH has one 2-vertex, n-3 vertices of degree 3, one vertex of degree 4, and one vertex of degree n-1. The dacard (3,K1+Pn-2) cannot have a vertex of degree 4. Therefore, only dacards corresponding to the 3-neighbours of the 4-vertex in H can be isomorphic to the dacard (3,K1+Pn-2).
If the 4-vertex is adjacent to the 2-vertex inH, then there are two 3-vertices adjacent to the 4-vertex. The extension H therefore can have at most two dacards in common with those of Wn, and the dacard, corresponding to each of the two 3-vertices adjacent to the 4-vertex, is a dacard of Wn. Otherwise, the 3-neighbour closest to the 2-vertex yields a dacard with a cut vertex, while no dacard of Wn has a cut vertex.
Case  4.2. Join x to the (n-2)-vertex and two 3-vertices.
The extensionH has two vertices of degree 2, n-5 (≥2) vertices of degree 3, two vertices of degree 4, and one vertex of degree n-1. The dacard (3,K1+Pn-2) cannot have a vertex of degree 4. Therefore, only dacards corresponding to the 3-vertices which are common neighbours of the two 4-vertices can be isomorphic to the dacard (3,K1+Pn-2). In the extension H, there are at most two 3-vertices which are the common neighbours of the two 4-vertices. Thus, the extension H has at most two dacards in common with those of Wn, which completes the proof.Figure 1
The extensionH in Case  2.Figure 2
The extensionH in Case  3.1.From Remark3, it follows that drn(K1,n)=1. But adrn(K1,n) can be greater than one for n≥3 by the next theorem.Theorem 5.
Forn≥1(2)adrn(K1,n)={1,ifn≤2,3,ifn=3,2,ifn>3.Proof.
The dadeck ofK1,n consists of one copy of (n,K¯n) and n copies of (1,K1,n-1). The extension H(n,K¯n) is clearly isomorphic to K1,n. Consider the extension H(1,K1,n-1). If we join the newly added vertex x to the (n-1)-vertex of the dacard (1,K1,n-1), then the extension H is isomorphic to K1,n. We join therefore the vertex x to any one of the endvertices of the dacard. For n=2, the extension H is isomorphic to K1,n, and, hence, adrn(K1,2)=1. For n=3, the extension H is isomorphic to P4. The dadeck of P4 consists of 2 copies of K1,2 and 2 copies of K1∪K2. The extension H therefore has exactly two dacards in common with those of K1,n and adrn(K1,3)=3. Now, let us assume that n≥4. Then, in the extension H, there is exactly one 2-vertex which is adjacent to the newly added endvertex and a unique (n-1)-vertex. Since there is no 2-vertex in K1,n-1 for n≥4, only the dacard corresponding to the 1-neighbour of the 2-vertex in the extension H can be a dacard of K1,n. Hence, adrn(K1,n)=2.Ramachandran [7] proved that drn(Km,n)=2 for 2≤m<n. We shall show that adrn of Km,n is not always two.Theorem 6.
For2≤m<n,
(3)adrn(Km,n)={3,ifm=n-2,2,otherwise.Proof.
The dadeck ofKm,n consists of m copies of (n,Km-1,n) and n copies of (m,Km,n-1). To get an extension H having at least one dacard in common with that of Km,n, augment the dacard (n,Km-1,n) or (m,Km,n-1) by adding a new vertex x and joining it to precisely n or m vertices, respectively, in the dacard.
Case  1. Augmenting the dacard (n,Km-1,n).
Let(A,B) be the bipartition of the dacard Km-1,n, where |A|=m-1. Then, if we join x to every vertex of B, then H≅Km,n. We join x therefore to at least one vertex of A. If we join x to all the m-1 vertices of A, then no vertex other than x can have degree n in H. The extension H therefore has only one dacard isomorphic to (n,Km-1,n). In this extension, the vertices have degrees m-1,m,n, and n+1 only. The degrees of the vertices in the dacard corresponding to an m-vertex of the extension H are m-1, m,n-1 and n where m-1<m≤n-1<n. The dacard (m,Km,n-1) is therefore not a dacard of the extension H. Thus, H has only one dacard in common with that of Km,n. If at least one vertex of A is not joined to x, then in H, there are vertices of degrees m-1,m,n, and n+1. This extension clearly has a dacard (n,Km-1,n) (dacard corresponding to the vertex x). The degrees of the vertices in the dacard corresponding to an n-vertex other than x of H are m-2,m-1,n, and n+1. Therefore, H has only one dacard isomorphic to (n,Km-1,n). The degrees of the vertices in the dacard corresponding to an m-vertex of H are m-1,m,n-1, and n where m-1<m≤n-1<n. Hence, this extension H has only one dacard in common with that of Km,n.
Case  2. Augmenting the dacard (m,Km,n-1).
Let(A,B) be the bipartition of the dacard Km,n-1, where A is the set of m vertices. If we join x to every vertex of A, then the extension H is isomorphic to Km,n. We join x therefore to at least one vertex of B.
Case  2.1. Join x to no vertex of A.
Ifn=m+1, then the extension H is isomorphic to Km,n. If n=m+2, then the extension H has two dacards isomorphic to (m,Km,n-1), and, hence, it has only two dacards in common with those of Km,n. So, we take that n>m+2. Now, the extension H has vertices of degrees m,m+1 and n-1 only. Clearly, this extension H has a dacard (m,Km,n-1) corresponding to the m-vertex x. The removal of any other m-vertex from this extension would give a dacard with vertices of degrees m,m+1, and n-2 only, and, hence, this dacard would not be isomorphic to Km,n-1. Thus, H has only one dacard isomorphic to (m,Km,n-1), and this is the only dacard in common with that of Km,n.
Case  2.2. Join x to at least one vertex of A.
Case  2.2.1. Join x to exactly one vertex (say y) of A and exactly one vertex (say z) of B.
In this case,m=2 and the extension H contains exactly one triangle, say xyz. The dacard of the extension H corresponding to the vertex x is clearly (m,Km,n-1). The extension H may have two more dacards (corresponding to the vertices y and z) in common with those of Km,n, since no dacard of Km,n contains a triangle. In the extension H, there exists at least one m-vertex in B other than x. Fix one such vertex and let it be u. The m-vertex u in the dacard obtained by deleting the vertex z from H is not adjacent to the (m-1)-vertex x. The dacard of H corresponding to the vertex z is therefore not isomorphic to (n,Km-1,n) (this verification is needed only for the case when m+1=n). If we remove the vertex y from the extension H, then the (m-1)-vertex u in the resulting dacard is not adjacent to the m-vertex z, and, hence, the dacard of H corresponding to the vertex y is not isomorphic to (m,Km,n-1). The extension H has thus only one dacard in common with that of Km,n.
Case  2.2.2. Join x to exactly one vertex (say y) of A and at least two vertices of B.
The extensionH has at least two triangles. Clearly, the dacard of H corresponding to the vertex x is (m,Km,n-1). The extension H may have one more dacard (corresponding to the vertex y) in common with that of Km,n. In H, there exists at least one (n-1)-vertex in A. Fix one such vertex and let it be z. Then, the (n-1)-vertex z in the dacard of H obtained by deleting the vertex y is not adjacent to the (m-1)-vertex x, where m≠n. The dacard of H (corresponding to the vertex y) is therefore not isomorphic to (n,Km-1,n). The extension H has thus only one dacard in common with that of Km,n.
Case  2.2.3. Join x to at least two vertices of A and exactly one vertex (say y) of B.
The extensionH has at least two triangles. Clearly, the dacard of H corresponding to the vertex x is (m,Km,n-1). The extension H may have one more dacard (corresponding to the vertex y) in common with that of Km,n. In H, there exists at least one (n-1)-vertex of A. Fix one such vertex and let it be z. The (n-1)-vertex z in the dacard of H, obtained by deleting the vertex y, is then not adjacent to the (m-1)-vertex x, where m≠n. The dacard of H (corresponding to the vertex y) is therefore not isomorphic to (n,Km-1,n). The extension H has thus only one dacard in common with that of Km,n.
Case  2.2.4. Join x to at least two vertices of A and at least two vertices of B.
Deletingx from H would give a dacard isomorphic to (m,Km,n-1). The deletion of any vertex other than x from H will give a dacard containing a triangle. The extension H has thus only one dacard isomorphic to (m,Km,n-1), and this is the only dacard in common with that of Km,n, which completes the proof of Theorem 6.


## 3. Concluding Remarks

It is clear, from their definitions, thatdrn(G)≤min{rn(G),adrn(G)}. But rn(G) and adrn(G) are not comparable in general. For instance, it is proved [9] that adrn(P4)=3 and adrn(P5)=4. Therefore, adrn(P4)<rn(P4)=4 and adrn(P5)>rn(P5)=3. However, adrn(K1,3)=rn(K1,3)=3.We summarize our results on theadrn and the corresponding results on the drn in Table 1.Table 1
drn and adrn of graphs G.
G
m
,
n
drn(G)
adrn(G)
K
n
1
1
K
n
,
n
n
>
1
3
3
C
n
n
≥
4
3
3
W
n
n
=
4
1
1
W
n
n
>
4
1
3
K
1
,
n
n
≤
2
1
1
K
1
,
n
n
=
3
1
3
K
1
,
n
n
>
3
1
2
K
m
,
n
2
≤
m
<
n
≠
m
+
2
2
2
K
m
,
n
2
≤
m
,
n
=
m
+
2
2
3



---

*Source: 808105-2013-03-31.xml*