Ali Ahmad^a , Martin Bacaˇ b,c, Muhammad Numan^c

ahmadsms@gmail.com, martin.baca@tuke.sk, numantng@gmail.com

We investigate the vertex total and edge total modification of the well-known irregularity strength of graphs.

We have determined the exact values of the total vertex irregularity strength and the total edge irregularity strength of a disjoint union of friendship graphs.

Keywords: vertex irregular total k-labeling, edge irregular total k-labeling, total vertex irregularity strength, total edge irregularity strength, friendship graph

Mathematics Subject Classification : 05C78

1. Introduction

Chartrand et al. [8] introduced labelings of the edges of a graph G with positive integers such that the sum of the labels of edges incident with a vertex is different for all the vertices. Such labelings were called irregular assignments and the irregularity strength s(G) of a graph G is known as the minimum k for which G has an irregular assignment using labels at most k. The irregularity strength s(G) can be interpreted as the smallest integer k for which G can be turned into a multigraph G⁰ by replacing each edge by a set of at most k parallel edges, such that the degrees of the vertices in G⁰ are all different.

Finding the irregularity strength of a graph seems to be hard even for graphs with simple structure, see [6, 19]. Karonski ´ et al. [12] conjectured that the edges of every connected graph of order

Received: 9 July 2012, Revised: 24 June 2013, Accepted: 27 July 2013.

^aCollege of computer and information system, Jazan University, Jazan, Saudi Arabia

^bDepartment of Applied Mathematics and Informatics, Technical University, Kosice, Slovak Republic ˇ

^cAbdus Salam School of Mathematical Sciences, GC University, Lahore, Pakistan

at least 3 can be assigned labels from {1, 2, 3}, such that for all pairs of adjacent vertices the sums of the labels of the incident edges are different.

Motivated by irregular assignments Bacaˇ et al. [5] defined a vertex irregular total k-labeling of a (p, q)-graph G = (V, E) to be a labeling of the vertices and edges of G

\[\phi: V \cup E \to \{1, 2, \dots, k\}\]

such that the total vertex-weights

\[wt(x) = \phi(x) + \sum_{xy \in E} \phi(xy)\]

are different for all vertices, that is, wt(x) 6= wt(y) for all different vertices x, y ∈ V . Furthermore, they defined the total vertex irregularity strength, tvs(G), of G as the minimum k for which G has a vertex irregular total k-labeling.

It is easy to see that irregularity strength s(G) of a graph G is defined only for graphs containing at most one isolated vertex and no connected component of order 2. On the other hand, the total vertex irregularity strength tvs(G) is defined for every graph G.

If an edge labeling f : E → {1, 2, . . . , s(G)} provides the irregularity strength s(G), then we extend this labeling to total labeling φ in such a way

\[\phi(xy) = f(xy)\] for every \(xy \in E(G)\),
\(\phi(x) = 1\) for every \(x \in V(G)\).

Thus, the total labeling φ is a vertex irregular total labeling and for graphs with no component of order ≤ 2 has tvs(G) ≤ s(G).

Nierhoff [14] proved that for all (p, q)-graphs G with no component of order at most 2 and G 6= K3, the irregularity strength s(G) ≤ p − 1. From this result it follows that

\[tvs(G) \le p - 1. \tag{1}\]

In [5] several bounds and exact values of tvs(G) were determined for different types of graphs (in particular for stars, cliques and prisms). Among others, the authors proved that for every (p, q) graph G with minimum degree δ = δ(G) and maximum degree ∆ = ∆(G),

\[\left\lceil \frac{p + \delta(G)}{\Delta(G) + 1} \right\rceil \le tvs(G) \le p + \Delta(G) - 2\delta(G) + 1. \tag{2}\]

In the case of r-regular graphs (2) gives

\[\left\lceil \frac{p+r}{r+1} \right\rceil \le tvs(G) \le p-r+1. \tag{3}\]

For graphs with no component of order ≤ 2, Bacaˇ et al. in [5] strengthened also these upper bounds, proving that tvs(G) ≤ p − 1 − l p−2 ∆(G)+1 ^m . These results were then improved by Przybylo

