Identifying codes of corona product graphs 3 Min Feng Kaishun Wang∗ 1 Sch. Math. Sci. & Lab. Math. Com. Sys., Beijing Normal University, Beijing, 100875, China 0 2 n a J Abstract 8 1 ForavertexxofagraphG,letNG[x]bethesetofxwithallofitsneighbors in G. A set C of vertices is an identifying code of G if the sets NG[x]∩C are ] nonempty and distinct for all vertices x. If G admits an identifying code, we O say that G is identifiable and denote by γID(G) the minimum cardinality of C an identifying code of G. In this paper, we study the identifying code of the . h corona product H ⊙ G of graphs H and G. We first give a necessary and t sufficientconditionforthe identifiable coronaproductH⊙G, andthenexpress a m γID(H ⊙ G) in terms of γID(G) and the (total) domination number of H. Finally, we compute γID(H ⊙G) for some special graphs G. [ Key words: Identifying code; domination number; total domination number; 1 v corona product. 5 2010 MSC: 94A29, 05C90 9 2 4 . 1 0 3 1 Introduction 1 : v Let G be a finite graph. We often denote by V(G) the vertex set of G. For x ∈ i X V(G), the neighborhood N (x) of x is the set of vertices adjacent to x; the closed G r neighborhood N [x] of x is the union of {x} and N (x). For subsets C and S of a G G V(G), we say that C covers S if the set N [x]∩C is nonempty for each x ∈ S; we G say that C separates S if the sets N [x]∩C are distinct for all x ∈ S. An identifying G code of G is a set of vertices which covers and separates V(G). If G admits an identifying code, we say that G is identifiable and denote by γID(G) the minimum cardinality of an identifying code of G. Note that G is identifiable if and only if the sets N [x] are distinct for all x ∈ V(G). G The concept of identifying codes was introduced by Karpovsky et al. [16] to model a fault-detection problem in multiprocessor systems. It was noted in [4, 5] that determining the identifying code with the minimum cardinality in a graph is an NP-complete problem. Many researchers focused on studying identifying codes of some restricted graphs, for example, paths [2], cycles [2, 10, 20], grids [1, 6, 13] and triangle-free graphs [9]. The identifying codes of graph products were studied; ∗Corresponding author. E-mail address: [email protected] 1 see [3, 11, 14, 15, 17, 18] for cartesian products, [8] for lexicographic products and [19] for direct products. The corona product H ⊙ G of two graphs H and G is defined as the graph obtained from H and G by taking one copy of H and |V(H)| copies of G and joining by an edge each vertex from the ith-copy of G with the ith-vertex of H. For each v ∈ V(H), we often refer to G the copy of G connected to v in H ⊙G. v This paper is aimed to investigate identifying codes of thecorona productH⊙G of graphs H and G. In Section 2, we first give a necessary and sufficient condition fortheidentifiablecoronaproductH⊙G, andthenconstructsomeidentifyingcodes of H⊙G. In Section 3, some inequalities for γID(H⊙G) are established. In Section 4, we express γID(H ⊙G) in terms of γID(G) and the (total) domination number of H. In Section 5, we compute γID(H ⊙G) for some special graphs G. 2 Constructions In this section, we first give a necessary and sufficient condition for the identifiable corona product H ⊙G, and then construct some identifying codes of H ⊙G. Theorem 2.1 Let G be a graph. (i) Suppose K is a trivial graph. Then K ⊙G is identifiable if and only if G is 1 1 an identifiable graph with maximum degree at most |V(G)|−2. (ii) If H is a nontrivial connected graph, then H ⊙G is identifiable if and only if G is identifiable. Proof. (i) Write V(K )= {v}. Note that N [v] = V(K ⊙G). For any vertices 1 K1⊙G 1 x and y of G , we have N [x] = N [y] if and only if N [x] = N [y]. v K1⊙G K1⊙G Gv Gv Hence, the desired result follows. (ii) If H ⊙G is identifiable, then G is identifiable for each v ∈ V(H), which v implies that G is identifiable. Conversely, suppose that G is identifiable. Pick any two distinct vertices x and y of H ⊙G. If {x,y} 6⊆ V(G ) for any v ∈ V(H), then v N [x] 6= N [y]. If there exists a vertex v ∈ V(H) such that {x,y} ⊆ V(G ), H⊙G H⊙G v by N [x]6= N [y] we have N [x] 6= N [y]. So H ⊙G is identifiable. 2 Gv Gv H⊙G H⊙G In the remaining of this section, some identifying codes of the identifiable corona product H ⊙G are constructed. We begin by a useful lemma. Lemma 2.2 A set C of vertices in the corona product H⊙G is an identifying code if, for each v ∈V(H), the following three conditions hold. (i) C ∩V(G ) is nonempty and separates V(G ) in G . v v v (ii) N (v)∩C 6= ∅, or C ∩V(G )6⊆ N [x] for any x ∈ V(G ). H v Gv v (iii) v ∈ C, or C ∩V(G ) covers V(G ) in G . v v v Proof. SinceC∩V(G )6= ∅, thesetC∩V(G )covers {v}. Since{v} covers V(G ), v v v by (iii) the set C∩(V(G )∪{v}) covers V(G ). It follows that C covers V(H⊙G). v v Hence, weonly need toshow that, for any two distinctvertices xandy inV(H⊙G), N [x]∩C 6= N [y]∩C. (1) H⊙G H⊙G 2 Case 1. {x,y}∩V(H) 6= ∅. Without loss of generality, assume that x ∈ V(H). If y ∈ V(H ⊙G)\V(G ), pick z ∈C ∩V(G ), then z ∈ (N [x]∩C)\N [y], x x H⊙G H⊙G which implies that (1) holds. Now supposethat y ∈V(G ). If C∩V(G ) 6⊆ N [y], x x Gx then N [x]∩C 6⊆ N [y], and so (1) holds; If C ∩V(G ) ⊆ N [y], by (ii) we H⊙G H⊙G x Gx can pick z′ ∈N (x)∩C. Then z′ ∈ (N [x]∩C)\N [y], and so (1) holds. H H⊙G H⊙G Case 2. {x,y}∩V(H) = ∅. Then there exist vertices u and v of H such that x ∈ V(G ) and y ∈ V(G ). If u = v, since C ∩ V(G ) separates {x,y} in G , u v u u the set C separates {x,y} in H ⊙G, which implies that (1) holds; If u 6= v, then N [x]∩N [y] = ∅. Since C covers {x,y}, the inequality (1) holds. 2 H⊙G H⊙G Next we shall construct identifying codes of H ⊙G. Corollary 2.3 Let H be an arbitrary graph and G be an identifiable graph with maximum degree at most V(G)−2. Then S v [ v∈V(H) is an identifying code of H ⊙ G, where S is an identifying code of G such that v v S 6⊆ N [x] for any vertex x of G . v Gv v Proof. It is immediate from Lemma 2.2. 2 Proposition 2.4 Let S be a set of vertices inan identifiable graph G. If S separates V(G), then there exists a vertex z ∈ V(G) such that S ∪{z} is an identifying code of G, and so |S|≥ γID(G)−1. Proof. If S covers V(G), then S∪{z} is an identifying code of G for any z ∈ V(G). Now suppose that S does not cover V(G). Then there exists a unique vertex z ∈ V(G) such that N [z]∩S = ∅, which implies that S ∪{z} is an identifying code of G G, as desired. 2 From the above proposition, a set of vertices that separates the vertex set is an identifying code, or is obtained from an identifying code by deleting a vertex. Now we usethis setof vertices in G andthe vertex set of H to constructidentifying codes of H ⊙G. Corollary 2.5 Let H be a nontrivial connected graph and G be a nontrivial identi- fiable graph. Write C = S ∪V(H), v [ v∈V(H) where S is a set of vertices separating V(G ) in G . Then C is an identifying code v v v of H ⊙G. Proof. For each v ∈ V(H), we have C ∩ V(G ) = S 6= ∅, N (v) ∩ C 6= ∅ and v v H v ∈ C. It follows from Lemma 2.2 that C is an identifying code of H ⊙G. 2 LetH beagraph. For asetD ofvertices, wesay thatD isadominating setofH if D covers V(H); we say that D is a total dominating set of H if the set N (x)∩D H 3 is nonempty for each x ∈ V(H). The domination number of H, denoted by γ(H), is the minimum cardinality of a dominating set of H; the total domination number of H, denoted by γ (H), is the minimum cardinality of a total dominating set of H. t Domination and its variations in graphs are now well studied. The literature on this subject has been surveyed and detailed in the the book [12]. The (total) dominating set of H can be used to construct identifying codes of H ⊙G. The proofs of the following corollaries are immediate from Lemma 2.2. Corollary 2.6 Let H be an arbitrary graph and G be an identifiable graph with maximum degree at most |V(G)| − 2. Suppose that D is a dominating set of H. Then S ∪D v [ v∈V(H) isanidentifying code of H⊙G, where S isanidentifying code of G if v ∈ V(H)\D; v v S is a set of vertices separating V(G ) in G such that S 6⊆ N [x] for any vertex v v v v Gv x of G if v ∈ D. v Corollary 2.7 LetH beanontrivialconnected graph andGbeanidentifiable graph. Suppose that T be a total dominating set of H. Then S ∪T v v∈[V(H) is an identifying code of H ⊙G, where S is an identifying code of G . v v 3 Upper and lower bounds In this section, we shall establish some inequalities for γID(H ⊙ G) by discussing the existence of some special identifying codes of G. In order to obtain upper bounds for γID(H ⊙G), it suffices to construct iden- tifying codes of H ⊙ G. By Corollaries 2.3, 2.5 and 2.6, we need to consider the identifying codes S of G satisfying one of the following conditions: (a) |S| = γID(G) and S 6⊆ N [x] for any x ∈V(G). G (b) |S| = γID(G) and there is a vertex z ∈ S such that S \{z} separates V(G). (c) |S| = γID(G)+1 and there exists a vertex z ∈ S such that S \{z} separates V(G) and S \{z} 6⊆ N [x] for any x ∈ V(G). G The identifying codes satisfying (b) or (c) were studied in [3, 8]. Lemma 3.1 Let G and H be two graphs. If there exists an identifying code S of G satisfying (a), then γID(H ⊙G) ≤ |V(H)|·γID(G). Proof. For each v ∈ V(H), let S be the copy of S in G . Corollary 2.3 implies v v that ∪ S is an identifyingcode of H⊙G withsize |V(H)|·γID(G), as desired. v∈V(H) v 2 4 Lemma 3.2 Let G and H be two nontrivial graphs. Suppose that H is connected. If there isanidentifyingcode S ofGsatisfying (b), thenγID(H⊙G)≤ |V(H)|·γID(G). Proof. Note that there exists a vertex z ∈ S such that S\{z} separates V(G). For each v ∈ V(H), let S be the copy of S \{z} in G . It follows from Corollary 2.5 v v that ∪ S ∪V(H) is an identifying code of H ⊙G with size |V(H)|·γID(G). v∈V(H) v Therefore, the desired inequality holds. 2 Lemma 3.3 Let G and H be two nontrivial graphs. If there exists an identifying code S of G satisfying (c), then γID(H ⊙G) ≤ |V(H)|·γID(G)+γ(H). Proof. Observe that there exists a vertex z ∈ S such that S \{z} separates V(G) and S \{z} 6⊆ N [x] for any vertex x ∈ V(G). Suppose that W is an identifying G code of G withsize γID(G) andD is a dominatingset of H withsize γ(H). For each v ∈ D, let S be the copy of S \{z} in G . For each v ∈ V(H)\D, let S be the v v v copy of W in G . It follows from Corollary 2.6 that ∪ S ∪D is an identifying v v∈V(H) v code of H ⊙G with size |V(H)|·γID(G)+γ(H), as desired. 2 With reference to Corollary 2.7, let T and S have the sizes γ (H) and γID(G), v t respectively. Then we get the following result immediately. Lemma 3.4 Let G be an identifiable graph and H be a nontrivial connected graph. Then γID(H ⊙G) ≤ |V(H)|·γID(G)+γ (H). t In the remaining of this section, we give lower boundsfor γID(H⊙G). We begin by discussing the properties of an identifying code of H ⊙G. Lemma 3.5 Let C be an identifying code of H ⊙ G and let v be a vertex of the first factor H. Then C ∩V(G ) separates V(G ) in G . Moreover, if v 6∈ C, then v v v C ∩V(G ) is an identifying code of G . v v Proof. Note that v is adjacent to every vertex in V(G ), and there are no edges v joining V(H⊙G)\({v}∪G ) with V(G ). Since C separates V(G ) in H⊙G, the v v v set C∩V(G ) separates V(G ) in G . If v 6∈ C, since C covers V(G ) in H⊙G, the v v v v set C ∩V(G ) covers V(G ) in G , which implies that C ∩V(G ) is an identifying v v v v code of G . 2 v Lemma 3.6 If H ⊙G is identifiable, then γID(H ⊙G) ≥ |V(H)|·γID(G). Proof. Let C be an identifying code of H ⊙G with size γID(H ⊙G). Combining Lemma 3.5 and Proposition 2.4, we have γID(G)−1, if v ∈ V(H)∩C, |C ∩V(G )| ≥ v (cid:26) γID(G), if v ∈ V(H)\C. Then γID(H⊙G) = (|C∩V(G )|+1)+ |C∩V(G )| ≥ |V(H)|·γID(G), v v v∈VX(H)∩C v∈VX(H)\C as desired. 2 5 Lemma 3.7 LetGbeanidentifiable graph withmaximum degree at most|V(G)|−2. If any identifying code of G does not satisfy (a), then γID(K ⊙G) ≥ γID(G)+1. 1 Proof. ByTheorem2.1,thecoronalproductK ⊙Gisidentifiable. Hence,Lemma3.6 1 implies that γID(K ⊙G) ≥ γID(G). Supposefor the contradiction that there exists 1 an identifying code C of K ⊙G with size γID(G). Write V(K ) = {v}. 1 1 Case 1. v 6∈ C. Then C is an identifying code of G with cardinality γID(G) v by Lemma 3.5. Hence, there is a vertex x ∈ V(G ) such that C ⊆ N [x], which v Gv implies that N [x]∩C = C = N [v]∩C, a contradiction. H⊙G H⊙G Case 2. v ∈ C. Then C ∩V(G ) = C \{v}. Combining Proposition 2.4 and v Lemma3.5,thereexistsavertexz ∈V(G )suchthat(C\{v})∪{z}isanidentifying v code of G with cardinality γID(G). Hence, we have (C \{v})∪{z} ⊆ N [y] for v Gv some y ∈ V(G ), which implies that (C \ {v}) ⊆ N [y]. Consequently, we get v Gv N [y]∩C = C = N [v]∩C, a contradiction. 2 H⊙G H⊙G Lemma 3.8 Suppose that C is an identifying code of H ⊙ G. If any identifying code of G does not satisfy (b), then |C ∩V(G )| ≥ γID(G) for each v ∈V(H). v Proof. Lemma 3.5 implies that C ∩ V(G ) separates V(G ) in G . Then |C ∩ v v v V(G )| ≥ γID(G)−1 by Proposition 2.4. If |C∩V(G )| = γID(G)−1, there exists v v avertex z ∈ V(G) suchthat(C∩V(G ))∪{z} is anidentifyingcodeof G satisfying v v (b), a contradiction. 2 For a set C of vertices in H ⊙G, write H(C)= V(H)∩C, H′(C) ={v |v ∈V(H),|C ∩G |≥ γID(G)+1}. v Lemma 3.9 Suppose that C is an identifying code of H ⊙ G. If any identifying code of G does not satisfy (b), then |C|≥ |V(H)|·γID(G)+|H(C)|+|H′(C)|. Proof. WriteH = V(H)\(H(C)∪H′(C)),H = H′(C)\H(C),H = H(C)\H′(C) 1 2 3 andH = H(C)∩H′(C). LetC =C∩V(G ). ByLemma3.8weget|C |= γID(G) 4 v v v for each v ∈ H ∪H . Then 1 3 |C| = |C |+ |C |+ (|C |+1)+ (|C |+1) v v v v vX∈H1 vX∈H2 vX∈H3 vX∈H4 ≥ |H |γID(G)+|H |(γID(G)+1)+|H |(γID(G)+1)+|H |(γID(G)+2) 1 2 3 4 = |V(H)|·γID(G)+|H(C)|+|H′(C)|, as desired. 2 Lemma 3.10 Let G be a nontrivial identifiable graph and H be a nontrivial con- nected graph. If each identifying code of G satisfies neither (a) nor (b), then γID(H ⊙G) ≥ |V(H)|·γID(G)+γ(H). 6 Proof. Theorem 2.1 implies that H ⊙ G is identifiable. Let C be an identifying code of H ⊙G with size γID(H ⊙G). Write D = H(C)∪H′(C). We shall show that D is a dominating set of H. Pick any v ∈ V(H) \ D. Note that v 6∈ C and |C ∩V(G )| ≤ γID(G). Then C ∩V(G ) is an identifying code of v v G with size γID(G ) by Lemma 3.5. Since each identifying code of G does not v v v satisfy (a), there exists a vertex x ∈ V(G ) such that C ∩V(G ) ⊆ N [x]. Since v v Gv N [v] ∩ C 6= N [x] ∩ C = C ∩ V(G ), we have N (v) ∩ H(C) 6= ∅, which H⊙G H⊙G v H implies that N (v)∩D 6= ∅. Then D is a dominating set of H. H Hence, we have |D| ≥ γ(H). By Lemma 3.9, we get γID(H ⊙G) = |C| ≥ |V(H)|·γID(G)+|H(C)∪H′(C)|≥ |V(H)|·γID(G)+γ(H), as desired. 2 Lemma 3.11 Let G be a nontrivial identifiable graph and H be a nontrivial con- nected graph. If each identifying code of G satisfies none of the conditions (a), (b) and (c), then γID(H ⊙G) ≥ |V(H)|·γID(G)+γ (H). t Proof. For each vertex v ∈ V(H), pick a vertex v′ ∈ N (v). Theorem 2.1 implies H thatH⊙Gisidentifiable. LetC beanidentifyingcodeofH⊙GwithsizeγID(H⊙G). Write T = H′′(C)∪H(C), where H′′(C) = {v′ | v ∈ H′(C)}. WeclaimthatT isatotaldominatingsetofH. Pickanyv ∈ V(H). Ifv ∈ H′(C), since N (v)∩H′′(C) 6= ∅ we have N (v)∩T 6= ∅. Now suppose that v 6∈ H′(C). H H By Lemma 3.8 we get |C ∩ V(G )| = γID(G ). If C ∩ V(G ) 6⊆ N [x] for any v v v Gv vertex x ∈ V(G ), then C ∩ V(G ) is not an identifying code of G . It follows v v v from Lemma 3.5 and Proposition 2.4 that there exists a vertex z ∈ V(G ) such v that (C ∩V(G ))∪{z} is an identifying code of G satisfying (c), a contradiction. v v Therefore, there exists a vertex x ∈ V(G ) such that C ∩V(G ) ⊆ N [x]. Since v v Gv N [v] ∩ C 6= N [x] ∩ C, we have N (v) ∩ H(C) 6= ∅, which implies that H⊙G H⊙G H N (v)∩T 6= ∅. Hence, our claim is valid. H Since |T|≥ γ (H) and |H′(C)| ≥ |H′′(C)|, we get |H′(C)|+|H(C)| ≥ γ (H). By t t Lemma 3.9, we have γID(H ⊙G) = |C|≥ |V(H)|·γID(G)+γ (H), t as desired. 2 4 Minimum cardinality In this section, we shall compute γID(H ⊙G). 7 Theorem 4.1 Let G and H be two nontrivial graphs. Suppose that H is connected. If there exists an identifying code of G satisfying (a) or (b), then γID(H ⊙G) = |V(H)|·γID(G). Proof. It is immediate from Theorem 2.1, Lemmas 3.1, 3.2 and 3.6. 2 Theorem 4.2 Let G be a nontrivial identifiable graph and H be a nontrivial con- nected graph. Suppose that each identifying code of G satisfies neither (a) nor (b). (i) If there exists an identifying code of G satisfying (c), then γID(H ⊙G) = |V(H)|·γID(G)+γ(H). (ii) If any identifying code of G does not satisfy (c), then γID(H ⊙G) = |V(H)|·γID(G)+γ (H). t Proof. (i) holds by Lemmas 3.3 and 3.10. By Lemmas 3.4 and 3.11, (ii) holds. 2 Now, we compute γID(K ⊙G) and γID(H ⊙K ). 1 1 Theorem 4.3 Suppose that G isan identifiable graph with maximum degree at most |V(G)|−2. (i) If there exists an identifying code of G satisfying (a), then γID(K ⊙G) = γID(G). 1 (ii) If any identifying code of G does not satisfy (a), then γID(K ⊙G) = γID(G)+1. 1 Proof. Theorem 2.1 implies that K ⊙G is identifiable. 1 (i) It is immediate from Lemmas 3.1 and 3.6. (ii) By Lemma 3.7 we only need to construct an identifying code of K ⊙G with 1 size γID(G)+1. Let W be an identifying code of G with size γID(G). Note that thereexists auniquevertex x ∈ V(G)such thatW ⊆ N [x]. Pick y ∈V(G)\N [x]. G G Write V(K ) = {v}. Let S bethe copy of W∪{y} in G . Then S is an identifying 1 v v v codeof G with S 6⊆ N [z] forany vertex z ∈V(G ). Itfollows fromCorollary 2.3 v v Gv v that S is an identifying code of K ⊙G with size γID(G)+1, as desired. 2 v 1 Corollary 4.4 Let G be an identifiable graph and H be a connected graph. Suppose that G satisfies one of the following conditions. (i) The graph G is not connected. (ii) The diameter of G is at least five. (iii) The maximum degree of G is less than γID(G)−1. Then γID(H ⊙G) = |V(H)|·γID(G). 8 Proof. NotethattheidentifyingcodesofGwithsizeγID(G)satisfy(a). Combining Theorems 4.1 and 4.3, we get the desired result. 2 Theorem 4.5 Let n ≥ 2. Then γID(K ⊙K ) = n+1, where K is the complete n 1 n graph on n vertices. Proof. Since K is identifiable, Theorem 2.1 implies that K ⊙K is identifiable. 1 n 1 Write V = V(K )= {v ,...,v }. For each i∈ {1,...,n}, denote by {u } thevertex n 1 n i set of the copy of K connected to v in K ⊙K . Write V′ = {u ,...,u }. Note 1 i n 1 1 n that V(K ⊙ K ) = V ∪ V′. Let C be an identifying code of K ⊙ K with size n 1 n 1 γID(K ⊙K ). We have the following two claims. n 1 Claim 1. |V ∩C|≥ 2. In fact, for any i ∈ {1,...,n}, since (V ∪{u })∩C = N [v ]∩C 6= N [u ]∩C = {u ,v }∩C, i Kn⊙K1 i Kn⊙K1 i i i we have |(V \{v })∩C|≥ 1. So |V ∩C|≥ 2. i Claim 2. |V′ ∩ C| ≥ n − 1. In fact, if there exist two distinct vertices u i and u neither of which belongs to C, then N [v ]∩C = N [v ]∩C, a j Kn⊙K1 i Kn⊙K1 j contradiction. Combining Claim 1 and Claim 2, we have γID(K ⊙K )= |V ∩C|+|V′∩C|≥n+1. n 1 Itis routineto showthat{u | 2 ≤ i≤ n}∪{v ,v }is anidentifying codeof K ⊙K i 1 2 n 1 with size n+1. Hence, the desired result follows. 2 Theorem 4.6 Let H be a connected graph that is not complete. Then γID(H ⊙K ) = |V(H)|. 1 Proof. Theorem 2.1 implies that H ⊙K is identifiable. Since γID(K ) = 1, by 1 1 Lemma 3.6 it suffices to construct an identifying code of H ⊙K with size |V(H)|. 1 For any u,v ∈ V(H), define u ≡ v if N (u) = N (v). Note that “ ≡ ” is H H an equivalence relation. Let O denote the equivalence class containing u. Pick u a representative system D with respect to this equivalence relation. For each v ∈ V(H), denote by {u } the vertex set of the copy of K connected to v in H ⊙K . v 1 1 Let C = {u | v ∈V(H)\D}∪D. v Observe that |C|= |V(H)|. Since C covers V(H ⊙K ), it suffices to show that, for 1 any two distinct vertices x and y of H ⊙K , 1 N [x]∩C 6= N [y]∩C. (2) H⊙K1 H⊙K1 Case 1. |{x,y}∩V(H)| = 2. If N [x] 6= N [y], there exists a vertex z ∈ V(H) H H such that {z} separates {x,y} in H. Note that there exists a vertex z′ ∈ D such that Oz′ = Oz. Then NH[z′] = NH[z], and so {z′} separates {x,y} in H. It follows that {z′} separates {x,y} in H ⊙ K . Since z′ ∈ C, the inequality (2) holds. If 1 9 N [x] = N [y], then O = O , which implies that x 6∈ D or y 6∈ D. Without loss H H x y of generality, we may assume that x 6∈ D. Then u ∈ (N [x]∩C)\N [y], x H⊙K1 H⊙K1 which implies that (2) holds. Case 2. |{x,y}∩V(H)| = 1. Without loss of generality, assume that x ∈ V(H) and y = u for some v ∈ V(H). If x 6= v, since both {x} and {u } separate {x,y} in v x H ⊙G, we obtain (2) by {x,u }∩C 6= ∅. Now suppose that x = v. Since H is not x complete, we have |D| ≥ 2. Hence, there is a vertex w ∈ D such that w is adjacent to x in H. It follows that w ∈ (N [x]∩C)\N [y], and so (2) holds. H⊙K1 H⊙K1 Case 3. |{x,y}∩V(H)| = 0. Then N [x]∩N [y] = ∅. Since C covers H⊙K1 H⊙K1 {x,y} in H ⊙G, the inequality (2) holds. 2 Let T = K ⊙K and T = T ⊙K for n ≥ 2. We call T a binomial tree, 1 1 1 n n−1 1 n which is a useful data structure in the context of algorithm analysis and design [7]. Note that T is a spanning tree of the hypercube Q . The problem of computing n n γID(Q ) is still open. By Theorem 4.6, we get the following corollary. n Corollary 4.7 Let n ≥ 3. Then γID(T )= 2n−1. n For a connected graph with pendant edges, we have the following more general result than Theorem 4.6. Corollary 4.8 Let H be a connected graph with m vertices. Suppose that H is a 1 graph obtained from H by adding n (≥ 1) pendant edges to the ith-vertex of H. If i H is not isomorphic to K ⊙K , then 1 m 1 m γID(H ) = n . (3) 1 i Xi=1 Proof. It is routine to show that (3) holds for m = 1. Now suppose m ≥ 2. Write V(H) = {v ,...,v }. For each i ∈ {1,...,m}, let S = {u | 1 ≤ j ≤ n } be the 1 m i ij i set of vertices adjacent to v in V(H )\V(H). Then the subgraph of H induced i 1 1 by S is isomorphic to K . Similar to the proof of Lemma 3.6, we have i ni m m γID(H )≥ γID(K ) = n . 1 ni i Xi=1 Xi=1 In order to prove (3), it suffices to construct an identifying code of H with size 1 m n . i=1 i P Case 1. H is a complete graph. Then there exists an index j ∈ {1,...,m} such that n ≥2. Pick k ∈ {1,...,m}\{j}. It is routine to show that j {v ,v }∪(S \{u })∪(S \{u })∪ S j k j j1 k k1 i i∈{1,...[,n}\{j,k} is an identifying code of H with size m n . 1 i=1 i Case 2. H is not a complete graphP. Write m A = {v ,u }, B = V(H )\A. i i1 1 i[=1 10