Faraha Ashraf^a , Martin Bacaˇ a,b, Andrea Semanicov ˇ a-Fe ´ nov ˇ cˇ´ıkova´ a,b, Ayesha Shabbir^c

faraha27@gmail.com, martin.baca@tuke.sk, andrea.fenovcikova@tuke.sk, ashinori@hotmail.com

A simple graph G = (V (G), E(G)) admits an H-covering if every edge in E(G) belongs at least to one subgraph of G isomorphic to a given graph H. Then the graph G admitting Hcovering admits an H-irregular total k-labeling f : V (G)∪E(G) → {1, 2, . . . , k} if for every two different subgraphs H⁰ and H⁰⁰ isomorphic to H there is wt^f (H⁰ ) 6= wt^f (H⁰⁰ P ), where wt^f (H) = v∈V (H) f(v) + P e∈E(H) f(e) is the associated H-weight. The minimum k for which the graph G has an H-irregular total k-labeling is called the total H-irregularity strength of the graph G.

In this paper, we obtain the precise value of the total H-irregularity strength of G-amalgamation of graphs.

Keywords: total (vertex, edge) H-irregular labeling, total (vertex, edge) H-irregularity strength, amalgamation of graphs Mathematics Subject Classification: 05C78, 05C70 DOI: 10.5614/ejgta.2017.5.2.13

1. Introduction

All graphs we consider are simple and finite. For a given graph G denote V (G), E(G), ∆(G) and δ(G) as its sets of vertices and edges, the maximum and minimum degree, respectively.

In [12], Chartrand et al. 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.

Received: 9 May 2017, Revised: 2 September 2017, Accepted: 27 September 2017.

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

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

^cGovernment College University Faisalabad, Sahiwal Campus, Pakpatan Road, Sahiwal, Pakistan

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 exact value of s(G) is known only for some special classes of graphs, e.g. complete graphs [12], graphs with the components being paths and cycles [4, 18], or some families of trees [5]. The lower bound on the s(G) is given by the inequality

\[s(G) \ge \max_{1 \le i \le \Delta} \frac{n_i + i - 1}{i},\]

where nⁱ denotes the number of vertices of degree i. In the case of d-regular graphs of order n it reduces to

\[s(G) \ge \frac{n+d-1}{d}\].

The conjecture stated in [12] says that the value of s(G) is for every graph equal to the above lower bound plus some constant not depending on G. The best bound of this form is currently due to Kalkowski, Karonski and Pfender. Namely, the authors in [17] have proved that s(G) ≤ 6 dn/δe < 6n/δ + 6. Currently Majerski and Przybyło [19] proved that s(G) ≤ (4 + o(1))n/δ + 4 for graphs with minimum degree δ ≥ √ n ln n.

For a given vertex labeling h : V (G) → {1, 2, . . . , k} the associated weight of an edge xy ∈ E(G) is wh(xy) = h(x)+h(y). Such a labeling h is called edge irregular if for every two different edges xy and x 0 y 0 there is wh(xy) 6= wh(x 0 y 0 ). The minimum k for which the graph G has an edge irregular k-labeling is called the edge irregularity strength of G and denoted by es(G). The notion of the edge irregularity strength was defined by Ahmad et al. in [1]. There is estimated the lower bound as follows

\[\operatorname{es}(G) \ge \max\left\{ \left\lceil \frac{|E(G)|+1}{2} \right\rceil, \Delta(G) \right\}. \tag{1}\]

In [1] are determined the exact values of the edge irregularity strength for paths, stars, double stars and for Cartesian product of two paths.

For a given total labeling f : V (G) ∪ E(G) → {1, 2, . . . , k} the associated total vertex-weight of a vertex x is

\[wt_f(x) = f(x) + \sum_{xy \in E(G)} f(xy)\]

and the associated total edge-weight of an edge xy is

\[wt_f(xy) = f(x) + f(xy) + f(y).\]

In [9] a total k-labeling f is defined to be an edge (respectively, vertex) irregular total k-labeling of the graph G if for every two distinct edges xy and x 0 y 0 respectively, distinct vertices x and y) of G there is wt^f (xy) 6= wt^f (x 0 y 0 ) (respectively, wt^f (x) 6= wt^f (y)).