in [18] for sparse graphs and for graphs with large minimum degree. In the latter case were proved the bounds \(tvs(G) < 32 \frac{p}{\delta(G)} + 8\) in general and \(tvs(G) < 8 \frac{p}{r} + 3\) for r-regular (p,q)-graphs. Anholcer et~al. [4] established a new upper bound of the form

\[tvs(G) \le 3\left\lceil \frac{p}{\delta(G)} \right\rceil + 1.\] (4)

Wijaya \(et\ al.\) [21] determined an exact value of the total vertex irregularity strength for complete bipartite graphs. Wijaya \(et\ al.\) [20] found the exact values of tvs for wheels, fans, suns and friendship graphs. Nurdin \(et\ al.\) determined exact values of tvs for several types of trees and for disjoint union of paths in [17] and [15], respectively. Ahmad \(et\ al.\) [2] found exact values of tvs for Jahangir graphs and circulant graphs.

Now we consider a total k-labeling \(\phi: V \cup E \to \{1,2,\ldots,k\}\) with the associated total edgeweight

\[wt(xy) = \phi(x) + \phi(xy) + \phi(y).\]

Bača et al. in [5] define a labeling \(\phi: V \cup E \to \{1, 2, \dots, k\}\) to be an edge irregular total k-labeling of the graph G = (V, E) if for every two different edges xy and x'y' of G one has \(wt(xy) \neq wt(x'y')\). The total edge irregularity strength, tes(G), is defined as the minimum k for which G has an edge irregular total k-labeling.

In [5] we can find that

\[tes(G) \ge \max\left\{ \left\lceil \frac{|E(G)| + 2}{3} \right\rceil, \left\lceil \frac{\Delta(G) + 1}{2} \right\rceil \right\}, \tag{5}\]

where \(\Delta(G)\) is the maximum degree of G, and also there are determined the exact values of the total edge irregularity strength for paths, cycles, stars, wheels and friendship graphs.

Recently Ivančo and Jendroľ [9] proved that for any tree T the \(tes(T) = \max\left\{\left\lceil\frac{|E(T)|+2}{3}\right\rceil, \left\lceil\frac{\Delta(T)+1}{2}\right\rceil\right\}\). Moreover, they posed the following conjecture.

Conjecture 1. [9] Let G be an arbitrary graph different from \(K_5\). Then

\[tes(G) = \max\left\{ \left\lceil \frac{|E(G)| + 2}{3} \right\rceil, \left\lceil \frac{\Delta(G) + 1}{2} \right\rceil \right\}.\] (6)

The Ivančo and Jendrol's conjecture has been verified for complete graphs and complete bipartite graphs in [10] and [11], for the Cartesian product of two paths in [13], for large dense graphs with \(\frac{|E(G)|+2}{3} \leq \frac{\Delta(G)+1}{2}\) in [7], for the categorical product of a cycle and a path in [1] and for the categorical product of two paths in [3].

The main aim of this paper is determined the exact values of the total vertex irregularity strength and the total edge irregularity strength of a disjoint union of friendship graphs.

2. Total vertex irregularity strength of disjoint union of friendship graphs

The friendship graph \(F_n\) is a set of n triangles having a common central vertex, and otherwise disjoint. The friendship graph \(F_n\) has 2n + 1 vertices (2n vertices of degree 2 and one vertex of degree 2n) and 3n edges.

Nurdin et al. [16] proved the following lower bound of tvs for any graph G.

Theorem 2.1. [16] Let G be a connected graph having \(n_i\) vertices of degree i (\(i = \delta, \delta + 1, \delta + 2, \ldots, \Delta\)), where \(\delta\) and \(\Delta\) are the minimum and the maximum degree of G, respectively. Then

\[tvs(G) \ge \max \left\{ \left\lceil \frac{\delta + n_{\delta}}{\delta + 1} \right\rceil, \left\lceil \frac{\delta + n_{\delta} + n_{\delta+1}}{\delta + 2} \right\rceil, \dots, \left\lceil \frac{\delta + \sum_{i=\delta}^{\Delta} n_i}{\Delta + 1} \right\rceil \right\}.\] (7)

