AUSTRALASIAN JOURNAL OF COMBINATORICS

Volume 69(3) (2017), Pages 394–401

Edge irregular reflexive labeling of

prisms and wheels∗
Dushyant Tanna
School of Mathematical and Physical Sciences
The University of Newcastle
Newcastle, NSW 2308
Australia
dtanna.vmgbr@gmail.com

Joe Ryan
School of Electrical Engineering and Computer Science
The University of Newcastle
Newcastle, NSW 2308
Australia
joe.ryan@newcastle.edu.au

Andrea Semaničová-Feňovčı́ková
Department of Applied Mathematics and Informatics
Technical University, Košice
Slovak Republic
andrea.fenovcikova@tuke.sk

In memory of Mirka Miller

Abstract
For a graph G we define a k-labeling ρ such that the edges of G are
labeled with integers {1, 2, . . . , ke } and the vertices of G are labeled with
even integers {0, 2, . . . , 2kv }, where k = max{ke , 2kv }. The labeling ρ is
called an edge irregular reflexive k-labeling if distinct edges have distinct
weights, where the edge weight is defined as the sum of the label of that
edge and the labels of its ends. The smallest k for which such a labeling
exists is called the reflexive edge strength of G.
In this paper we give exact values for the reflexive edge strength for
prisms, wheels, baskets and fans.
∗
The research for this article was supported by APVV-15-0116 and by VEGA 1/0385/17.
 D. TANNA ET AL. / AUSTRALAS. J. COMBIN. 69 (3) (2017), 394–401 395

1 Introduction

Regular graphs have been an area of interest almost as long as graphs have been
studied. However, as a consequence of the Handshaking Lemma, no simple graphs
can be completely irregular. That is, no simple graph can have each vertex bearing
a distinct degree. Multigraphs however can display this property. In [4] the authors
asked, “In a loopless multigraph, determine the fewest parallel edges required to
ensure that all vertices have distinct degree.” For convenience, the problem was
recast in terms of a weighted simple graph with the edge weights representing the
number of parallel edges. The degree of a vertex was then determined by adding the
weights of the edges incident to that vertex. Then the problem became:

“Assign positive values to the edges of a simply connected graph of order

at least 3 in such a way that the graph becomes irregular. What is the
minimum value of the largest label over all such irregular assignments?”

The minimum value of the largest label is known as the irregularity strength of a
graph.
The concept of reflexive irregular multigraphs originated in [8] as a natural conse-
quence of irregular multigraphs by allowing for loops. Following the initiative of [4]
and rewording the problem as a graph labeling exercise, irregular reflexive labelings
include vertex labels representing degrees contributed by the loops. The weight of a
vertex v, denoted by wt(v), is now determined by summing the incident edge labels
and the label of v.
Previously, Bača et al. [2] proposed an irregular total labeling in which the vertices
were labelled by positive integers. For some of the results in irregular total labelings,
refer to [1, 5, 6, 7, 9]. The difference between this idea and reflexive labeling is
threefold:

1. The concept is consistent with the genesis of the problem by considering multi-
graphs with loops.

2. The vertex labels must be even non-negative integers, representing the fact
that each loop contributes 2 to the vertex degree.

3. Vertex label 0 is permissible as representing a loopless vertex.

As in the case of irregular total labelings, this new scheme allows for considering not
just vertex weights but also edge weights. An edge weight is the sum of the edge
label and the labels of the vertices incident to the edge. Thus we are able to propose
vertex irregular reflexive labelings and edge irregular reflexive labelings.
A labeling g is said to be an edge irregular reflexive k-labeling (respectively,
vertex irregular reflexive k-labeling) if, for distinct edges e and f , wtg (e) = wtg (f )
(respectively, for distinct vertices u and v, wtg (u) = wtg (v)). The smallest value
 D. TANNA ET AL. / AUSTRALAS. J. COMBIN. 69 (3) (2017), 394–401 396

of k for which such labelings exist is called the reflexive edge strength (respectively,
reflexive vertex strength).
In this paper we find exact values of reflexive edge strength for prisms, wheels,
baskets and fans. Due to the similarity of the labeling schemes, many of the theorems
and proofs presented here will be similar to those given in the papers [2, 3]; however,
respective strengths (on the same graph) may be different. For example, res(D10 ) =
10, while in [3] it was shown that tes(D10 ) = 11.
When proving the subsequent result, we will frequently use the following lemma
that was proved in [8].