The minimum k for which the graph G has an edge (respectively, vertex) irregular total klabeling is called the total edge (respectively, vertex) irregularity strength of the graph G and denoted by tes(G) (respectively, tvs(G)).

The following lower bound on the total edge irregularity strength of a graph G is given in [9].

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

Ivanco and Jendrol ˇ ' [14] posed a conjecture that for arbitrary graph G different from K⁵ the total edge irregularity strength equals to the lower bound (2). This conjecture has been verified for complete graphs and complete bipartite graphs in [15, 16], for the categorical product of two cycles and two paths in [3, 2], for generalized Petersen graphs in [13], for generalized prisms in [10], for corona product of a path with certain graphs in [22] and for large dense graphs with (|E(G)| + 2)/3 ≤ (∆(G) + 1)/2 in [11].

The bounds for the total vertex irregularity strength are given in [9] as follows.

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

Przybyło [23] proved that tvs(G) < 32|V (G)|/δ(G)+8 in general and tvs(G) < 8|V (G)|/r+3 for r-regular graphs. This was then improved by Anholcer et. al in [6] by the following way

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

Recently Majerski and Przybyło in [20] based on a random ordering of the vertices proved that if δ(G) ≥ (|V (G)|) 0.5 ln |V (G)|, then

\[\operatorname{tvs}(G) \le \frac{(2+o(1))|V(G)|}{\delta(G)} + 4.\] (5)

Combining previous modifications of the irregularity strength, Marzuki, Salman and Miller [21] introduced a new irregular total k-labeling of a graph G called totally irregular total klabeling, which is required to be at the same time vertex irregular total and also edge irregular total. The minimum k for which a graph G has a totally irregular total k-labeling is called the total irregularity strength of G and is denoted by ts(G). In [21] there are given upper and lower bounds for the parameter ts(G). Ramdani and Salman in [24] determined the exact values of the total irregularity strength for several Cartesian product graphs.

Motivated by the irregularity strength and the total edge (respectively, vertex) irregularity strength of a graph G, Ashraf et al. in [7, 8] introduced new parameters, total (respectively, edge and vertex) H-irregularity strengths, as a natural extension of the parameters s(G), es(G), tes(G) and tvs(G).

An edge-covering of G is a family of subgraphs H1, H2, . . . , H^t such that each edge of E(G) belongs to at least one of the subgraphs Hⁱ , i = 1, 2, . . . , t. Then it is said that G admits an (H1, H2, . . . , Ht)-(edge) covering. If every subgraph Hⁱ is isomorphic to a given graph H, then the graph G admits an H-covering. Note, that in this case all subgraphs of G isomorphic to H must be in the H-covering.

Let G be a graph admitting H-covering. For the subgraph H ⊆ G under the total k-labeling f, we define the associated H-weight as

\[wt_f(H) = \sum_{v \in V(H)} f(v) + \sum_{e \in E(H)} f(e).\]

A total k-labeling f is called to be an H-irregular total k-labeling of the graph G if for every two different subgraphs H⁰ and H⁰⁰ isomorphic to H there is wt^f (H⁰ ) 6= wt^f (H⁰⁰). The total Hirregularity strength of a graph G, denoted ths(G, H), is the smallest integer k such that G has

an H-irregular total k-labeling. If H is isomorphic to \(K_2\), then the \(K_2\)-irregular total k-labeling is isomorphic to the edge irregular total k-labeling and thus the total \(K_2\)-irregularity strength of a graph G is equivalent to the total edge irregularity strength, that is \(\operatorname{ths}(G, K_2) = \operatorname{tes}(G)\).

For the subgraph \(H\subseteq G\) under the edge labeling \(g:E(G)\to\{1,2,\ldots,k\}\) (respectively, the vertex labeling \(h:V(G)\to\{1,2,\ldots,k\}\)) the associated H-weight is \(wt_g(H)=\sum_{e\in E(H)}g(e)\)

(respectively, \[wt_h(H) = \sum_{v \in V(H)} h(v)\]).