The next theorem determines the exact value of the total vertex irregularity strength for disjoint union of arbitrary friendship graphs.

Theorem 2.2. Let \(F_{n_j}\) be a friendship graph with \(n_j\) triangles, \(n_j \geq 3\) and \(1 \leq j \leq m\), \(m \geq 2\). Let \(G \cong \bigcup_{j=1}^m F_{n_j}\) be a disjoint union of the friendship graphs \(F_{n_j}\). Then

\[tvs(G) = \left[ \frac{2 + 2\sum_{j=1}^{m} n_j}{3} \right].\] (8)

Proof. The disjoint union of the friendship graphs has \(2\sum_{j=1}^{m}n_{j}\) vertices of degree 2, say, \(u_{i}^{j}, v_{i}^{j}, 1 \leq j \leq m, 1 \leq i \leq n_{j}\), and vertices of degree \(2n_{j}\), say, \(c^{j}\), \(1 \leq j \leq m\). From inequality (7) it follows that

\[tvs(G) \ge \left\lceil \frac{2 + 2\sum_{j=1}^{m} n_j}{3} \right\rceil. \tag{9}\]

For our convenient, we order the friendship graphs \(F_{n_j}\) such that \(n_1 \leq n_2 \leq \cdots \leq n_m\). Let \(E(G) = \{c^j v_i^j, c^j u_i^j : 1 \leq j \leq m, 1 \leq i \leq n_j\} \cup \{v_i^j u_i^j : 1 \leq j \leq m, 1 \leq i \leq n_j\}\) be the edge set of \(\bigcup_{j=1}^m F_{n_j}\).

Put \(k = \left\lceil \frac{2+2\sum\limits_{j=1}^m n_j}{3} \right\rceil\). To show that k is an upper bound for total vertex irregularity strength of

disjoint union of the friendship graphs we describe a total k-labeling \(\phi: V \cup E \to \{1, 2, \dots, k\}\) as follows:

\[\phi(c^j) = k \text{ for } 1 \le j \le m,\]

\[\phi(u_i^j) = \begin{cases} 1, & \text{if } 1 \le i \le n_j - 1 \text{ and } 1 \le j \le m \\ 2\left(1 - m - k + \sum_{s=1}^m n_s\right) + j, & \text{if } i = n_j \text{ and } 1 \le j \le m \end{cases}\] \[\phi(v_i^j) = \begin{cases} 1 - m - k + \sum_{s=1}^m n_s + \left\lceil \frac{1 + i - j + \sum_{s=1}^{j-1} n_s}{2} \right\rceil, & \text{if } 1 \le i \le n_j - 1 \\ & \text{and } 1 \le j \le m \end{cases}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\phi(c^j u_i^j) = \begin{cases} \left\lceil \frac{1 + i - j + \sum_{s=1}^{j-1} n_s}{2} \right\rceil, & \text{if } 1 \le i \le n_j - 1 \text{ and } 1 \le j \le m \end{cases}\] \[\phi(u_i^j v_i^j) = \begin{cases} \left\lceil \frac{2 + i - j + \sum_{s=1}^{j-1} n_s}{2} \right\rceil, & \text{if } 1 \le i \le n_j - 1 \text{ and } 1 \le j \le m \end{cases}\] \[\phi(u_i^j v_i^j) = \begin{cases} \left\lceil \frac{2 + i - j + \sum_{s=1}^{j-1} n_s}{2} \right\rceil, & \text{if } 1 \le i \le n_j - 1 \text{ and } 1 \le j \le m \end{cases}\] \[\phi(u_i^j v_i^j) = \begin{cases} \left\lceil \frac{2 + i - j + \sum_{s=1}^{j-1} n_s}{2} \right\rceil, & \text{if } 1 \le i \le n_j - 1 \text{ and } 1 \le j \le m \end{cases}\] \[\phi(u_i^j v_i^j) = \begin{cases} \left\lceil \frac{2 + i - j + \sum_{s=1}^{j-1} n_s}{2} \right\rceil, & \text{if } 1 \le i \le n_j - 1 \text{ and } 1 \le j \le m \end{cases}\] \[\phi(u_i^j v_i^j) = \begin{cases} \left\lceil \frac{2 + i - j + \sum_{s=1}^{j-1} n_s}{2} \right\rceil, & \text{if } 1 \le i \le n_j - 1 \text{ and } 1 \le j \le m \end{cases}\] \[\phi(u_i^j v_i^j) = \begin{cases} \left\lceil \frac{2 + i - j + \sum_{s=1}^{j-1} n_s}{2} \right\rceil, & \text{if } 1 \le i \le n_j - 1 \text{ and } 1 \le j \le m \end{cases}\]