Lemma 1.1 [8] For every graph G,

⎧ 
⎨ |E(G)|
3
if |E(G)| ≡ 2, 3 (mod 6),
res(G) ≥  
⎩ |E(G)|
+1 if |E(G)| ≡ 2, 3 (mod 6).
3

The lower bound for res(G) follows from the fact that the minimal edge weight
under an edge irregular reflexive labeling is 1 and the minimum of the maximal edge
weights, that is, |E(G)|, can be achieved only as the sum of 3 numbers from which
at least 2 are even.

2 Edge Irregular Reflexive Labeling of Prisms

The prism Dn , n ≥ 3, is a trivalent graph which can be defined as the Cartesian

product P2 Cn of a path on two vertices with a cycle on n vertices. We denote
the vertex set and the edge set of Dn by V (Dn ) = {xi , yi : i = 1, 2, . . . , n} and
E(Dn ) = {xi xi+1 , yi yi+1 , xi yi : i = 1, 2, . . . , n}, where indices are taken modulo n.

Theorem 2.1 For n ≥ 3,


n+1 if n is odd,
res(Dn ) =
n if n is even.

Proof: As the prism Dn has 3n edges, immediately from Lemma 1.1 we get that
res(Dn ) ≥ n + 1 for n odd and res(Dn ) ≥ n for n even.
Let k = n for n even and let k = n + 1 for n odd. We define the labeling f of Dn
such that:

f (xi ) = 0 i = 1, 2, . . . , n,
f (yi ) = k i = 1, 2, . . . , n,
f (xi xi+1 ) = f (yi yi+1 ) = i i = 1, 2, . . . , n − 1,
f (x1 xn ) = f (y1 yn ) = n,
f (xi yi ) = i i = 1, 2, . . . , n.
 D. TANNA ET AL. / AUSTRALAS. J. COMBIN. 69 (3) (2017), 394–401 397

Evidently f is a k-labeling. The edge weights of the edges in Dn under the labeling
f are the following:

wtf (xi xi+1 ) =0 + i + 0 = i for i = 1, 2, . . . , n − 1,

wtf (x1 xn ) =0 + n + 0 = n,
wtf (xi yi ) =0 + i + k = k + i for i = 1, 2, . . . , n,
wtf (yi yi+1 ) =k + i + k = 2k + i for i = 1, 2, . . . , n − 1,
wtf (y1 yn ) =k + n + k = 2k + n.

This means that for n odd, {wtf (e) : e ∈ E(Dn )} = {1, 2, . . . , n, n+ 2, n+ 3, . . . , 2n+
1, 2n + 3, 2n + 4, . . . , 3n + 2}, and for n even, {wtf (e) : e ∈ E(Dn )} = {1, 2, . . . , 3n}.
Thus the edge weights are distinct, that is, f is a edge irregular reflexive k-labeling
of a prism Dn . 

3 Edge Irregular Reflexive Labeling of Wheels

The wheel Wn , n ≥ 3, is a graph obtained by joining all vertices of Cn to a further

vertex called the centre. We denote the vertex set and the edge set of Wn by V (Wn ) =
{x, xi : i = 1, 2, . . . , n} and E(Wn ) = {xi xi+1 , xxi : i = 1, 2, . . . , n}, where indices are
taken modulo n. We prove the following result for wheels.

Theorem 3.1 For n ≥ 3,

⎧
⎪
⎨4 if n = 3,
res(Wn ) =  2n  if n ≡ 0, 2 (mod 3) and n ≥ 5,
⎪
⎩ 2n
3
 3 +1 if n ≡ 1 (mod 3).

Proof: According to the fact that the wheel Wn has 2n edges, using Lemma 1.1
we obtain the following lower bound for the wheel: res(Wn ) ≥ k =  2n
3
 if n ≡ 0, 2
