11_577_germina.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 3, No. 2, 2010, 269-281 ISSN 1307-5543 – www.ejpam.com More on Classes of Strongly Indexable Graphs K. A. Germina P.G. & Research Department of Mathematics, Mary Matha Arts & Science College (Kannur Univer- sity), Mananthavady-670645, India. Abstract. Given any positive integer k, a (p,q)-graph G = (V, E) is strongly k-indexable if there exists a bijection f : V → {0,1,2, . . . , p − 1} such that f +(E(G)) = {k, k + 1, k + 2, . . . , k + q − 1, } where f +(uv) = f (u)+ f (v) for any edge uv ∈ E; in particular, G is said to be strongly indexable when k = 1. For any strongly k-indexable (p,q)-graph G, q ≤ 2p − 3 and if, in particular, q = 2p − 3 then G is called a maximal strongly indexable graph. In this paper, our main focus is to construct more classes of k-strongly indexable graphs. 2000 Mathematics Subject Classifications: 05C78 Key Words and Phrases: Strongly Indexable, edge-magic, super-edge-magic, graphs 1. Introduction Unless mentioned otherwise, by a graph we shall mean in this paper a finite, undirected, connected graph without loops or multiple edges. Terms not defined here are used in the sense of Harary [11]. Acharya et.al [2] introduced the concept of an ’indexer’ of a graph as a special case of arithmetic labelings. A labeling of a graph G = (V, E) is an assignment f of distinct nonnegative integers to the vertices of G; it is an indexer of G if the induced ’edge function’ f + : E(G)→ N, from E(G) into the set N of natural numbers, defined by the rule: f +(uv) = f (u) + f (v), ∀ uv ∈ E(G), is also injective. It is known that every finite graph has an indexer; hence, an indexer f is said to be optimal if f [G] := maxv∈V (G){ f (v)} has the least possible value υ(G) amongst all the indexers of G. Clearly, υ(G) ≥ |V (G)| for any graph G with a countable number of vertices. For any given positive integer k, an indexer f of G is called a k-indexer if f +(E(G)) := { f +(uv) : uv ∈ E(G)} = {k, k+ 1, k+ 2, . . . , }. Not every graph is k-indexable as indicated by the following theorem for finite graphs. Email address: srgerminaka�gmail. om http://www.ejpam.com 269 c© 2010 EJPAM All rights reserved. K. A. Germina / Eur. J. Pure Appl. Math, 3 (2010), 269-281 270 Theorem 1. [2]: Let G = (V, E) be any (p,q)-graph and f be any k-indexer of G, where k is odd. Then, there exists an ’equitable partition’ of V into two subsets Vo and Ve such that there are exactly ⌈ q+k−1 2 ⌉ edges each of which joins a vertex of Vo with one of Ve, where ⌈.⌉ denotes the least integer function. Theorem 2. [2]: For any indexable (p,q)-graph G, q ≤ 2p−3, calling G a maximally indexable graph if q = 2p− 3. Acharya and Germina [3] characterized the classes of maximal strongly indexable graphs, satisfying q = 2p− 3, particularly, such outerplanar graphs. We shall need the following known results. Theorem 3. [1]: For any graph G = (V, E) and for any additive vertex function f : V (G)→ N, Σe∈E f +(e) = Σu∈V f (u)d(u) Theorem 4. [2]: Every strongly indexable finite graph has at most one nontrivial component which is either a star or has a triangle. Lemma 1. [4]: Let G = (V, E) be a maximal outerplanar graph with p > 7. Let H = (u1,u2,u3, . . . ,up) be a Hamiltonian cycle in G. Let V1 = {u1,u2,u3, . . . ,u⌊ p 2 ⌋} and V2 = {u⌊ p 2 ⌋+1,u⌊ p 2 ⌋+2,u⌊ p 2 ⌋+3, . . . ,up} constitute an equitable partition of the vertex set of G. Then, no chord of G has both vertices in V1 or V2 if and only if ∆(G) = ⌊ p 2 ⌋+ 2 and there exist exactly two vertices of degree 2. Theorem 5. [4]: Let G = (V, E) be a maximal outerplanar graph with p > 7. Then, G is strongly indexable if and only if ∆(G) = ⌊ p 2 ⌋+ 2 and there exist exactly two vertices of degree 2. 2. Construction of Strongly Indexable Graphs Definition 1. Let G1 = (V1, E1) and G2 = (V2, E2) be two graphs. Then the join G = (V, E) of G1 and G2 is defines as the V = V1+ V2 and the edge set E of G is the edges in G1 ∪G2 and all edges joining G1 and G2. In this section we study the properties of some important families of graphs such as fans, ladders, and generalized prisms that are strongly indexable (for some value of k). Theorem 6. The fan Pn + K1 is strongly indexable if and only if n ∈ {1,2,3,4,5,6}. Proof. The strongly indexable labellings of Pn + K1 for n ∈ {1,2,3,4,5,6} is depicted in Figure 1 Conversely, note that Pn + K1, for n ≥ 2 is a maximal outer planar graph with q = 2p− 3 and there exists a vertex of full degree. Hence invoking Lemma 1 ( see, [4]), G is strongly indexable if and only if p ≤ 7. Hence the proof follows. Theorem 7. Pn + K2 is strongly indexable if and only if n≤ 2. K. A. Germina / Eur. J. Pure Appl. Math, 3 (2010), 269-281 271 Figure 1 Proof. The strongly indexable labellings of Pn + K2 for n= 1,2 is depicted in Figure 2 Figure 2 Converse follows from the fact that for any indexable (p,q)-graph G, q ≤ 2p − 3 (See [1, 2]), since |E(Pn+ K2)| > 2|V (Pn+ K2)| − 3. In general, we have the following Theorem Theorem 8. Pn + Ki is strongly indexable if and only if n ≤ 2, when i ≤ 2, and n ≤ 6, when i = 1 Lemma 2. For every positive integer n, the graph K2 + nK1 is strongly indexable. Proof. Let V (K2) = {v1, v2} and V (nK1) = {u1,u2, . . . ,un}. Let f : V (K2 + nK1) → {0,1,2 . . . , n+ 1} defined by f (v1) = 0; f (v2) = n+ 1; f (ui) = i, 1≤ i ≤ p− 2 Remark 1. Lemma 2 establishes the sharpness of the Theorem 2 and hence we obtain a sequence of strongly indexable graphs as follows: Take the labellling f defined for K2 + nK1. Remove the edge with maximum labelling (here 2p− 3) and continue this process of removing the edge with maximum labelling until we arrive at K1,n. Hence we are able to characterize all the strongly indexable complete m-bipartite graphs as follows. Theorem 9. The only strongly indexable complete m-partite graphs are K1,n and K1,1,n, for all integers n≥ 1 K. A. Germina / Eur. J. Pure Appl. Math, 3 (2010), 269-281 272 Proof. It is easy to see that K1,n is strongly indexable by assigning 0 to the central vertex and the integers 1,2, . . . n− 1 to the non-central vertices in a one-one manner. Furthermore, the complete tripartite graph K1,1,n ∼= K2 + nK1 is strongly indexable by Lemma 2. For the uniqueness of K1,1,n let G ∼= Kn1,n2,n3 be a complete tripartite graph with n1, n2, n3 ≥ 1. Now, assume the contrary that n2 ≥ 2 and G is strongly indexable. The order of G is n1 + n2 + n3 and the size of G is n1n2 + n1n3 + n2n3. Since Kn1,n2,n3 is strongly indexable by assumption, n1n2+ n1n3+ n2n3 ≤ 2(n1+ n2+ n3)− 3, which in turn implies n1n3 < 2n2− 3, since n2 ≥ 2. Hence n2n3 ≤ 2n2, which implies 2− n3 > 0, from which we conclude that n3 = 1. By similar argument we get n1 = 1. Now to show that there are no strongly indexable complete m-partite graphs for m ≥ 4, observe that K1,1,1,n is such that |E(K1,1,1,n)| > 2|V (K1,1,1,n)| − 3. (|V (K1,1,1,n| = 3 + n and |E(K1,1,1,n| = 3n+ 3). Definition 2. Let G1 = (V1, E1) and G2 = (V2, E2) be two graphs. Then the Cartesian product G = (V, E) of G1 and G2 is defined as : Consider any two nodes u = u1u2 and v1v2 in V = V1×V2. Then u and v are adjacent in G1 × G2, whenever u1 = v1 and u2v2 ∈ E(G2) or u2 = v2 and u1v1 ∈ E(G1). The Ladder Ln ∼= Pn × P2 is not strongly indexable for all n ≥ 2, since L2 contains no triangle. However there exists an integer k such that L2 is k-strongly indexable. Theorem 10. The ladder Ln ∼= Pn × P2 is ⌈ n 2 ⌉-strongly indexable, if n is odd. Proof. Let V (P2) = {v1, v2} and V (Pn) = {ui : 1 ≤ i ≤ n}. Define f : V (Pn × P2) → {0,1,2, . . . , 2n} defined by f (ui, v1) = ¨ i−1 2 1≤ i ≤ n, i odd n+i−1 2 1≤ i ≤ n, i even and f (ui , v2) = ¨ f (un−1v1) + i 2 1≤ i ≤ n, i even f (un−1v1) + n+i 2 1≤ i ≤ n, i odd Remark 2. The converse of Theorem 10 is not true. L2 ∼= C4 is not k-strongly indexable. However P4 × P2 and P6 × P2 are 3-strongly indexable and 4-strongly indexable respectively. (See Figure 3) Theorem 11. K3× Pn is strongly indexable Proof. Let V (K3) = {ui : 1≤ i ≤ 3} and V (Pn) = {x i : 1≤ i ≤ n}. Define f : V (K3× Pn)→ {0,1, , 2, . . . , 3n} defined by f (u1 x i) = {0,4,6,10,12,16,18,22,24,30,32,36, . . .} f (u2 x i) = {2,3,8,9,14,15,20,21,26,27,32, . . .} and f (u3 x i) = {1,5,7,11,13,17,19,23,25,29,31,35, . . .} Figure 4 illustrates the strongly indexable labelling of K3 × P4 K. A. Germina / Eur. J. Pure Appl. Math, 3 (2010), 269-281 273 Figure 3 Figure 4 Theorem 12. In general Kn× Pk is strongly indexable if and only n= 3. Proof. Necessary part follows from Theorem 11. Converse follows from the fact that |E(Kn× Pk)| > 2|V (Kn× Pk)| − 3. Theorem 13. Cm× Pn is 2-strongly indexable if m is odd and n≥ 2 Proof. Assume V (Cm) = {vi , 1 ≤ i ≤ m} and V (Pn) = {u j , 1 ≤ j ≤ n.} Now, the 2-strongly indexable labeling f is defined as follows f (vi,u j) =        i+m−1 2 1≤ i ≤ m, i even j = 1 i−1+m(2 j−1) 2 2≤ j ≤ n, j odd, 1≤ i ≤ m i−2+m(2 j−1) 2 2≤ j ≤ n, j even, 1≤ i ≤ m, i odd i−2+m(2 j−2) 2 2≤ j ≤ n, j even 1≤ i ≤ m, i even Remark 3. Even though Cm×Pn is not strongly indexable we can generate infinitely many classes of strongly indexable graph G by adjoining two vertices say u and v with the vertex assignments 0 and 1 respectively. Hence Cm× Pn∪{uv}, where u and v having the vertex assignments 0 and 1 are classes of strongly indexable graphs. In fact, this constriction of adjoining an edge uv where, f (u) = 0and f (v) = 1 of a 2-strongly indexable graphs results in to a strongly indexable graph. Theorem 14. Given any k-strongly indexable graph G = (p,q), there exists a strongly indexable graph H = (p,q+ k− 1) graph, with G a spanning subgraph of H. K. A. Germina / Eur. J. Pure Appl. Math, 3 (2010), 269-281 274 Proof. Let G = (p,q), be k-strongly indexable and let f be the k-strong indexer of G. Hence, f (V (G) = {0,1,2, . . . , p− 1} and f +(E(G) = {k, k+ 1, . . . , k+ q− 1}. Let u ∈ V (G) be such that f (u) = 0 and let ui, 1 ≤ i ≤ k− 1 be the vertices of G with f (ui) = i, 1≤ i ≤ k− 1. Now construct the edges by joining uui so that f (uui) = {1,2, . . . , k − 1}. The new graph H constructed is a (p,q+k−1) graph with f (V (H) = {0,1,2, p−1} and f +(E(H) = {1,2, . . . , k+ q− 1} and hence f is a strong indexer of H. Figure 5 and Figure 6 gives the strongly indexable labellings of C5× Pn and C5× Pn∪{uv} Figure 5 Figure 6 Definition 3. For three or more disjoint graph G1, G2, . . . , Gk sequential join G1 + G2 + . . . Gk is the graph (G1+ G2)∪ (G2 + G3)∪ · · · ∪ (Gk−1+ Gn) Lemma 3. Let Gi ∼= K1, 1≤ i ≤ n. Then the sequential join (G1+G2)∪(G2+G3)∪· · ·∪(Gn−1+ Gn) is strongly indexable if and only if n≤ 3. Proof. The proof follows from the fact that Pn is strongly indexable if and only if n≤ 3. Lemma 4. Let Gi ∼= K1, 1≤ i ≤ n. Then the sequential join (G1+G2)∪(G2+G3)∪· · ·∪(Gn−1+ Gn) is ⌈ n 2 ⌉- strongly indexable for all n. Proof. The proof follows from the fact that Pn is ⌈ n 2 ⌉-strongly indexable for all n, where the ⌈ n 2 ⌉-strongly indexable labelling of Pn is as follows K. A. Germina / Eur. J. Pure Appl. Math, 3 (2010), 269-281 275 Define f : V (Pm)→ {0,1,2, . . . , m− 1} defined by f (ui) =      i−1 2 1≤ i ≤ m, i odd, m odd i−1 2 1≤ i ≤ m− 1, i odd, m even n−i−1 2 2≤ i ≤ m− 1, i even, m odd n−i−2 2 2≤ j ≤ m− 1, i even, m even Lemma 5. Let G1 ∼= K1, and Gi ∼= K2, 2 ≤ i ≤ n. The sequential join (G1 + G2) ∪ (G2 + G3)∪ · · ·∪(Gn−1+Gn) is strongly indexable if and only if n= 2. However, Pn is ⌈ n 2 ⌉-strongly indexable. Proof. The proof follows from the fact that Pn is strongly indexable if and only if n≤ 3 and that Pn is ⌈ n 2 ⌉-strongly indexable Theorem 15. K1,n+ Ki is not strongly indexable for n≥ 2, i ≥ 1. Proof. The proof follows from the fact that |E(K1,n+ Ki)|> 2V (K1,n+ Ki)| − 3. Theorem 16. Let Gi ∼= K1,n, 1 ≤ i ≤ n. The sequential join G ∼= (G1 + G2) ∪ (G2 + G3) ∪ · · · ∪ (Gn−1 + Gn) is strongly indexable if and only if, either i = n = 1 or i = 2 and n = 1 or i = 1, n= 3. Proof. Let i = n = 1, then G ∼= P2, which is strongly indexable and when i = 2 and n = 1 or i = 1, n= 3, G ∼= P3 which is again strongly indexable. Converse follows from the fact that, whenever i = n > 1 or i > 2 and n > 1 or i > 1, n > 3, |E(G)|> |V (G)− 3. Definition 4. Let G1 = (V1, E1) and G2 = (V2, E2) be two graphs. Then the union G = (V, E) of G1 and G2 is defines as the V = V1 ∪ V2 and E = E1 ∪ E2. Theorem 17. For any integer n≥ 3, the linear forest P1 ∪ Pn is strongly indexable if and only if n≤ 3. Proof. Clearly, for n ∈ {0,1,2}, P1 ∪ Pn is strongly indexable. Conversely, since Pn, n ≥ 4 is not strongly indexable since we can not have a strongly index- able labelling of Pn. Theorem 18. For any integer n≥ 3, the linear forest P1 ∪ Pn is ⌈ n 2 ⌉-strongly indexable. Proof. The proof is immediate as Pn, n≥ 4 is ⌈ n 2 ⌉-strongly indexable. Theorem 19. The linear forest P2 ∪ Pn is not strongly indexable. However P2 ∪ Pn is ⌈ n+3 2 ⌉- strongly indexable. K. A. Germina / Eur. J. Pure Appl. Math, 3 (2010), 269-281 276 Proof. Let P2 ∪ Pn be a linear forest. Let V (P2 ∪ Pn) = {u1,u2} ∪ {vi, 1 ≤ i ≤ n} so that E(P2 ∪ Pn) = {u1u2} ∪ {vi vi+1, 1≤ i ≤ n− 1}. Now, V (P2 ∪ Pn) = n+ 2 and E(P2 ∪ Pn) = n. Define f : V (P2 ∪ Pn)→ {0,1,2, . . . , n+ 1} defined in the following cases. Case 1 n≡ 0(mod4) f (u1) = 0; f (u2) = n 2 + 2 f (v j) =              n 2 + 1 if j =1 n 2 + 3 if j = 3 2i− 1 if j = 4i and 1≤ i ≤ n 4 n 2 + 2i+ 3 if j = 4i+ 2 and 1≤ i ≤ n−4 4 2i+ 2 if j = 4i and 1≤ i ≤ n−4 4 n 2 + 2i+ 2 if j = 4i+ 3 and 1≤ i ≤ n−4 4 Case 2 n≡ 1(mod4) f (u1) = 0; f (u2) = n+ 1 f (v j) =    n+2 j+1 4 if j is odd and 1≤ j ≤ n 3n+2 j+1 4 + 3 if j is even and 2≤ j ≤ n−1 2 2 j−n+1 4 if j is even and n+3 2 ≤ j ≤ n−1 2 Case 3 n≡ 2(mod4) f (u1) = 0; f (u2) = n 2 + 1 f (v j) =                  n+ 1 if j =1 n− 1 if j = 3 n if j = n n 2 − 2i+ 1 if j = 4i and 1≤ i ≤ n−2 4 n− 2i− 1 if j = 4i+ 1 and 1≤ i ≤ n−2 4 n 2 − 2i− 2 if j = 4i+ 2 and 0≤ i ≤ n−6 4 n− 2i if j = 4i+ 3 and 1≤ i ≤ n−6 4 Case 4 n≡ 3(mod4) f (u1) = 0; f (u2) = n+ 1 K. A. Germina / Eur. J. Pure Appl. Math, 3 (2010), 269-281 277 f (v j) =        j+1 2 if j is odd and 1≤ j ≤ n−1 2 j+n 2 + 3 if j is odd and n+3 2 ≤ j ≤ n j+n+1 2 if j is even and 2≤ j ≤ n−3 2 j+2 2 + 3 if j is even and n+1 2 ≤ j ≤ n− 1 In all the cases f extends a ⌈ n+3 2 ⌉-strongly indexable labelling, as the edge values are consecutive integers from ⌈ n+3 2 ⌉ to ⌈3n+1 2 ⌉. Theorem 20. For an integer m ≥ 2, P3 ∪ mP2 is k-strongly indexable, where k = 3m+3 2 if m is odd and k = 3m+2 2 if m is even. Proof. Case 1 m is odd Define f : V (P3 ∪mP2)→ {0,1,2, . . . , 2m+ 2} defined by f (x) =                  3m−5 2 if x = u m+ 1 if x = v m+3 2 if x = w i − 1 if x = ui and m−1 2 ≤ i ≤ m+3 2 i if x = ui and m+5 2 ≤ i ≤ m i + 3m−2 2 + 2 if x = vi and 1≤ i ≤ m+3 2 i + m−1 2 if x = vi and m+5 2 ≤ i ≤ m Clearly f is infective and the edge values are consecutive numbers from 3m+3 2 to 5m−1 2 . Case 2 m is even Define f : V (P3 ∪mP2)→ {0,1,2, . . . , 2m+ 2} defined by f (x) =                m+ 1 if x = u m if x = v m+ 2 if x = w i − 1 if x = ui and 1≤ i ≤ m+2 2 i if x = ui and m 2 ≤ i ≤ m i + 3m 2 + 2 if x = vi and 1≤ i ≤ m 2 i + m 2 + 2 if x = vi and m+2 2 ≤ i ≤ m Clearly f is infective and the edge values are consecutive numbers from 3m+2 2 to 5m 2 + 2. Theorem 21. K1,n ∪ K1,n+1, n≥ 1 is strongly 3-indexable Proof. Let V (K1,n∪K1,n+1) = {u,ui , 1≤ i ≤ n}∪{v, vi, 1≤ i ≤ n+1} and E(K1,n∪K1,n+1) = {uui : 1≤ i ≤ n} ∪ {vvi : 1≤ i ≤ n+ 1}. K. A. Germina / Eur. J. Pure Appl. Math, 3 (2010), 269-281 278 Define f : V (K1,n ∪ K1,n+1)→ {0,1,2, . . . , 2n+ 2} defined by f (u) = 0; f (ui) = 2(i+ 1), 1≤ i ≤ n f (v) = 2; f (vi) = 2i− 1, 1≤ i ≤ n+ 1. Now, clearly f (V (K1,n ∪ K1,n+1)) = {0,1,2, . . . 2n+ 2}. Also, the minimum and maximum edge value induced at the edges are f +(vv1) = 2+ f (v1) = 3 and f +(vvn+1) = 2+ f (vn+1) = 2n+ 3; Also note that f (u) + f (ui) is always even and f (v) + f (vi) is always odd. Again, f (u) + f (ui) 6= f (u) + f (u j) for all i 6= j, and f (v) + f (vi) 6= f (v) + f (v j) for all i 6= j. Hence, the induced edge values are consecutive integers from 3 to 2n+ 2, which implies f is a 3-strong indexer of K1,n ∪ K1,n+1. Theorem 21 can be expanded to the following form Theorem 22. For the integers m, n, mK1,n, is 3m−1 2 -strongly indexable, whenever m is odd. Proof. Let V (mK1,n) = {ui : 1≤ i ≤ m} ∪ {vi, j : 1≤ i ≤ m, 1≤ j ≤ n} and E(mK1,n) = {ui vi, j : 1≤ i ≤ m, 1≤ j ≤ n}. Define f : V (mK1,n)→ {0,1,2 . . . , m(n+ 1)− 1} defined by f (ui) = i − 1, 1≤ i ≤ m; f (vi,1) = ¨ i+ 3m−3 2 if 1≤ i ≤ m+1 2 i+ m−3 2 if m+1 2 < i ≤ m and f (vi, j) = f (vi,1) +m( j− 1), 1≤ i ≤ m, 2≤ j ≤ n; Clearly, f is a 3m−1 2 -strong indexer of mK1,n. Figure 7 gives the strong indexer of 5K4. Figure 7 Theorem 23. The graph mCn is m⌊ n 2 ⌋-strongly indexable for all m ≥ 1 and n≥ 3. Proof. Let both m and n be odd integers. When m = 1 the graph is an odd cycle which is k-strongly indexable. Let V (Cn) = {0,1,2, . . . , n− 1} Define the strong indexer of Cn as follows: K. A. Germina / Eur. J. Pure Appl. Math, 3 (2010), 269-281 279 f (vi) = ¨ i−2 2 if 1≡ 0(mod2) n+i−2 2 if i ≡ 1(mod2) Then f is a ⌊ n 2 ⌋-strong indexer of Cn. Now, let m≥ 3. Let V (mCn) = {ui, j : 1≤ i ≤ m, 1≤ j ≤ n} and E(mCn) = {ui, jui, j+1 : 1≤ i ≤ m, 1≤ j ≤ n− 1} ∪ {ui,nui,1 : 1≤ i ≤ m}. Define f : V (mCn)→ {0,1,2, . . . , mn} defined by f (ui,1) = i− 1, 1≤ i ≤ m and f (vi, j) =        m(⌈ n 2 ⌉+ j−2 2 ) + 2i+m−1 2 if 1≤ i ≤ m−1 2 and j even m(⌈ n 2 ⌉+ j−2 2 ) + 2i−m−1 2 if m+1 2 ≤ i ≤ m and j even m( j−i 2 + 1)− 2i if 1≤ i ≤ m−1 2 and j 6= 1 is odd m( j−i 2 + 2)− 2i if m+1 2 ≤ i ≤ m and j 6= 1 is odd It is not difficult to check that f is a strong indexer of mCn Figure 8 is strongly indexable labelling of 7C5 Figure 8 Remark 4. Invoking Theorem 3 due to Acharya [1] which state that “if G is r-regular k-strongly indexable (p,q)-graph (r ≥ 1), then q is odd” we see that the converse of Theorem 23 also holds good. From Theorem 23 and Remark 4 we have the following Theorems Theorem 24. The 2-regular graph mCn is k-strongly indexable if and only if m ≥ 1 and n ≥ 3 are odd Theorem 25. Any 3-regular graph G = (p,q) is k-strongly indexable then p ≡ 2(mod4) Proof. Assume G = (p,q) be 3-regular k-strongly indexable. Since G is 3-regular, p should necessarily be even so that either p ≡ 0(mod4) or p ≡ 2(mod4). REFERENCES 280 When p ≡ 0(mod4), p = 4t say, for some positive integer t so that q = 12t 2 = 6t If f is the strong indexer of G, then by Theorem 3 [1] Σ p−1 i=0 id(ui) = k+ k+ 1+ · · ·+ k+ q− 1 Hence, 3p(p−1) 2 = kq+ q(q−1) 2 , applying p = 4t, q = 6t ⇒ 21t(4t − 1) = 12tk+ 6t(6t − 1)⇒ t = 2k+1 2 , a contradiction. Hence, p ≡ 2(mod4). 3. Conclusion and scope Graph labelings, where the vertices and edges are assigned, real values subject to cer- tain conditions, have often been motivated by their utility to various applied fields and their intrinsic mathematical interest (logico - mathematical). Graph labelings are applied in de- termination of crystal structure from X-ray diffraction data [6, 10, 14, 15, 16], the design of certain important classes of good non periodic codes for pulse radar and missile guidance [7], and in the problem in radio-astronomy that a few movable antennae are required to be lo- cated in several successive array configurations to receive various spatial frequencies relative to some area of the sky [5]. Harper formulated this design Optimization Problem in graph labeling terms and solved some cases using this technic for minimum-confusion code design [12]. k-strongly indexable graphs are used in the construction of polygons of same internal angle and distinct sides: Using strongly k-Indexable labelings of a cycle C2n+1, one can con- struct a polygon P4n+2 with 4n+2 sides such that all the internal angles are equal and lengths of the sides are distinct [13]. ACKNOWLEDGEMENTS The author is thankful to the Department of Science & Technology, Government of India for supporting this research under the project No. SR/S4/MS:277/06. References [1] B.D. Acharya. On the construction of graphs with given constant valence- difference(s) on each of their lines, Wiss. Z. Th. Ilmenau, 23, 33-60, 1977. [2] B.D. Acharya and S.M. Hegde. Arithmetic graphs, J. Graph Theory, 14, 275-299, 1990. [3] B.D. Acharya and Germina K.A. Strongly k-indexable unicyclic graphs, Graph Theory Notes of New York,45-49, LV:2008. [4] B.D. Acharya and Germina K.A. Maximal Strongly indexable Graphs, Ars. Combinatorics, To appear. [5] J.C. Bermond, A. Kotzig, and J. Turgeon. On a combinatorial problem of antennas in radio-astronomy. Colloquium of the Mathematical Society, Janos Bolyai 18, Combina- torics, Hungary, 135-149, 1976. REFERENCES 281 [6] G.S. Bloom. Numbered undirected graphs and their uses: A survey of unifying scientific and engineering concepts and its use in developing a theory of non-redundant homo- metric sets relating to some ambiguities in x-ray diffraction analysis, Ph. D., dissertation, Univ. of Southern California, Los Angeles, 1975 [7] A.R. Eckler. The construction of missile guidance codes resistant to random interference, Bell.Syst. Tech., J, Vol. 39, 973-994, 1960 [8] H. Enomoto. A.S. Llado, T. Nakamigawa, and G. Ringel, Super edge-magic graphs, SUT J. Math., 34,105-109, 1998. [9] R. Figueroa-Centeno, R. Ichishima, and F. Muntaner-Batle. The place of super-edge-magic labellings among other classes of labellings, Discrete Math., 231, 153-168, 2001. [10] J.N. Franklin. ambiguities in the X-ray analysis of crystal structures, Acta Cryst., Vol. A 30, 698-702, Nov. 1974. [11] F. Harary. Graph Theory, Addison Wesley,Reading, Massachusetts, 1969. [12] L. H. Harper. DSIF Integrated circuit layout and Iso-perimetric Problems, JPL space pro- gram summary 37-66 Vol. 2, pp. 37-42, sept. 1970 [13] S.M. Hegde and Sudhakar Shetty. Strongly indexable graphs and applications, Discrete Mathematics, To appear. [14] J. Leech. on the representation of 1,2, . . . , n by differences, J. London math. Soc., Vol. 31, 160-169, Apr. 1956 [15] J.C. P. Miller, differences basis, three problems in additive number theory, A.D.L. Atkin and B.J. Birch, Eds, London, Academic Press,299-322, 1971. [16] G. Ringel. Labeling problems, Proceedings of the Eighth International Conference on Graph Theory, Combinatorics, Algorithms and Applications. 1996