Such edge labeling g (respectively, vertex labeling h) is called to be an H-irregular edge (respectively, vertex) k-labeling of the graph G if for every two different subgraphs H' and H'' isomorphic to H there is \(wt_g(H') \neq wt_g(H'')\) (respectively, \(wt_h(H') \neq wt_h(H'')\)). The edge (respectively, vertex) H-irregularity strength of a graph G, denoted by ehs(G, H) (respectively, ehs(G, H)), is the smallest integer ehs(G, H) as an ehs(G, H)-irregular edge (respectively, ehs(G, H)), is the smallest integer ehs(G, H) as an ehs(G, H)-irregular edge (respectively, ehs(G, H)).

Note, that \(\mathrm{vhs}(G,H) = \infty\) if there exist two subgraphs in G isomorphic to H that have the same vertex sets.

Let \(G_i\), \(i=1,2,\ldots,n\), be finite graphs containing a graph \(\mathcal G\) as a subgraph. The graph \(\mathcal G\) we will call a connector. The \(\mathcal G\)-amalgamation of graphs \(G_1,G_2,\ldots,G_n\) denoted by \(Amal(G_i,\mathcal G)\) is a graph obtained by taking all \(G_i\)'s and identifying their connectors \(\mathcal G\). If all graphs \(G_i\), \(i=1,2,\ldots,n\), are isomorphic to a given graph G we will use the notation \(Amal(G,\mathcal G,n)\). Note that if \(\mathcal G=K_1\) then this operation is known as a vertex-amalgamation and if \(\mathcal G=K_2\) then it is called an edge-amalgamation.

In this paper we will study the total (respectively, edge and vertex) G-irregularity strengths of the graph \(Amal(G, \mathcal{G}, n)\) when \(Amal(G, \mathcal{G}, n)\) contains exactly n subgraphs isomorphic to G and we prove that the exact values of the total (respectively, edge and vertex) G-irregularity strengths of the investigated family of graphs equals to the lower bounds.

2. Lower bounds

Let G be a graph admitting H-covering. Let \(\mathbb{H}_m^S = (H_1^S, H_2^S, \ldots, H_m^S)\) be the set of all subgraphs of G isomorphic to H such that the graph \(S, S \not\cong H\), is their maximum common subgraph. Thus \(V(S) \subset V(H_i^S)\) and \(E(S) \subset E(H_i^S)\) for every \(i=1,2,\ldots,m\). In [8] was given the lower bound of the total H-irregularity strength if the subgraphs isomorphic to H share some elements.

Theorem 2.1. [8] Let G be a graph admitting an H-covering. Let \(S_i\), i = 1, 2, ..., z, be all subgraphs of G such that \(S_i\) is a maximum common subgraph of \(m_i\), \(m_i \ge 2\), subgraphs of G isomorphic to H. Then

ths\[(G, H) \ge \max \left\{ \left[ 1 + \frac{m_1 - 1}{|V(H/S_1)| + |E(H/S_1)|} \right], \dots, \left[ 1 + \frac{m_z - 1}{|V(H/S_z)| + |E(H/S_z)|} \right] \right\}.\]

Next theorem proved in [7] gives the lower bound of the edge (vertex) H-irregularity strength of a graph.

Theorem 2.2. [7] Let G be a graph admitting an H-covering. Let \(S_i\), i = 1, 2, ..., z, be all subgraphs of G such that \(S_i\) is a maximum common subgraph of \(m_i\), \(m_i \ge 2\), subgraphs of G isomorphic to H. Then

\[\operatorname{ehs}(G, H) \ge \max \left\{ \left\lceil 1 + \frac{m_1 - 1}{|E(H/S_1)|} \right\rceil, \left\lceil 1 + \frac{m_2 - 1}{|E(H/S_2)|} \right\rceil, \dots, \left\lceil 1 + \frac{m_z - 1}{|E(H/S_z)|} \right\rceil \right\}, \\ \operatorname{vhs}(G, H) \ge \max \left\{ \left\lceil 1 + \frac{m_1 - 1}{|V(H/S_1)|} \right\rceil, \left\lceil 1 + \frac{m_2 - 1}{|V(H/S_2)|} \right\rceil, \dots, \left\lceil 1 + \frac{m_z - 1}{|V(H/S_z)|} \right\rceil \right\}.\]

Immediately form previous theorems we obtain the following result

Theorem 2.3. If the graph \(Amal(G, \mathcal{G}, n)\) contains exactly n subgraphs isomorphic to G then

\[\operatorname{ths}(Amal(G,\mathcal{G},n),G) \geq 1 + \left\lceil \frac{n-1}{|V(G)| + |E(G)| - |V(\mathcal{G})| - |E(\mathcal{G})|} \right\rceil,\] \[\operatorname{ehs}(Amal(G,\mathcal{G},n),G) \geq 1 + \left\lceil \frac{n-1}{|E(G)| - |E(\mathcal{G})|} \right\rceil,\] \[\operatorname{vhs}(Amal(G,\mathcal{G},n),G) \geq 1 + \left\lceil \frac{n-1}{|V(G)| - |V(\mathcal{G})|} \right\rceil.\]

3. Upper bounds

In this section we prove that the lower bounds presented in Theorem 2.3 are also the upper bounds. First we prove the corresponding result for the total G-irregularity strength of the graph \(Amal(G, \mathcal{G}, n)\).

Theorem 3.1. If the graph \(Amal(G, \mathcal{G}, n)\) contains exactly n subgraphs isomorphic to G then

ths(\[Amal(G, \mathcal{G}, n), G\]) =1 + \(\left\lceil \frac{n-1}{|V(G)| + |E(G)| - |V(\mathcal{G})| - |E(\mathcal{G})|} \right\rceil\).

Proof. Let the graph \(Amal(G, \mathcal{G}, n)\) contains exactly n subgraphs isomorphic to G. Let us denote by the symbols \(x_j^i\), i = 1, 2, ..., n, j = 1, 2, ..., s, where \(s = |V(G)| + |E(G)| - |V(\mathcal{G})| - |E(\mathcal{G})|\), the elements (vertices and edges) of the graph \(Amal(G, \mathcal{G}, n)\) from the ith copy \(G^i\) that are not elements of the connector \(\mathcal{G}\).

We define a total labeling f of \(Amal(G, \mathcal{G}, n)\) such that

\[f(x) = 1 \quad \text{if } x \in V(\mathcal{G}) \cup E(\mathcal{G}),\] \[f(x_j^i) = \begin{cases} \frac{i-1}{s} + 1 & \text{if } i \equiv 1 \pmod{s}, 1 \leq i \leq n, j = 1, 2, \dots, s, \\ \left\lfloor \frac{i-1}{s} \right\rfloor + 2 & \text{if } i \not\equiv 1 \pmod{s}, 2 \leq i \leq n, j = 1, 2, \dots, i - \left\lfloor \frac{i-1}{s} \right\rfloor s - 1, \\ \left\lfloor \frac{i-1}{s} \right\rfloor + 1 & \text{if } i \not\equiv 1 \pmod{s}, 2 \leq i \leq n, j = i - \left\lfloor \frac{i-1}{s} \right\rfloor s, i - \left\lfloor \frac{i-1}{s} \right\rfloor s + 1, \dots, s. \end{cases}\]

If \(n \equiv 1 \pmod{s}\) then the maximal used label is

\[\frac{n-1}{s} + 1 = \left\lceil \frac{n-1}{s} \right\rceil + 1.\]

If \(n \not\equiv 1 \pmod{s}\) then the maximal used label is

\[\left\lfloor \frac{n-1}{s} \right\rfloor + 2 = \left( \left\lceil \frac{n-1}{s} \right\rceil - 1 \right) + 2 = \left\lceil \frac{n-1}{s} \right\rceil + 1.\]

Thus f is (d(n − 1)/se + 1)-labeling.

In the light of Theorem 2.3 it suffices to prove that the G-weights are distinct. For the weights of graphs Gⁱ , i = 1, 2, . . . , n, we get the following

\[wt_f(G^i) = \sum_{x \in V(G^i) \cup E(G^i)} f(x) = \sum_{x \in V(G) \cup E(G)} f(x) + \sum_{j=1}^s f(x_j^i) = \sum_{x \in V(G) \cup E(G)} 1 + \sum_{j=1}^s f(x_j^i)\]\[= |V(G)| + |E(G)| + \sum_{j=1}^s f(x_j^i).\]

If i ≡ 1 (mod s) then

\[wt_f(G^i) = |V(\mathcal{G})| + |E(\mathcal{G})| + \sum_{j=1}^{s} \left(\frac{i-1}{s} + 1\right) = |V(\mathcal{G})| + |E(\mathcal{G})| + \left(\frac{i-1}{s} + 1\right)s\]\[= |V(\mathcal{G})| + |E(\mathcal{G})| + s - 1 + i.\]

For i 6≡ 1 (mod s) we get

\[wt_{f}(G^{i}) = |V(\mathcal{G})| + |E(\mathcal{G})| + \sum_{j=1}^{i-\left\lfloor \frac{i-1}{s} \right\rfloor s-1} f(x_{j}^{i}) + \sum_{j=i-\left\lfloor \frac{i-1}{s} \right\rfloor s}^{s} f(x_{j}^{i})\] \[= |V(\mathcal{G})| + |E(\mathcal{G})| + \sum_{j=1}^{i-\left\lfloor \frac{i-1}{s} \right\rfloor s-1} (\lfloor \frac{i-1}{s} \rfloor + 2) + \sum_{j=i-\left\lfloor \frac{i-1}{s} \right\rfloor s}^{s} (\lfloor \frac{i-1}{s} \rfloor + 1)\] \[= |V(\mathcal{G})| + |E(\mathcal{G})| + (i - \lfloor \frac{i-1}{s} \rfloor s - 1) (\lfloor \frac{i-1}{s} \rfloor + 2)\] \[+ (s - i + \lfloor \frac{i-1}{s} \rfloor s + 1) (\lfloor \frac{i-1}{s} \rfloor + 1)\] \[= |V(\mathcal{G})| + |E(\mathcal{G})| + s \lfloor \frac{i-1}{s} \rfloor + 2 (i - \lfloor \frac{i-1}{s} \rfloor s - 1) + (s - i + \lfloor \frac{i-1}{s} \rfloor s + 1)\] \[= |V(\mathcal{G})| + |E(\mathcal{G})| + s \lfloor \frac{i-1}{s} \rfloor + s + i - \lfloor \frac{i-1}{s} \rfloor s - 1\] \[= |V(\mathcal{G})| + |E(\mathcal{G})| + s - 1 + i.\]

Combining the previous facts we get that for every i, i = 1, 2, . . . , n, holds

\[wt_f(G^i) = |V(\mathcal{G})| + |E(\mathcal{G})| + s - 1 + i.\]

Thus the set of G-weights consists of consecutive integers.

For the edge G-irregularity strengths of the graph Amal(G, G, n) we get the following result.

Theorem 3.2. If the graph \(Amal(G, \mathcal{G}, n)\) contains exactly n subgraphs isomorphic to G then

\[\operatorname{ehs}(\operatorname{Amal}(G,\mathcal{G},n),G) = 1 + \left\lceil \frac{n-1}{|E(G)| - |E(\mathcal{G})|} \right\rceil.\]

Proof. Let the graph \(Amal(G, \mathcal{G}, n)\) contains exactly n subgraphs isomorphic to G. Let us denote by the symbols \(e_j^i\), \(i = 1, 2, \ldots, n\), \(j = 1, 2, \ldots, s\), where \(s = |E(G)| - |E(\mathcal{G})|\), the edges of the graph \(Amal(G, \mathcal{G}, n)\) from the ith copy \(G^i\) that are not edges of the connector \(\mathcal{G}\).

We define an edge labeling q of \(Amal(G, \mathcal{G}, n)\) such that

\[g(e) = 1 \quad \text{if } e \in E(\mathcal{G}),\] \[g(e_j^i) = \begin{cases} \frac{i-1}{s} + 1 & \text{if } i \equiv 1 \pmod{s}, 1 \leq i \leq n, j = 1, 2, \dots, s, \\ \left\lfloor \frac{i-1}{s} \right\rfloor + 2 & \text{if } i \not\equiv 1 \pmod{s}, 2 \leq i \leq n, j = 1, 2, \dots, i - \left\lfloor \frac{i-1}{s} \right\rfloor s - 1, \\ \left\lfloor \frac{i-1}{s} \right\rfloor + 1 & \text{if } i \not\equiv 1 \pmod{s}, 2 \leq i \leq n, j = i - \left\lfloor \frac{i-1}{s} \right\rfloor s, i - \left\lfloor \frac{i-1}{s} \right\rfloor s + 1, \dots, s. \end{cases}\]

Using similar arguments as in the proof of Theorem 3.1 we prove that under the edge labeling g the induced G-weights are distinct.

For the vertex version we have

Theorem 3.3. If the graph \(Amal(G, \mathcal{G}, n)\), \(|V(G)| \neq |V(\mathcal{G})|\), contains exactly n subgraphs isomorphic to G then

\[vhs(Amal(G, \mathcal{G}, n), G) = 1 + \left\lceil \frac{n-1}{|V(G)| - |V(\mathcal{G})|} \right\rceil.\]

Proof. Let the graph \(Amal(G, \mathcal{G}, n)\), \(|V(G)| \neq |V(\mathcal{G})|\), contains exactly n subgraphs isomorphic to G. Let us denote by the symbols \(v_j^i\), \(i = 1, 2, \ldots, n, j = 1, 2, \ldots, s\), where \(s = |V(G)| - |V(\mathcal{G})|\), the vertices of the graph \(Amal(G, \mathcal{G}, n)\) from the ith copy \(G^i\) that are not vertices of the connector \(\mathcal{G}\).

It is easy to see that the vertex labeling h of \(Amal(G, \mathcal{G}, n)\) defined bellow has the desired properties.

\[h(v) = 1 \quad \text{if } v \in V(\mathcal{G}),\] \[h(v_j^i) = \begin{cases} \frac{i-1}{s} + 1 & \text{if } i \equiv 1 \pmod{s}, 1 \leq i \leq n, j = 1, 2, \dots, s, \\ \left\lfloor \frac{i-1}{s} \right\rfloor + 2 & \text{if } i \not\equiv 1 \pmod{s}, 2 \leq i \leq n, j = 1, 2, \dots, i - \left\lfloor \frac{i-1}{s} \right\rfloor s - 1, \\ \left\lfloor \frac{i-1}{s} \right\rfloor + 1 & \text{if } i \not\equiv 1 \pmod{s}, 2 \leq i \leq n, j = i - \left\lfloor \frac{i-1}{s} \right\rfloor s, i - \left\lfloor \frac{i-1}{s} \right\rfloor s + 1, \dots, s. \end{cases}\]

Immediately from Theorem 3.1 we obtain the result for the total edge irregularity strength of a star \(K_{1,n}\), that was proved in [9].

Corollary 3.1. [9] Let n be a positive integer, then

\[\operatorname{tes}(K_{1,n}) = 1 + \left\lceil \frac{n-1}{2} \right\rceil.\]

Proof. Let n be a positive integer, then

ths(\[Amal(K_2, K_1, n), K_2\]) = ths(\(K_{1,n}, K_2\)) = tes(\(K_{1,n}\)) = 1 + \(\left\lceil \frac{n-1}{|V(K_2)| + |E(K_2)| - |V(K_1)| - |E(K_1)|} \right\rceil\)
= 1 + \(\left\lceil \frac{n-1}{2+1-1-0} \right\rceil\) = 1 + \(\left\lceil \frac{n-1}{2} \right\rceil\).

The friendship graph is a finite graph with the property that every two vertices have exactly one neighbor in common. Friendship graph fⁿ can be obtained as a collection of n triangles with a common vertex. The generalized friendship graph fm,n is a collection of n cycles (all of order m), meeting at a common vertex. Immediately from the previous theorems we get the following.

Corollary 3.2. Let m, n be positive integers, m ≥ 3 and n ≥ 1. Then

ths\[(f_{m,n}, C_m) = 1 + \left\lceil \frac{n-1}{2m-1} \right\rceil\],
\nehs\((f_{m,n}, C_m) = 1 + \left\lceil \frac{n-1}{m} \right\rceil\),
vhs\((f_{m,n}, C_m) = 1 + \left\lceil \frac{n-1}{m-1} \right\rceil\).

4. Conclusion

In the paper we studied the total (respectively, edge and vertex) G-irregularity strengths of the graph Amal(G, G, n) when Amal(G, G, n) contains exactly n subgraphs isomorphic to G. We estimated the lower bounds of the total (respectively, edge and vertex) G-irregularity strengths and proved that the exact values of these parameters for the amalgamation of graphs equal to the lower bounds.

Acknowledgement

This work was supported by the Slovak Science and Technology Assistance Agency under the contract No. APVV-15-0116 and by VEGA 1/0385/17.

References

• [1] A. Ahmad, O.B.S. Al-Mushayt and M. Baca, On edge irregularity strength of graphs, ˇ Appl. Math. Comput. 243 (2014), 607–610.
• [2] A. Ahmad and M. Baca, Total edge irregularity strength of a categorical product of two paths, ˇ Ars Combin. 114 (2014), 203–212.
• [3] A. Ahmad, M. Baca and M.K. Siddiqui, On edge irregular total labeling of categorical product ˇ of two cycles, Theory Comp. Systems 54(1) (2014), 1–12.
• [4] M. Aigner and E. Triesch, Irregular assignments of trees and forests, SIAM J. Discrete Math. 3 (1990), 439–449.

• [5] D. Amar and O. Togni, Irregularity strength of trees, Discrete Math. 190 (1998), 15-38.
• [6] M. Anholcer, M. Kalkowski and J. Przybyło, A new upper bound for the total vertex irregularity strength of graphs, Discrete Math. 309 (2009), 6316–6317.
• [7] F. Ashraf, M. Baca, Z. Kim ˇ akov ´ a and A. Semani ´ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova, On vertex and edge ´ Hirregularity strengths of graphs, Discrete Math. Algorithms and Applications 8(4) (2016), 13 pages.
• [8] F. Ashraf, M. Baca, M. Lascs ˇ akov ´ a and A. Semani ´ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova, On ´ H-irregularity strength of graphs, Discuss. Math. Graph Theory, accepted.
• [9] M. Baca, S. Jendrol ˇ ', M. Miller and J. Ryan, On irregular total labellings, Discrete Math. 307 (2007), 1378–1388.
• [10] M. Baca and M.K. Siddiqui, Total edge irregularity strength of generalized prism, ˇ Applied Math. Comput. 235 (2014), 168–173.
• [11] S. Brandt, J. Miskuf and D. Rautenbach, On a conjecture about edge irregular total labellings, ˇ J. Graph Theory 57 (2008), 333–343.
• [12] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988), 187–192.
• [13] K.M.M. Haque, Irregular total labellings of generalized Petersen graphs, Theory Comp. Systems 50 (2012), 537–544.
• [14] J. Ivanco and S. Jendrol ˇ ', Total edge irregularity strength of trees, Discussiones Math. Graph Theory 26 (2006), 449–456.
• [15] S. Jendrol', J. Miskuf and R. Sot ˇ ak, Total edge irregularity strength of complete graphs and ´ complete bipartite graphs, Electron. Notes Discrete Math. 28 (2007), 281–285.
• [16] S. Jendrol', J. Miskuf and R. Sot ˇ ak, Total edge irregularity strength of complete graphs and ´ complete bipartite graphs, Discrete Math. 310 (2010), 400–407.
• [17] M. Kalkowski, M. Karonski and F. Pfender, A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math. 25 (2011), 1319-1321.
• [18] L. Kinch and J. Lehel, The irregularity strength of tP3, Discrete Math. 94 (1991), 75-79.
• [19] P. Majerski and J. Przybyło, On the irregularity strength of dense graphs, SIAM J. Discrete Math. 28(1) (2014), 197–205.
• [20] P. Majerski and J. Przybyło, Total vertex irregularity strength of dense graphs, J. Graph Theory 76(1) (2014), 34–41.

• [21] C.C. Marzuki, A.N.M. Salman and M. Miller, On the total irregularity strength on cycles and paths, Far East J. Math. Sci. 82(1) (2013), 1-21.
• [22] Nurdin, A.N.M. Salman and E.T. Baskoro, The total edge-irregular strengths of the corona product of paths with some graphs, J. Combin. Math. Combin. Comput. 65 (2008), 163–175.
• [23] 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.
• [24] R. Ramdani and A.N.M. Salman, On the total irregularity strength of some Cartesian product graphs, AKCE Int. J. Graphs Comb. 10(2) (2013), 199–209.