2n
(mod 3) and res(Wn ) ≥ k =  3  + 1 if n ≡ 1 (mod 3). It is easy to see that k is
even.
Thus res(W3 ) ≥ 2. If res(W3 ) ≤ 3 then the vertices of W3 can be labeled only with
0’s or 2’s and the set of all possible edge weights is a subset of the set {1, 2, . . . , 7}. As
the edge weights 1 and 2 could be realizable only as 1=0+1+0; 2=0+2+0, it follows
that five edges have end vertex labeled with 0. However, this is a contradiction as
the edge weights 6 and 7 can be realizable only as 6=2+2+2 and 7=2+3+2. Thus
res(W3 ) ≥ 4. The corresponding labelings for Wn , n = 3, 4, 5, 6, are illustrated in
Figure 1.
 D. TANNA ET AL. / AUSTRALAS. J. COMBIN. 69 (3) (2017), 394–401 398

2 4 3 4
0 2 0 2 1
2 3 3 2 3 4
2 0 4 2 4
1 4 2 4 4 0 2 2 4
3 3
1 4 2 2 2 1
1 3 2 1
2 2 2 3
0 1 2 0 0
2 1 0 1 0
0 3 2

Figure 1: The reflexive edge irregular k-labeling of wheels Wn , n = 3, 4, 5, 6.

For n ≥ 7 we define a total labeling of Wn such that

f (x) = k,
⎧
⎪
⎪ 0 i = 1, 2, . . . , k − 1,
⎪
⎨2 i = k,
f (xi ) =
⎪
⎪ k i = k + 1, k + 2, . . . , n − 1,
⎪
⎩
k − 2 i = n,
⎧
⎪
⎪ i i = 1, 2, . . . , k − 1,
⎪
⎨k − 2 i = k,
f (xxi ) =
⎪
⎪n − 2k + 1 + i i = k + 1, k + 2, . . . , n − 1,
⎪
⎩
5 i = n,

⎧
⎪
⎪i i = 1, 2, . . . , k − 2,
⎪
⎪
⎪
⎪k−3 i = k − 1,
⎪
⎪
⎨k − 1 i = k,
f (xi xi+1 ) =
⎪
⎪i−k+3 i = k + 1, k + 2, . . . , n − 2,
⎪
⎪
⎪
⎪ i = n − 1,
⎪
⎪
4
⎩
2 i = n.
 D. TANNA ET AL. / AUSTRALAS. J. COMBIN. 69 (3) (2017), 394–401 399

Evidently, for n ≥ 7, f is a k-labeling. Now we calculate the edge weights.

wtf (xi xi+1 ) =0 + i + 0 = i for i = 1, 2, . . . , k − 2,

wtf (xk−1 xk ) =0 + (k − 3) + 0 = k − 1,
wtf (xk xk+1 ) =2 + (k − 1) + k = 2k + 1,
wtf (xi xi+1 ) =k + (i − k + 3) + k = k + 3 + i
for i = k + 1, k + 2, . . . , n − 2,
wtf (xn−1 xn ) =k + 4 + (k − 2) = 2k + 2,
wtf (xn x1 ) =(k − 2) + 2 + 0 = k,
wtf (xxi ) =k + i + 0 = k + i for i = 1, 2, . . . , k − 1,
wtf (xxk ) =k + (k − 2) + 2 = 2k,
wtf (xxi ) =k + (n − 2k + 1 + i) + k = n + 1 + i
for i = k + 1, k + 2, . . . , n − 1,
wtf (xxn ) =k + 5 + (k − 2) = 2k + 3.

It is easy to check that the edge weights are from the set {1, 2, . . . , 2n}. This con-
cludes the proof. 

A fan Fn is obtained from wheel Wn if one rim edge, say x1 xn , is deleted. A

basket Bn is obtained by removing a spoke, say xxn , from wheel Wn . Before we give
the exact value of reflexive edge strength of fans and baskets, we give the following
lemma.

Lemma 3.2 Let e be an arbitrary edge in G. Then

res(G − {e}) ≤ res(G).

Proof: The proof is trivial. 

Theorem 3.3 For n ≥ 3,

⎧
⎪
⎨3 if n = 3,
res(Fn ) = res(Bn ) = 4 if n = 4,
⎪
⎩ 2n
3 if n ≥ 5.

Proof: Using similar arguments as in the proof of Theorem 3.1, we find that
res(F3 ) ≥ 3 and res(F4 ) ≥ 4. The corresponding labeling for F3 can be obtained
from the labeling illustrated for W3 ; see Figure 1, when the edge labeled with 4 is
deleted. For the fan F4 we can delete an arbitrary rim edge.
For n ≥ 5, combining Lemmas 1.1 and 3.2 we have res(Fn ) = res(Wn ) =  2n
3
 for
