
For a simple graph G=(V,E) with the vertex set V(G) and the edge set E(G), a vertex labeling φ:V(G)→{1,2,…,k} is called a k-labeling. The weight of an edge under the vertex labeling φ is the sum of the labels of its end vertices and the modular edge-weight is the remainder of the division of this sum by |E(G)|. A vertex k-labeling is called a modular edge irregular if for every two different edges their modular edge-weights are different. The maximal integer k minimized over all modular edge irregular k-labelings is called the modular edge irregularity strength of G. In the paper we estimate the bounds on the modular edge irregularity strength and for caterpillar, cycle, friendship graph and n-sun we determine the precise values of this parameter that prove the sharpness of the lower bound.
Citation: Ali N. A. Koam, Ali Ahmad, Martin Bača, Andrea Semaničová-Feňovčíková. Modular edge irregularity strength of graphs[J]. AIMS Mathematics, 2023, 8(1): 1475-1487. doi: 10.3934/math.2023074
[1] | Martin Bača, Muhammad Imran, Zuzana Kimáková, Andrea Semaničová-Feňovčíková . A new generalization of edge-irregular evaluations. AIMS Mathematics, 2023, 8(10): 25249-25261. doi: 10.3934/math.20231287 |
[2] | Gohar Ali, Martin Bača, Marcela Lascsáková, Andrea Semaničová-Feňovčíková, Ahmad ALoqaily, Nabil Mlaiki . Modular total vertex irregularity strength of graphs. AIMS Mathematics, 2023, 8(4): 7662-7671. doi: 10.3934/math.2023384 |
[3] | Muhammad Amir Asif, Rashad Ismail, Ayesha Razaq, Esmail Hassan Abdullatif Al-Sabri, Muhammad Haris Mateen, Shahbaz Ali . An application on edge irregular reflexive labeling for $ m^t $-graph of cycle graph. AIMS Mathematics, 2025, 10(1): 1300-1321. doi: 10.3934/math.2025060 |
[4] | Ibrahim Tarawneh, Roslan Hasni, Ali Ahmad, Muhammad Ahsan Asim . On the edge irregularity strength for some classes of plane graphs. AIMS Mathematics, 2021, 6(3): 2724-2731. doi: 10.3934/math.2021166 |
[5] | Fatma Salama, Randa M. Abo Elanin . On total edge irregularity strength for some special types of uniform theta snake graphs. AIMS Mathematics, 2021, 6(8): 8127-8148. doi: 10.3934/math.2021471 |
[6] | Mohamed Basher . On the reflexive edge strength of the circulant graphs. AIMS Mathematics, 2021, 6(9): 9342-9365. doi: 10.3934/math.2021543 |
[7] | Mohamed Basher . Edge irregular reflexive labeling for the $ r $-th power of the path. AIMS Mathematics, 2021, 6(10): 10405-10430. doi: 10.3934/math.2021604 |
[8] | Kooi-Kuan Yoong, Roslan Hasni, Gee-Choon Lau, Muhammad Ahsan Asim, Ali Ahmad . Reflexive edge strength of convex polytopes and corona product of cycle with path. AIMS Mathematics, 2022, 7(7): 11784-11800. doi: 10.3934/math.2022657 |
[9] | Wei Gao, Zahid Iqbal, Shehnaz Akhter, Muhammad Ishaq, Adnan Aslam . On irregularity descriptors of derived graphs. AIMS Mathematics, 2020, 5(5): 4085-4107. doi: 10.3934/math.2020262 |
[10] | Sadik Delen, Ismail Naci Cangul . Effect of edge and vertex addition on Albertson and Bell indices. AIMS Mathematics, 2021, 6(1): 925-937. doi: 10.3934/math.2021055 |
For a simple graph G=(V,E) with the vertex set V(G) and the edge set E(G), a vertex labeling φ:V(G)→{1,2,…,k} is called a k-labeling. The weight of an edge under the vertex labeling φ is the sum of the labels of its end vertices and the modular edge-weight is the remainder of the division of this sum by |E(G)|. A vertex k-labeling is called a modular edge irregular if for every two different edges their modular edge-weights are different. The maximal integer k minimized over all modular edge irregular k-labelings is called the modular edge irregularity strength of G. In the paper we estimate the bounds on the modular edge irregularity strength and for caterpillar, cycle, friendship graph and n-sun we determine the precise values of this parameter that prove the sharpness of the lower bound.
Throughout this paper, G=(V,E) is a simple graph with the vertex set V(G) and the edge set E(G). Chartrand et al. in [1] introduced an edge k-labeling ψ:E(G)→{1,2,…,k} of a graph G such that the sum of the labels of edges incident with a vertex is different for all the vertices of G. Such labelings were called irregular assignments and the irregularity strength s(G) of a graph G is known as the maximal integer k, minimized over all irregular assignments. If no such assignment exists then s(G)=∞. Obviously, s(G)<∞ if and only if G contains no isolated edge and has at most one isolated vertex. The irregularity strength has attracted much attention [2,3,4,5,6,7,8].
Motivated by these papers, Ahmad et al. in [9] defined an edge irregular k-labeling of a graph G to be a vertex labeling φ:V(G)→{1,2,…,k} such that the edge-weights wtφ(uv)=φ(u)+φ(v) are different for all edges, that is wtφ(uv)≠wtφ(u′v′) for all different edges uv,u′v′∈E(G). Furthermore, they defined the edge irregularity strength, es(G), of G as the minimum k for which the graph G has an edge irregular k-labeling.
For a simple graph with maximum degree Δ(G) in [9] is estimated a lower bound of the edge irregularity strength in the form
es(G)≥max{⌈|E(G)|+12⌉,Δ(G)}. | (1.1) |
For several families of graphs, the exact value of the edge irregularity strength has been determined, namely for paths, stars, double stars and cartesian product of two paths in [9], for Toeplitz graphs in [10] and for complete m-ary trees in [11]. Other results on the edge irregularity strength and its variations can be found in [12,13,14,15].
The modular irregular labeling as a modification of the irregular assignment was introduced in [16]. A function ψ:E(G)→{1,2,…,k} of a graph G of order n is called a modular irregular labeling if the weight function λ:V(G)→Zn defined by λ(u)=wtψ(u)=∑ψ(uv) is bijective and is called as the modular weight of the vertex u, where Zn is the group of integers modulo n and the sum is over all vertices v adjacent to u. The modular irregularity strength, ms(G), is defined as the minimum k for which G has a modular irregular labeling using labels at most k. If there is no such labeling for the graph G then the value of ms(G) is defined as ∞.
Clearly, every modular irregular labeling of a graph with no component of order at most two is also its irregular labeling. This gives a lower bound of the modular irregularity strength, i.e., if G is a graph with no component of order at most two then
s(G)≤ms(G). | (1.2) |
The exact values of the modular irregularity strength have been determined for certain families of graphs, namely for paths, cycles and stars [16], for fan graphs [17], wheels [18] and friendship graphs [19].
Motivated by the modular irregular labeling and the edge irregular labeling, in this paper we study modular edge irregular k-labelings.
For a graph G=(V,E) of size m we define a vertex labeling φ:V(G)→{1,2,…,k} to be a modular edge irregular k-labeling if the edge-weight function ρ:E(G)→Zm defined by ρ(uv)=wtφ(uv)=φ(u)+φ(v) is bijective and is called as the modular edge-weight of the edge uv, where Zm is the group of integers modulo m. The modular edge irregularity strength, mes(G), is defined as the minimum k for which G has a modular edge irregular k-labeling. If there is no such labeling for the graph G, then the value of mes(G) is defined as ∞.
Note that Muthugurupackiam and Ramya in [20,21] introduced a definition on even (odd) modular edge irregular labeling, where the set of modular edge-weights contains only even or odd integers.
The main aim of the paper is to show some estimations on the modular edge irregularity strength, investigate the existence of modular edge irregular k-labelings for several families of graphs and determine the precise values of the modular edge irregularity strength that prove the sharpness of the presented lower bound.
Directly from the definition it follows that every modular edge irregular k-labeling of a graph is also its edge irregular k-labeling. Thus, for any simple graph G holds
es(G)≤mes(G). | (2.1) |
In general, the converse of (2.1) does not hold. However, the validity of the following claim is obvious.
Theorem 2.1. Let G be a simple graph with es(G)=k. If edge-weights under the corresponding edge irregular k-labeling constitute a set of consecutive integers, then
es(G)=mes(G)=k. | (2.2) |
In [9], the precise value of the edge irregularity strength for paths and stars are determined as follows:
Theorem 2.2. [9] Let Pn be a path on n vertices, n≥2. Then es(Pn)=⌈n2⌉.
Theorem 2.3. [9] Let K1,n be a star on n+1 vertices, n≥1. Then es(K1,n)=n.
The previous two theorems prove that the lower bound of the edge irregularity strength in (1.1) is tight. There is described the existence of the edge irregular ⌈n2⌉-labeling (for paths) and the existence of the edge irregular n-labeling (for stars), where the corresponding edge-weights in both cases constitute the set of consecutive integers. According to Theorem 2.1 we have:
Corollary 2.1. Let Pn be a path on n≥2 vertices. Then mes(Pn)=⌈n2⌉.
Corollary 2.2. Let K1,n be a star on n+1 vertices, n≥1. Then mes(K1,n)=n.
These corollaries prove the tightness of the lower bound of the modular edge irregularity strength given in (2.1).
In the next theorem we characterize the modular edge irregularity strength of cycles.
Theorem 2.4. Let Cn be a cycle on n vertices, n≥3. Then
mes(Cn)={⌈n2⌉,ifn≡1(mod4),⌈n2⌉+1,ifn≡0,3(mod4),∞,ifn≡2(mod4). |
Proof. Let V(Cn)={vi:1≤i≤n} and E(Cn)={vivi+1:1≤i≤n}, where vn+1=v1. Faudree et al. in [22] described irregular assignments f for cycles and proved that
s(Cn)={⌈n2⌉,ifn≡1(mod4),⌈n2⌉+1,otherwise. |
We define a vertex labeling ψ of Cn such that for 1≤i≤n
ψ(vi)=f(vivi+1). |
Thus each edge label becomes the vertex label and we get an edge irregular labeling of the cycle. Since for every n≢2(mod4) in Faudree's irregular assignments of Cn the vertex-weights constitute a set of consecutive integers then according to Theorem 2.1 it implies that
mes(Cn)={⌈n2⌉,ifn≡1(mod4),⌈n2⌉+1,ifn≡0,3(mod4). |
For the remaining case when n≡2(mod4), i.e., n=4h+2 for some positive integer h≥1, let us suppose that the cycle C4h+2 admits a modular edge irregular labeling φ. It means that the sum of all vertex labels used to calculate the edge-weights of C4h+2 is congruent to the sum of modular edge-weights. Hence
24h+2∑i=1φ(vi)≡0+1+⋯+(4h+1)=(4h+2)(4h+1)2=(2h+1)(4h+2−1)≡(2h+1)(−1)≡2h+1(mod(4h+2)). |
A contradiction as 2h+1 is odd.
A caterpillar is a graph derived from a path by hanging any number of leaves from the vertices of the path. The caterpillar can be seen as a sequence of stars K1,n1∪K1,n2∪⋯∪K1,nr, where each K1,ni is a star with central vertex ci and ni leaves for i=1,2,…,r, and the leaves of K1,ni include ci−1 and ci+1, for i=2,3,…,r−1. In [23] the authors denote the caterpillar as Sn1,n2,…,nr, where the vertex set is V(Sn1,n2,…,nr) = {ci:1≤i≤r}∪r−1⋃i=2{vji:2≤j≤ni−1} ∪{vj1:1≤j≤n1−1}∪{vjr:2≤j≤nr}, and the edge set is E(Sn1,n2,…nr)={cici+1:1≤i≤r−1}∪r−1⋃i=2{civji:2≤j≤ni−1} ∪{c1vj1:1≤j≤n1−1}∪{crvjr:2≤j≤nr}, see Figure 1. Thus |V(Sn1,n2,…,nr)|=r∑i=1ni−r+2 and |E(Sn1,n2,…,nr)|=r∑i=1ni−r+1.
Let Sn1,n2,…,nr be a caterpillar and No=⌈r2⌉∑i=1n2i−1 and Ne=⌊r2⌋∑i=1n2i.
Theorem 2.5. Let k=max{No−⌈r2⌉+1,Ne−⌊r2⌋+1}. The caterpillar Sn1,n2,…,nr admits a modular edge irregular k-labeling.
Proof. We are using an idea of Kotzig and Rosa [24] that any caterpillar can be realized in the plane so that its vertices are displaced in two rows, the edges joining these vertices from different rows and no two edges cross. Let {A,B} be a bipartition of the vertex set of the caterpillar Sn1,n2,…,nr. Let a1,a2,…,aNo−⌈r2⌉+1 be the vertices in the partition A, ordered from left to right, and let b1,b2,…,bNe−⌊r2⌋+1 be the vertices in the partition B, ordered from left to right.
Define a vertex labeling φ of Sn1,n2,…,nr in the following way.
φ(ai)=i,if1≤i≤No−⌈r2⌉+1,φ(bj)=j,if1≤j≤Ne−⌊r2⌋+1. |
It is not complicated to see that the maximal vertex label is k=max{No−⌈r2⌉+1,Ne−⌊r2⌋+1} and the edge-weights create the integer interval from 2 to |E(Sn1,n2,…,nr)|+1=No+Ne−r+2. Thus, the vertex labeling φ is a modular edge irregular k-labeling.
Immediately from (1.1) and Theorem 2.5 we obtain the next theorem.
Theorem 2.6. Let Sn1,n2,…,nr be a caterpillar. Then
max{⌈No+Ne−r+22⌉,ni:1≤i≤r}≤es(Sn1,n2,…,nr)≤mes(Sn1,n2,…,nr)≤max{No−⌈r2⌉+1,Ne−⌊r2⌋+1}. |
Note that if r is even and No=Ne+α, where α∈{−1,0,1}, or if r is odd and No=Ne+β, where β∈{0,1,2} then
max{⌈No+Ne−r+22⌉,ni:1≤i≤r}=max{No−⌈r2⌉+1,Ne−⌊r2⌋+1}. |
Thus we get the following result.
Corollary 2.3. Let Sn1,n2,…,nr be a caterpillar. If r is even and No=Ne+α, where α∈{−1,0,1}, or if r is odd and No=Ne+β, where β∈{0,1,2} then
es(Sn1,n2,…,nr)=mes(Sn1,n2,…,nr)=⌈No+Ne−r+22⌉. |
In compliance with (2.1) the previous corollary proves the sharpness of the lower bound of the modular edge irregularity strength of caterpillars.
Marr and Wallis in their book [25] define an n-sun Sn as a cycle Cn with an edge terminating in a vertex of degree 1 attached to each vertex.
Theorem 2.7. Let Sn be an n-sun on 2n vertices, n≥3. Then
es(Sn)=mes(Sn)=n+1. |
Proof. Let V(Sn)={vi,ui:1≤i≤n} and E(Sn)={vivi+1,viui:1≤i≤n}, where vn+1=v1. According to (1.1) and (2.1) we have the following lower bound n+1≤es(Sn)≤mes(Sn). To prove that n+1 is also the upper bound we distinguish two cases according to the parity of n.
Case 1. For n≥3 odd, we construct a vertex labeling φ as follows
φ(vi)={i+12,ifiisodd,n+1+i2,ifiiseven,φ(ui)={1,ifiisodd,i≠n,n+1,ifiisevenandi=n. |
The labels of vertices receive the integers from 1 to n+1 and for the weights of edges we get
wtφ(vivi+1)={n+32+i,if1≤i≤n−1,n+32,ifi=n,wtφ(viui)={i+32,ifiodd,i≠n,3n+32,ifi=n,3n+3+i2,ifieven. |
One can easily check that under the vertex labeling φ the edges of the n-sun admit the consecutive weights from 2 to 2n+1. Thus, the vertex labeling φ is a modular edge irregular (n+1)-labeling of Sn for n odd.
Case 2. For n≥4 even, we consider a vertex labeling ψ defined such that
ψ(vi)={i,if1≤i≤n−1,n+1,ifi=n,ψ(ui)={i,if1≤i≤n2,i+2,ifn2+1≤i≤n−3,n,ifi=n−2,n−1,n. |
The maximal vertex labels is n+1 and the edge-weights are the following
wtψ(vivi+1)={2i+1,if1≤i≤n−2,2n,ifi=n−1,n+2,ifi=n,wtψ(viui)={2i,if1≤i≤n2,2i+2,ifn2+1≤i≤n−3,i+n,ifi=n−2,n−1,2n+1,ifi=n. |
Thus the weights of edges are consecutive numbers from 2 to 2n+1. This means that the vertex labeling ψ is a modular edge irregular (n+1)-labeling of Sn for n even.
Thus
mes(Sn)=n+1 |
for every n≥3.
A friendship graph fn, n≥1, is a set of n triangles having a common central vertex, and otherwise disjoint. Let w denote the central vertex. For the ith triangle, 1≤i≤n, let ui and vi denote the other two vertices. Thus fn contains 2n+1 vertices w,ui,vi, 1≤i≤n and 3n edges wui, wvi, uivi, 1≤i≤n.
As |E(fn)|=3n and the maximum degree Δ(fn)=2n then (1.1) implies that es(fn)≥2n. However, if under a vertex labeling φ of fn there exist two vertices u,v∈V(fn) such that φ(u)=φ(v) then using the fact that u and v have just one common neighbor, say z∈V(fn), we obtain wtφ(uz)=φ(u)+φ(z)=φ(v)+φ(z)=wtφ(vz). It means that under any edge irregular labeling of the friendship graph fn all the vertex values must be different. That way
es(fn)≥2n+1 | (2.3) |
and according to (2.1) we also have a lower bound of the modular edge irregularity strength for fn.
The following theorem shows that the lower bound of the edge irregularity strength of fn in (2.3) is acquired just for a few values of n. A similar idea of the proving was used in [26] for showing the edge-antimagicness of friendship graphs with difference d=1.
Theorem 2.8. The friendship graph fn of order 2n+1 admits an edge irregular (2n+1)-labeling with consecutive edge-weights if and only if n∈{1,3,4,5,7}.
Proof. Suppose that there exists a vertex labeling φ:V(G)→{1,2,…,2n+1} such that the edge-weights of fn successively attain consecutive values x,x+1,…,x+3n−1. If φ(w)=t, 1≤t≤2n+1, then the set of vertex labels under the vertex labeling φ can be partitioned into three subsets A={1,2,…,t−1}, B={t} and C={t+1,t+2,…,2n+1}. Thus φ(V(fn))=A∪B∪C.
We are able to see that weights of edges wui and wvi, 1≤i≤n, constitute the set W = {t+1, t+2,…,2t−1,2t+1,2t+2,…,2n+t+1}. It is not difficult to see that the set of edge-weights WA = {x,x+1,…,t} can only be created as sums of two distinct values in the set A and the set of edge-weights WB={2n+t+2,2n+t+3,…,x+3n−1} can only be created as sums of two distinct values in the set B. The sets WA and WB contain consecutive integers each while the set W has a gap. The missing edge-weight 2t can be obtained only as sum of a value from the set A, say a, and a value from the set B, say b. Thus in the set A−{a} we have t−2 numbers and the corresponding set of edge-weights WA={x,x+1,…,t} has the cardinality |WA|=t−22, i.e., t must be even. This also implies that x=t2+2.
Since the sum of all the values in the set A−{a} is equal to the sum of all the edge-weights in the set WA={t2+2,t2+3,…,t}, then
t(t−1)2−a=(3t+4)(t−2)8. | (2.4) |
As a∈A then 1≤a≤t−1 and from (2.4) we get
8≤t2−2t+8≤8t−8, |
which is equivalent to
t2−2t≥0andt2−10t+16≤0. |
As t must be even the previous inequalities give
t∈{2,4,6,8}. | (2.5) |
In the computation of the edge-weights of fn, the label t of the vertex w is used 2n times and the labels of the vertices ui and vi, 1≤i≤n, are used twice each and the sum of the all edge-weights of fn is equal to the sum of all the vertex labels, used to calculate the edge-weights. Then we get the following equation
2n∑i=1(φ(ui)+φ(vi))+2nφ(w)=n∑i=1(wtφ(wui)+wtφ(wvi))+n∑i=1wtφ(uivi), |
which gives
(2n+2)(2n+1)+2t(n−1)=3n(3n+t+3)2, |
and it immediately follows that
0=n2−n(3+t)+4(t−1). | (2.6) |
According to (2.5) from the Eq (2.6) we receive all the possible integer values of the parameters n, x and t as follows:
(n,x,t)∈{(1,3,2),(3,4,4),(4,3,2),(4,4,4),(4,5,6),(4,6,8),(5,5,6),(7,6,8)}. | (2.7) |
For the converse, it is not difficult to find the corresponding edge irregular (2n+1)-labelings of fn for parameters (n,x,t) from (2.7). Figures 2–4 illustrate searched (2n+1)-labelings of fn, where integers in italic font represent the edge-weights. This concludes the proof.
Applying Theorem 2.1 to Theorem 2.8 we achieve the following corollary.
Corollary 2.4. Let fn be a friendship graph on 2n+1 vertices. If n∈{1,3,4,5,7} then mes(fn)=2n+1.
The next theorem gives a condition when no modular edge irregular labeling of fn exists.
Theorem 2.9. If fn is a friendship graph on 2n+1 vertices and n≡2(mod4), then fn has no modular edge irregular labeling and mes(fn)=∞.
Proof. Assume that the friendship graph fn on 2n+1 vertices admits a modular edge irregular labeling φ. Then the sum of all vertex labels used to calculate the edge-weights of fn is congruent to the sum of modular edge-weights. It means if D=2n∑i=1(φ(ui)+φ(vi))+2nφ(w) then
D≡3n−1∑s=0s(mod3n), |
where 3n−1∑s=0s=3n(3n−1)2.
If n≡2(mod4), i.e., n=4h+2 for some positive integer h≥1, then using properties of congruence we get
D≡(12h+6)(12h+5)2=(6h+3)(12h+6−1)≡(6h+3)(−1)≡6h+3(mod(12h+6)). |
This contradicts the fact that D is even.
The next theorem provides lower and upper bounds on the parameter mes(fn) for n odd.
Theorem 2.10. For the friendship graph fn of order 2n+1, n≥9 odd, we have
2n+1≤mes(fn)≤5n+12. |
Proof. The lower bound follows from (2.1) and (2.3). To see the upper bound let us define a vertex labeling φ of fn, for n≥9 odd, in the following way
φ(ui)= i,3n+2−i2if1≤i≤n,φ(vi)={3n+2−i2,iifiisodd,4n+2−i2,ifiiseven,φ(w)= 5n+12. |
Thus the labels of vertices ui,vi, 1≤i≤n are the consecutive integers from 1 to 2n and the vertex w receives the maximum label 5n+12. Then for the weights of the edges uivi, 1≤i≤n, we have
wtφ(uivi)={3n+2+i2,ifiisodd,4n+2+i2,ifiiseven, |
and for the weights of the edges wui and wvi, 1≤i≤n, we get
wtφ(wui)= 5n+12+i,wtφ(wvi)={8n+3−i2,ifiisodd,9n+3−i2,ifiiseven. |
We can observe that the edge-weights of fn, under the vertex labeling φ, form the sequence of consecutive integers 3n+32,3n+52,…,9n+12.
In the light of Theorem 2.1, it follows that the vertex labeling φ is a modular edge irregular 5n+12-labeling of fn and it proves that mes(fn)≤5n+12 for n≥9 odd. Thus, we arrive at the desired result.
In this paper is introduced a new graph invariant, namely the modular edge irregularity strength and estimated its lower bound. For several families of graphs (paths, stars, cycles and n-suns) are determined the precise values of the modular edge irregularity strength that prove the sharpness of this lower bound. For caterpillars Sn1,n2,…,nr realized in the plane as a balanced (respectively almost balanced) bipartite graph we proved that if r is even and No=Ne+α, where α∈{−1,0,1}, or if r is odd and No=Ne+β, where β∈{0,1,2} then mes(Sn1,n2,…,nr)=⌈No+Ne−r+22⌉. For the other cases we proved only an upper bound for the modular edge irregularity strength. Therefore we propose the following open problem.
Open Problem 3.1. For the caterpillar Sn1,n2,…,nr determine the exact value of the modular edge irregularity strength for No=Ne+γ for every integer γ.
For the friendship graph fn of order 2n+1 was proved that
mes(fn){=2n+1,ifn∈{1,3,4,5,7},=∞,ifn≡2(mod4),≤5n+12,ifn≥9odd. |
For further research, we suggest the following open problems.
Open Problem 3.2. For the friendship graph fn of order 2n+1 and n≥9 odd, determine the exact value of the modular edge irregularity strength.
It is a matter of algebraic argumentation to show that there does not exist a modular edge irregular 17-labeling of f8. Thus according to Figure 5 we get that mes(f8)=18. The remaining open case for the existence of a modular edge irregular labeling of fn is n≡0(mod4) for n≥12. Therefore we propose
Open Problem 3.3. For the friendship graph fn of order 2n+1, n≥12 and n≡0(mod4), determine the exact value of the modular edge irregularity strength.
The research for this article was supported by the Slovak Research and Development Agency under the contract APVV-19-0153 and by VEGA 1/0243/23.
In this article, all authors disclaim any conflict of interest.
[1] | G. Chartrand, M. Jacobson, J. Lehel, O. Oellermann, S. Ruiz, F. Saba, Irregular networks, Congressus Numerantium, 64 (1988), 197–210. |
[2] |
M. Anholcer, C. Palmer, Irregular labellings of circulant graphs, Discrete Math., 312 (2012), 3461–3466. https://doi.org/10.1016/j.disc.2012.06.017 doi: 10.1016/j.disc.2012.06.017
![]() |
[3] |
T. Bohman, D. Kravitz, On the irregularity strength of trees, J. Graph Theor., 45 (2004), 241–254. https://doi.org/10.1002/jgt.10158 doi: 10.1002/jgt.10158
![]() |
[4] |
B. Cuckler, F. Lazebnik, Irregularity strength of dense graphs, J. Graph Theor., 58 (2008), 299–313. https://doi.org/10.1002/jgt.20313 doi: 10.1002/jgt.20313
![]() |
[5] | R. Faudree, J. Lehel, Bound on the irregularity strength of regular graphs, Colloq. Math. Soc. János Bolyai, 52 (1987), 247–256. |
[6] |
M. Kalkowski, M. Karonski, F. Pfender, A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math., 25 (2011), 1319–1321. https://doi.org/10.1137/090774112 doi: 10.1137/090774112
![]() |
[7] |
P. Majerski, J. Przybyło, On the irregularity strength of dense graphs, SIAM J. Discrete Math., 28 (2014), 197–205. https://doi.org/10.1137/120886650 doi: 10.1137/120886650
![]() |
[8] |
J. Przybyło, Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math., 23 (2009), 511–516. https://doi.org/10.1137/070707385 doi: 10.1137/070707385
![]() |
[9] |
A. Ahmad, O. Al-Mushayt, M. Bača, On edge irregularity strength of graphs, Appl. Math. Comput., 243 (2014), 607–610. https://doi.org/10.1016/j.amc.2014.06.028 doi: 10.1016/j.amc.2014.06.028
![]() |
[10] | A. Ahmad, M. Bača, M. Nadeem, On edge irregularity strength of Toeplitz graphs, UPB Sci. Bull. A, 78 (2016), 155–162. |
[11] | A. Ahmad, M. Asim, M. Bača, R. Hasni, Computing edge irregularity strength of complete m-ary trees using algorithmic approach, UPB Sci. Bull. A, 80 (2018), 145–152. |
[12] |
I. Tarawneh, R. Hasni, A. Ahmad, M. Asim, On the edge irregularity strength for some classes of plane graphs, AIMS Mathematics, 6 (2021), 2724–2731. https://doi.org/10.3934/math.2021166 doi: 10.3934/math.2021166
![]() |
[13] |
M. Basher, On the reflexive edge strength of the circulant graphs, AIMS Mathematics, 6 (2021), 9342–9365. https://doi.org/10.3934/math.2021543 doi: 10.3934/math.2021543
![]() |
[14] |
M. Basher, Edge irregular reflexive labeling for the r-th power of the path, AIMS Mathematics, 6 (2021), 10405–10430. https://doi.org/10.3934/math.2021604 doi: 10.3934/math.2021604
![]() |
[15] |
K. Yoong, R. Hasni, G. Lau, M. Asim, A. Ahmad, Reflexive edge strength of convex polytopes and corona product of cycle with path, AIMS Mathematics, 7 (2022), 11784–11800. https://doi.org/10.3934/math.2022657 doi: 10.3934/math.2022657
![]() |
[16] |
M. Bača, K. Muthugurupackiam, K. Kathiresan, S. Ramya, Modular irregularity strength of graphs, Electron. J. Graph The., 8 (2020), 435–443. http://dx.doi.org/10.5614/ejgta.2020.8.2.19 doi: 10.5614/ejgta.2020.8.2.19
![]() |
[17] |
M. Bača, Z. Kimáková, M. Lascsáková, A. Semaničová-Feňovčíková, The irregularity and modular irregularity strength of fan graphs, Symmetry, 13 (2021), 605. https://doi.org/https://doi.org/10.3390/sym13040605 doi: 10.3390/sym13040605
![]() |
[18] |
M. Bača, M. Imran, A. Semaničová-Feňovčíková, Irregularity and modular irregularity strength of wheels, Mathematics, 9 (2021), 2710. https://doi.org/10.3390/math9212710 doi: 10.3390/math9212710
![]() |
[19] |
K. Sugeng, Z. Barack, N. Hinding, R. Simanjuntak, Modular irregular labeling on double-star and friendship graphs, J. Math., 2021 (2021), 4746609. https://doi.org/10.1155/2021/4746609 doi: 10.1155/2021/4746609
![]() |
[20] | K. Muthugurupackiam, S. Ramya, Even modular edge irregularity strength of graphs, International J. Math. Combin., 1 (2018), 75–82. |
[21] | K. Muthugurupackiam, S. Ramya, On modular edge irregularity strength of graphs, J. Appl. Sci. Comput., 6 (2019), 1902–1905. |
[22] |
R. Faudree, R. Schelp, M. Jacobson, J. Lehel, Irregular networks, regular graphs and integer matrices with distinct row and column sums, Discrete Math., 76 (1989), 223–240. https://doi.org/10.1016/0012-365X(89)90321-X doi: 10.1016/0012-365X(89)90321-X
![]() |
[23] | K. Sugeng, M. Miller, Slamin, M. Bača, (a,d)-edge-antimagic total labelings of caterpillars, Lecture notes in computer science, Berlin: Springer, 2005,169–180. https://doi.org/10.1007/978-3-540-30540-8_19 |
[24] |
A. Kotzig, A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull. 13 (1970), 451–461. https://doi.org/10.4153/CMB-1970-084-1 doi: 10.4153/CMB-1970-084-1
![]() |
[25] | A. Marr, W. Wallis, Magic graphs, 2 Eds., Boston: Birkhäuser, 2013. |
[26] |
M. Bača, Y. Lin, M. Miller, M. Youssef, Edge-antimagic graphs, Discrete Math., 307 (2007), 1232–1244. https://doi.org/10.1016/j.disc.2005.10.038 doi: 10.1016/j.disc.2005.10.038
![]() |
1. | Debi Oktia Haryeni, Zata Yumni Awanis, Martin Bača, Andrea Semaničová-Feňovčíková, Modular Version of Edge Irregularity Strength for Fan and Wheel Graphs, 2022, 14, 2073-8994, 2671, 10.3390/sym14122671 | |
2. | Gohar Ali, Martin Bača, Marcela Lascsáková, Andrea Semaničová-Feňovčíková, Ahmad ALoqaily, Nabil Mlaiki, Modular total vertex irregularity strength of graphs, 2023, 8, 2473-6988, 7662, 10.3934/math.2023384 | |
3. | Martin Bača, Muhammad Imran, Zuzana Kimáková, Andrea Semaničová-Feňovčíková, A new generalization of edge-irregular evaluations, 2023, 8, 2473-6988, 25249, 10.3934/math.20231287 | |
4. | D. Ahima Emilet, Daniel Paul, R. Jayagopal, Micheal Arockiaraj, Zhao Li, Total Face Irregularity Strength of Certain Graphs, 2024, 2024, 1563-5147, 1, 10.1155/2024/5540959 | |
5. | A Sethukkarasi, S Vidyanandini, 2024, Graph Composite Labeling techniques and Practical Applications, 979-8-3503-4985-6, 526, 10.1109/ESIC60604.2024.10481632 | |
6. | Asad Ullah, Shahid Zaman, Arshad Hussain, Asma Jabeen, Melaku Berhe Belay, Derivation of mathematical closed form expressions for certain irregular topological indices of 2D nanotubes, 2023, 13, 2045-2322, 10.1038/s41598-023-38386-1 | |
7. | Baskar Mari, Ravi Sankar Jeyaraj, Radio number of $ 2- $ super subdivision for path related graphs, 2024, 9, 2473-6988, 8214, 10.3934/math.2024399 | |
8. | Baskar Mari, Ravi Sankar Jeyaraj, Further results on the radio number for some construction of the path, complete, and complete bipartite graphs, 2024, 10, 24058440, e34434, 10.1016/j.heliyon.2024.e34434 |