\(\phi(c^j v_i^j) = k \text{ for } 1 < j < m \text{ and } 1 < i < n_j.\)

Under the labeling \(\phi\) for total vertex-weights we have:

\[wt(u_i^j) = \begin{cases} 3+i-j+\sum_{s=1}^{j-1} n_s, & \text{if } 1 \le i \le n_j-1 \text{ and } 1 \le j \le m \\ 2(\sum_{s=1}^m n_s-m)+2+j, & \text{if } i=n_j \text{ if } 1 \le j \le m \end{cases}\] \[wt(v_i^j) = \begin{cases} 3-m+i-j+\sum_{s=1}^m n_s+\sum_{s=1}^{j-1} n_s, & \text{if } 1 \le i \le n_j-1 \\ & \text{and } 1 \le j \le m \end{cases}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[wt(c^j) = (n_j+2)k+\sum_{i=1}^{n_j-1} \left[\frac{1+i-j+\sum_{s=1}^{j-1} n_s}{2}\right] \text{ for } 1 \le j \le m.\]

It is a routine matter to verify that all vertex and edge labels are at most k and the total vertex-weights are different for all pairs of distinct vertices. In fact,

\[tvs\left(\bigcup_{j=1}^{m} F_{n_j}\right) \le \left\lceil \frac{2 + 2\sum_{j=1}^{m} n_j}{3} \right\rceil. \tag{10}\]

Combining (10) with the lower bound given by (9), we conclude that

\[tvs\left(\bigcup_{j=1}^{m} F_{n_j}\right) = k.\]

Using the previous theorem we can get the following corollary.

Corollary 2.1. Let \(F_n\) be a friendship graph with n triangles, \(n \ge 3\) and let \(mF_n\) be the disjoint union of m copies of \(F_n\), \(m \ge 2\). Then

\[tvs(mF_n) = \left\lceil \frac{2(mn+1)}{3} \right\rceil. \tag{11}\]

Proof. Since for the disjoint union of m copies of the friendship graph \(F_n\) we have that \(\delta(mF_n)=2\) and number of vertices of degree \(\delta\) is \(n_{\delta}=2mn\) then from inequality (7) it follows that

\[tvs(mF_n) \ge \left\lceil \frac{2(mn+1)}{3} \right\rceil. \tag{12}\]

According the proof of previous theorem from (10) it follows that

\[tvs(mF_n) \le \left\lceil \frac{2(mn+1)}{3} \right\rceil. \tag{13}\]

Combining (12) and (13) produces the desired result.

The result from Theorem 2.2 adds further support to a recent conjecture.

Conjecture 2. [16] Let G be a connected graph having \(n_i\) vertices of degree i (\(i = \delta, \delta + 1, \delta + 2, \ldots, \Delta\)), where \(\delta\) and \(\Delta\) are the minimum and the maximum degree of G, respectively. Then

\[tvs(G) = \max \left\{ \left\lceil \frac{\delta + n_{\delta}}{\delta + 1} \right\rceil, \left\lceil \frac{\delta + n_{\delta} + n_{\delta + 1}}{\delta + 2} \right\rceil, \dots, \left\lceil \frac{\delta + \sum_{i=\delta}^{\Delta} n_i}{\Delta + 1} \right\rceil \right\}.\]

3. Total edge irregularity strength of disjoint union of friendship graphs

The following theorem determines the exact value of the total edge irregularity strength for disjoint union of arbitrary friendship graphs.

Theorem 3.1. Let \(F_{n_j}\) be a friendship graph with \(n_j\) triangles, \(n_j \geq 3\) and \(1 \leq j \leq m\), \(m \geq 2\). Let \(G \cong \bigcup_{j=1}^m F_{n_j}\) be a disjoint union of the friendship graphs \(F_{n_j}\). Then

\[tes(G) = 1 + \sum_{j=1}^{m} n_j.\] (14)

Proof. The disjoint union of the friendship graphs, \(\bigcup_{j=1}^{m} F_{n_j}\), has \(3\sum_{j=1}^{m} n_j\) edges. From (5) is given the following lower bound on the total edge irregularity strength.

\[tes\left(\bigcup_{j=1}^{m} F_{n_j}\right) \ge \left[\frac{2+3\sum_{j=1}^{m} n_j}{3}\right] = 1 + \sum_{j=1}^{m} n_j.\] (15)

Put \(k = 1 + \sum_{j=1}^{m} n_j\). In view that k is an upper bound on the total edge irregularity strength of \(\bigcup_{j=1}^{m} F_{n_j}\) it suffices to prove the existence of a total k-labeling \(\varphi : V \cup E \to \{1, 2, \dots, k\}\) such that

\[\varphi(x) + \varphi(xy) + \varphi(y) \neq \varphi(x') + \varphi(x'y') + \varphi(y')\]

for every \(xy, x'y' \in E\) with \(xy \neq x'y'\).

For vertices and edges of \(\bigcup_{i=1}^{m} F_{n_i}\) let

\[\varphi(u_i^j) = \varphi(u_i^j v_i^j) = 1, \qquad \text{for } 1 \le i \le n_j \text{ and } 1 \le j \le m\] \[\varphi(v_i^j) = \varphi(c^j u_i^j) = i + \sum_{s=1}^{j-1} n_s, \quad \text{for } 1 \le i \le n_j \text{ and } 1 \le j \le m\] \[\varphi(c^j) = \varphi(c^j v_i^j) = k, \qquad \text{for } 1 \le i \le n_j \text{ and } 1 \le j \le m.\]

Observe that the total edge-weights under the labeling \(\varphi\) constitute the sets

\[W_1 = \{wt(u_i^j v_i^j) = 2 + i + \sum_{s=1}^{j-1} n_s : 1 \le i \le n_j, 1 \le j \le m\} = \{3, 4, \dots, k+1\},\] \[W_2 = \{wt(c^j u_i^j) = k + 1 + i + \sum_{s=1}^{j-1} n_s : 1 \le i \le n_j, 1 \le j \le m\} = \{k + 2, k + 3, \dots, 2k\},\]

On irregularity strength of disjoint union of friendship graphs | Ali Ahmad et al.

\[W_3 = \{ wt(c^j v_i^j) = 2k + i + \sum_{s=1}^{j-1} n_s : 1 \le i \le n_j, 1 \le j \le m \} = \{ 2k + 1, 2k + 2, \dots, 3k - 1 \}.\]

It is not difficult to see that the function ϕ is the required total k-labeling such that the total edge-weights are different for all edges.

Thus we have that

\[tes\left(\bigcup_{j=1}^{m} F_{n_j}\right) \le 1 + \sum_{j=1}^{m} n_j.\]

This concludes the proof.

From Theorem 3.1 it is easy to get the following corollary.

Corollary 3.1. Let Fⁿ be a friendship graph with n triangles, n ≥ 3 and let mFⁿ be the disjoint union of m copies of Fn, m ≥ 2. Then

\[tes(mF_n) = mn + 1. (16)\]

Proof. The disjoint union of m copies of the friendship graph Fⁿ has 3mn edges and its maximum degree is 2n. Hence, from (5) it follows that

\[tes(mF_n) \ge \max\left\{ \left\lceil \frac{3mn+2}{3} \right\rceil, \left\lceil \frac{2n+1}{2} \right\rceil \right\}.\] (17)

For m ≥ 2, (17) gives tes(mFn) ≥ mn + 1. From the proof of Theorem 3.1 it follows the existence of total (mn + 1)-labeling ϕ where under labeling ϕ total edge-weights are different for all edges. Thus we arrive at the desired result.

Our result on total edge irregularity strength of disjoint union of friendship graphs adds further support to Conjecture 1.

Acknowledgement

The work was supported by Higher Education Commission Pakistan Grant HEC(FD)/2007/555 and by Slovak VEGA Grant 1/0130/12.

References

• [1] A. Ahmad and M. Baca, Edge irregular total labeling of certain family of graphs, ˇ AKCE J. Graphs. Combin. 6 No. 1 (2009), 21–29.
• [2] A. Ahmad and M. Baca, On vertex irregular total labelings, ˇ Ars Combin., in press.
• [3] A. Ahmad and M. Baca, Total edge irregularity strength of a categorical product of two paths, ˇ Ars Combin., in press.
• [4] M. Anholcer, M. Kalkowski and J. Przybylo, A new upper bound for the total vertex irregularity strength of graphs, Discrete Math. 309 (2009), 6316–6317.

• [5] M. Baca, S. Jendro ˇ ˇl, M. Miller and J. Ryan, On irregular total labellings, Discrete Math. 307 (2007), 1378–1388.
• [6] T. Bohman and D. Kravitz, On the irregularity strength of trees, J. Graph Theory 45 (2004), 241–254.
• [7] S. Brandt, J. Miskuf and D. Rautenbach, On a conjecture about edge irregular total labellings, ˇ J. Graph Theory 57 (2008), 333–343.
• [8] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988), 187–192.
• [9] J. Ivanco and S. Jendro ˇ ˇl, Total edge irregularity strength of trees, Discussiones Math. Graph Theory 26 (2006), 449–456.
• [10] S. Jendroˇl, J. Miskuf and R. Sot ˇ ak, Total edge irregularity strength of complete and complete ´ bipartite graphs, Electron. Notes Discrete Math. 28 (2007), 281–285.
• [11] S. Jendroˇl, J. Miskuf and R. Sot ˇ ak, Total edge irregularity strength of complete graphs and ´ complete bipartite graphs, Discrete Math. 310 (2010), 400–407.
• [12] M. Karonski, T. Luczak and A. Thomason, Edge weights and vertex colours, ´ J. Combin. Theory B 91 (2004), 151–157.
• [13] J. Miskuf and S. Jendro ˇ ˇl, On total edge irregularity strength of the grids, Tatra Mt. Math. Publ. 36 (2007), 147–151.
• [14] T. Nierhoff, A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math. 13 (2000), 313–323.
• [15] Nurdin, E.T. Baskoro, A.N.M. Salman and N.N. Goas, On the total vertex irregularity strength of a disjoint union of t copies of path, J. Combin. Math. Combin. Comput. 71 (2009), 129– 136.
• [16] Nurdin, E.T. Baskoro, A.N.M. Salman and N.N. Goas, On the total vertex irregularity strength of trees, Discrete Math. 310 (2010), 3043–3048.
• [17] Nurdin, E.T. Baskoro, A.N.M. Salman and N.N. Goas, On total vertex irregular labelings for several types of trees, Utilitas Math., in press.
• [18] J. Przybylo, Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math. 23 (2009), 511–516.
• [19] O. Togni, Irregularity strength of the toroidal grid, Discrete Math. 165/166 (1997), 609–620.
• [20] K. Wijaya and Slamin, Total vertex irregular labeling of wheels, fans, suns and friendship graphs, JCMCC 65 (2008), 103–112.
• [21] K. Wijaya, Slamin, Surahmat and S. Jendroˇl, Total vertex irregular labeling of complete bipartite graphs, JCMCC 55 (2005), 129–136.