n ≡ 0, 2 (mod 3) and  2n
3
 ≤ res(Fn ) ≤  2n
3
 + 1 for n ≡ 1 (mod 3).
 D. TANNA ET AL. / AUSTRALAS. J. COMBIN. 69 (3) (2017), 394–401 400

Let n ≡ 1 (mod 3), n ≥ 7. Then the number k =  2n

3
 is odd. We define a k-labeling
of Fn such that:
f (x) = k − 1,
⎧
⎪
⎪k − 1 i = 1,
⎪
⎪
⎪
⎪
⎨k − 3 i = 2,
f (xi ) = 0 i = 3, 4, . . . , k,
⎪
⎪
⎪
⎪2 i = k + 1,
⎪
⎪
⎩k − 1 i = k + 2, k + 3, . . . , n,
⎧
⎪
⎪4 i = 1,
⎪
⎪
⎪
⎪ i = 2,
⎨5
f (xxi ) = i − 2 i = 3, 4, . . . , k,
⎪
⎪
⎪
⎪k−3 i = k + 1,
⎪
⎪
⎩2i − 2k + 1 i = k + 2, k + 3, . . . , n,
⎧
⎪
⎪4 i = 1,
⎪
⎪
⎪
⎪2 i = 2,
⎪
⎪
⎨i − 2 i = 3, 4, . . . , k − 1,
f (xi xi+1 ) =
⎪
⎪k−4 i = k,
⎪
⎪
⎪
⎪k−2 i = k + 1,
⎪
⎪
⎩
2i − 2k + 2 i = k + 2, k + 3, . . . , n − 1.
It is not difficult to check that the edge weights are distinct numbers from the set
{1, 2, . . . , 2n − 1}.
The proof for the basket Bn can be done analogously as for the fan. Evidently
V (Bn ) = V (Fn ) and E(Bn ) = E(Fn ) ∪ {x1 xn } − {xxn }. For n ≡ 1 (mod 3), n ≥ 7,
the following  2n
3
-labeling g of Bn , defined such that g(y) = f (y) for y ∈ V (Fn ) or
y ∈ E(Fn ) − {xxn } and g(x1 xn ) = f (xxn ), has the desired properties. 

4 Conclusion

In this paper we have described the reflexive edge strength for several classes of
graphs. For further investigation we suggest solving the corresponding problem for
the reflexive vertex strength of these graphs.

References

[1] M. Anholcer and C. Palmer, Irregular Labelings of Circulant Graphs, Discrete

Math. 312(23) (2012), 3461–3466.
[2] M. Bača, S. Jendrol’, M. Miller and J. Ryan, Total Irregular Labelings, Discrete
Math. 307 (2007), 1378–1388.
 D. TANNA ET AL. / AUSTRALAS. J. COMBIN. 69 (3) (2017), 394–401 401

[3] M. Bača and M. K. Siddiqui, Total Edge Irregularity Strength of Generalized

Prism, Appl. Math. Comput. 235 (2014), 168–173.

[4] G. Chartrand, M. S. Jacobson, J. Lehel, O. R. Oellermann, S. Ruiz and F. Saba,

Irregular Networks, Congr. Numer. 64 (1988), 187–192.

[5] R. J. Faudree and J. Lehel, Bounds on the Irregularity Strength of Regular

Graphs, Combinatorics. Colloq. Math. Soc. János Bobyai 52 (1987), 247–256.

[6] J. A. Gallian, Graph Labeling, Electr. J. Combin., Dynamic Survey 16 (2013),

#DS6.

[7] S. Nurdin, E. T. Baskoro, A. N. M. Salman and N. N. Gaos, On the Total Vertex

Irregularity Strength of Trees, Discrete Math. 310 (2010), 3043–3048.

[8] J. Ryan, B. Munasinghe and D. Tanna, Reflexive Irregular Labelings, (preprint).

[9] M. K. Siddiqui, On the Total Edge Irregularity Strength of a Categorical Product

of a Cycle and a Path, AKCE J. Graphs Combin. 9(1) (2012), 43–52.

(Received 15 Nov 2016; revised 3 July 2017)