On -irregularity strength of ladders and fan graphs

Abstract

We investigate modifications of the well-known irregularity strength of graphs, namely, total (vertex, edge) $H$-irregularity strengths. Recently the bounds and precise values for some families of graphs concerning these parameters have been determined. In this paper, we determine the exact value of the total (vertex, edge) $H$-irregularity strengths for the ladders and fan graphs.

Keywords:

• Total (vertex, edge) $H$-irregular labeling
• Total (vertex, edge) $H$-irregularity strength
• H-irregular labeling
• H-irregularity strength

1 Introduction

Let us consider a simple and finite graph $G=(V,E)$ with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. For notations not defined here, we refer the reader to [1]. For a given vertex labeling $\alpha :V\left(G\right)\to \{1,2,\dots ,k\}$, where $k$ is a positive integer, the associated weight of an edge $e=xy\in E\left(G\right)$ is $w_{\alpha }\left(xy\right)=\alpha \left(x\right)+\alpha \left(y\right)$. For a given edge labeling $\beta :E\left(G\right)\to \{1,2,\dots ,k\}$ the associated weight of a vertex $x\in V\left(G\right)$ is $w_{\beta }\left(x\right)={\sum }_{xy\in E\left(G\right)}\beta \left(xy\right)$, where the sum is over all vertices $y$ adjacent to $x$.

An edge labeling $\beta$ is called irregular if $w_{\beta }\left(x\right)\ne w_{\beta }\left(y\right)$ for every pair $x,y$ of vertices of $G$. The smallest integer $k$ for which an irregular labeling of $G$ exists is known as the irregularity strength of $G$ and denoted by $\mathrm{s}\left(G\right)$. The notion of the irregularity strength was introduced by Chartrand et al. in [2]. We set $s\left(G\right)=\infty$ when graph $G$ contains an isolated edge or (at least) two isolated vertices. Faudree and Lehel [3] showed that if the graph $G$ of order $n$ is $d$-regular, $d\ge 2$, then $⌈(n+d-1)∕d⌉\le \mathrm{s}\left(G\right)\le ⌈n∕2⌉+9$. The best upper bound of the irregularity strength of the graph $G$ of order $n$ is due to Kalkowski, Karonski and Pfender, who showed in [4] that $\mathrm{s}\left(G\right)\le 6⌈n∕\delta ⌉<6n∕\delta +6$. Currently Majerski and Przybyło [5] proved that $\mathrm{s}\left(G\right)\le (4+o\left(1\right))n∕\delta +4$ for graphs with minimum degree $\delta \ge \sqrt{n}lnn$.

A vertex labeling $\alpha$ is called edge irregular if $w_{\alpha }\left(xy\right)\ne w_{\alpha }\left(x^{\prime }{y}^{\prime }\right)$ for any two distinct edges $xy$ and $x^{\prime }{y}^{\prime }$. 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 $\mathrm{es}\left(G\right)$. The notion of the edge irregularity strength was defined by Ahmad et al. in [6]. There it is proved that $\mathrm{es}\left(G\right)\ge max\left\{⌈(\left|E\left(G\right)\right|+1)∕2⌉,\Delta \left(G\right)\right\}$, where $\Delta \left(G\right)$ is the maximum degree of $G$. Moreover in [6] are determined the exact values of the edge irregularity strength for paths, stars, double stars and for Cartesian product of two paths.

An edge-covering of $G$ is a family of subgraphs $H_1,H_2,\dots ,H_t$ such that each edge of $E\left(G\right)$ belongs to at least one of the subgraphs $H_i$, $i=1,2,\dots ,t$. Then it is said that $G$ admits an $(H_1,H_2,\dots ,H_t)$-(edge) covering. If every subgraph $H_i$ is isomorphic to a given graph $H$, then the graph $G$ admits an $H$-covering. Note that in this case every graph isomorphic to $H$ must be in the $H$-covering.

Motivated by the irregularity strength and the edge irregularity strength of a graph $G$, Ashraf et al. in [7] introduced two new parameters, edge (vertex) $H$-irregularity strengths, as a natural extension of the parameters $\mathrm{s}\left(G\right)$ and $\mathrm{es}\left(G\right)$.

Let $G$ be a graph admitting $H$-covering. For the subgraph $H\subseteq G$ under the edge labeling $\beta$ the associated $H$-weight is $w{t}_{\beta }\left(H\right)={\sum }_{e\in E\left(H\right)}\beta \left(e\right)$. Such edge labeling $\beta$ is called an $H$-irregular edge $k$-labeling of the graph $G$ if $w{t}_{\beta }\left(H^{\prime }\right)\ne w{t}_{\beta }\left(H^{\prime \prime }\right)$ for any two distinct subgraphs $H^{\prime }$ and $H^{\prime \prime }$ isomorphic to $H$. The edge$H$-irregularity strength of a graph $G$, denoted by $\mathrm{ehs}(G,H)$, is the smallest integer $k$ such that $G$ has an $H$-irregular edge $k$-labeling.

For the subgraph $H\subseteq G$ under the vertex labeling $\alpha$ the associated $H$-weight is $w{t}_{\alpha }\left(H\right)={\sum }_{v\in V\left(H\right)}\alpha \left(v\right)$. A vertex labeling $\alpha$ is called $H$-irregular vertex$k$-labeling of the graph $G$ if $w{t}_{\alpha }\left(H^{\prime }\right)\ne w{t}_{\alpha }\left(H^{\prime \prime }\right)$ for any two distinct subgraphs $H^{\prime }$ and $H^{\prime \prime }$ isomorphic to $H$. The smallest integer $k$ for which an $H$-irregular vertex $k$-labeling of $G$ exists is known as the vertex $H$-irregularity strength of $G$ and denoted by $\mathrm{vhs}(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.

The next theorems give the lower bounds of the edge and vertex $H$-irregularity strength, respectively.

Theorem 1

[7] Let $G$ be a graph admitting an $H$-covering given by $t$ subgraphs isomorphic to $H$. Then $$\mathrm{vhs}(G,H)\ge ⌈1+\frac{t-1}{\left|V\left(H\right)\right|}⌉.$$

Theorem 2

[7] Let $G$ be a graph admitting an $H$-covering given by $t$ subgraphs isomorphic to $H$. Then $$\mathrm{ehs}(G,H)\ge ⌈1+\frac{t-1}{\left|E\left(H\right)\right|}⌉.$$

For a given total labeling $\phi :V\left(G\right)\cup E\left(G\right)\to \{1,2,\dots ,k\}$ the associated total vertex-weight of a vertex $x$ is $w{t}_{\phi }\left(x\right)=\phi \left(x\right)+{\sum }_{xy\in E\left(G\right)}\phi \left(xy\right)$ and the associated total edge-weight of an edge $xy$ is $w{t}_{\phi }\left(xy\right)=\phi \left(x\right)+\phi \left(xy\right)+\phi \left(y\right)$. In [8] a total $k$-labeling $\phi$ is defined to be an edge irregular total $k$-labeling of the graph $G$ if $w{t}_{\phi }\left(xy\right)\ne w{t}_{\phi }\left(x^{\prime }{y}^{\prime }\right)$ for any two distinct edges $xy$ and $x^{\prime }{y}^{\prime }$ of $G$ and to be a vertex irregular total $k$-labeling of $G$ if $w{t}_{\phi }\left(x\right)\ne w{t}_{\phi }\left(y\right)$ for any two distinct vertices $x$ and $y$ of $G$.

The minimum $k$ for which the graph $G$ has an edge irregular total $k$-labeling is called the total edge irregularity strength of the graph $G$, $\mathrm{tes}\left(G\right)$. Analogously is defined the total vertex irregularity strength of $G$, $\mathrm{tvs}\left(G\right)$, as the minimum $k$ for which there exists a vertex irregular total $k$-labeling of $G$.

Ivančo and Jendrol’ [9] posed a conjecture that for an arbitrary graph $G$ different from $K_5$ and maximum degree $\Delta \left(G\right)$, $\mathrm{tes}\left(G\right)=max\left\{⌈(\left|E\left(G\right)\right|+2)∕3⌉,\right.$ $\left.⌈(\Delta \left(G\right)+1)∕2⌉\right\}$. This conjecture has been verified for complete graphs and complete bipartite graphs in [10,11], for the categorical product of two cycles and two paths in [12,13], for generalized Petersen graphs in [14], for generalized prisms in [15], for the corona product of a path with certain graphs in [16] and for large dense graphs with $(\left|E\left(G\right)\right|+2)∕3\le (\Delta \left(G\right)+1)∕2$ in [17].

The bounds for the total vertex irregularity strength are given in [8] by the form (1) $$⌈\frac{\left|V\left(G\right)\right|+\delta \left(G\right)}{\Delta \left(G\right)+1}⌉\le \mathrm{tvs}\left(G\right)\le \left|V\left(G\right)\right|+\Delta \left(G\right)-2\delta \left(G\right)+1.$$(1)

Recently Majerski and Przybyło in [18] based on a random ordering of the vertices proved that if $\delta \left(G\right)\ge {\left(\left|V\left(G\right)\right|\right)}^{0.5}ln\left|V\left(G\right)\right|$, then $\mathrm{tvs}\left(G\right)\le (2+o\left(1\right))\left|V\left(G\right)\right|∕\delta \left(G\right)+4$. The exact values for the total vertex irregularity strength for circulant graphs and unicyclic graphs are determined in [19,20] and [21], respectively.

Motivated by the total vertex (edge) irregularity strength of a graph $G$, Ashraf et al. in [22] introduced a total $H$-irregularity strength as a natural extension of the parameters $\mathrm{tes}\left(G\right)$ and $\mathrm{tvs}\left(G\right)$. Let $G$ be a graph admitting the $H$-covering. For the subgraph $H\subseteq G$ under the total $k$-labeling $\phi$ the associated $H$-weight is defined as $$w{t}_{\phi }\left(H\right)=\sum _{v\in V\left(H\right)}\phi \left(v\right)+\sum _{e\in E\left(H\right)}\phi \left(e\right).$$A total $k$-labeling $\phi$ is called an $H$-irregular total$k$-labeling of the graph $G$ if $w{t}_{\phi }\left(H^{\prime }\right)\ne w{t}_{\phi }\left(H^{\prime \prime }\right)$ for any two distinct subgraphs $H^{\prime }$ and $H^{\prime \prime }$ isomorphic to $H$. The total$H$-irregularity strength of a graph $G$, denoted $\mathrm{ths}(G,H)$, is the smallest integer $k$ such that $G$ has an $H$-irregular total $k$-labeling.

The next theorem gives a lower bound for the total $H$-irregularity strength.

Theorem 3

[22] Let $G$ be a graph admitting an $H$-covering given by $t$ subgraphs isomorphic to $H$. Then $$\mathrm{ths}(G,H)\ge ⌈1+\frac{t-1}{\left|V\left(H\right)\right|+\left|E\left(H\right)\right|}⌉.$$

In the paper, we determine the exact values of the total (vertex, edge) $H$-irregularity strengths for the ladders $L_n$ (respectively fan graphs $F_n$), $n\ge 2$, where the subgraph $H$ is a ladder $L_m$ (respectively a fan graph $F_m$) for $2\le m\le n$.

2 Ladder-irregularity strength of ladders

Let $L_n\cong P_n\square P_2$, $n\ge 2$, be a ladder with the vertex set $V\left(L_n\right)=\{v_i,u_i:i=1,2,\dots ,n\}$ and the edge set $E\left(L_n\right)=\{v_i{v}_{i+1},u_i{u}_{i+1}:i=1,2,\dots ,n-1\}\cup \{v_i{u}_i:i=1,2,\dots ,n\}$. The first theorem gives the exact value of the total ladder-irregularity strength for ladders.

Theorem 4

Let $L_n\cong P_n\square P_2$,$n\ge 2$, be a ladder admitting $L_m$ covering, where $m$ is a positive integer, $2\le m\le n$. Then $$\mathrm{ths}(L_n,L_m)=⌈\frac{4m+n-2}{5m-2}⌉.$$

Proof

The ladder $L_n$, $n\ge 2$, admits a $L_m$-covering with exactly $(n-m+1)$ ladders $L_m$, where $m$ is a positive integer and $2\le m\le n$. From Theorem 3 it follows that $\mathrm{ths}(L_n,L_m)\ge ⌈(4m+n-2)∕(5m-2)⌉$. Put $k=⌈(4m+n-2)∕(5m-2)⌉$. To show that $k$ is an upper bound for the total $L_m$-irregularity strength of $L_n$ we define a total $L_m$-irregular labeling ${\phi }_m:V\left(L_n\right)\cup E\left(L_n\right)\to \{1,2,\dots ,k\}$, $m=2,3,\dots ,n$, in the following way: $${\phi }_m\left(v_i\right)=⌈\frac{i+4m-2}{5m-2}⌉,\text{for}i=1,2,\dots ,n\text{,}$$$${\phi }_m\left(u_i\right)=⌈\frac{i+2m-1}{5m-2}⌉,\text{for}i=1,2,\dots ,n\text{,}$$$${\phi }_m\left(v_i{v}_{i+1}\right)=⌈\frac{i+3m-1}{5m-2}⌉,\text{for}i=1,2,\dots ,n-1\text{,}$$$${\phi }_m\left(u_i{u}_{i+1}\right)=⌈\frac{i+m}{5m-2}⌉,\text{for}i=1,2,\dots ,n-1\text{,}$$$${\phi }_m\left(v_i{u}_i\right)=⌈\frac{i}{5m-2}⌉,\text{for}i=1,2,\dots ,n\text{.}$$ It is a routine matter to verify that under the labeling ${\phi }_m$ all vertex and edge labels are at most $k$.

Every ladder $L_m^j$, $j=1,2,\dots ,n-m+1$, in $L_n$ has the vertex set $$V\left(L_m^j\right)=\{v_{j+i},u_{j+i}:i=0,1,\dots ,m-1\}$$and the edge set $$E\left(L_m^j\right)=\{v_{j+i}{u}_{j+i}:i=0,1,\dots ,m-1\}\cup \{v_{j+i}{v}_{j+i+1},u_{j+i}{u}_{j+i+1}:i=0,1,\dots ,m-2\}.$$It is easy to see that every edge of $L_n$ belongs to at least one ladder $L_m^j$ if $m=2,3,\dots ,n$.

For the $L_m$-weight of the ladder $L_m^j$, $j=1,2,\dots ,n-m+1$, under the total labeling ${\phi }_m$, $m=2,3,\dots ,n$, we get $$w{t}_{{\phi }_m}\left(L_m^j\right)=\sum _{v\in V\left(L_m^j\right)}{\phi }_m\left(v\right)+\sum _{e\in E\left(L_m^j\right)}{\phi }_m\left(e\right).$$Let us consider the difference of weights of subgraphs $L_m^{j+1}$ and $L_m^j$ for $j=1,2,\dots ,n-m$ $$w{t}_{{\phi }_m}\left(L_m^{j+1}\right)-w{t}_{{\phi }_m}\left(L_m^j\right)={\phi }_m\left(v_{j+m}\right)+{\phi }_m\left(v_{j+m}{u}_{j+m}\right)+{\phi }_m\left(u_{j+m}\right)+{\phi }_m\left(v_{j+m-1}{v}_{j+m}\right)+{\phi }_m\left(u_{j+m-1}{u}_{j+m}\right)-{\phi }_m\left(v_j\right)-{\phi }_m\left(u_j\right)-{\phi }_m\left(v_j{u}_j\right)-{\phi }_m\left(v_j{v}_{j+1}\right)-{\phi }_m\left(u_j{u}_{j+1}\right)$$$$=⌈\frac{j+5m-2}{5m-2}⌉+⌈\frac{j+m}{5m-2}⌉+⌈\frac{j+3m-1}{5m-2}⌉+⌈\frac{j+4m-2}{5m-2}⌉+⌈\frac{j+2m-1}{5m-2}⌉-⌈\frac{j+4m-2}{5m-2}⌉-⌈\frac{j+2m-1}{5m-2}⌉-⌈\frac{j}{5m-2}⌉-⌈\frac{j+3m-1}{5m-2}⌉-⌈\frac{j+m}{5m-2}⌉=1.$$ This proves that $w{t}_{{\phi }_m}\left(L_m^{j+1}\right)=w{t}_{{\phi }_m}\left(L_m^j\right)+1$. Therefore, ${\phi }_m$ is a total $L_m$-irregular labeling of $L_n$ and thus $\mathrm{ths}(L_n,L_m)\le k$. This concludes the proof.□

Now we will deal with the vertex ladder-irregularity strength for ladders.

Theorem 5

Let $L_n\cong P_n\square P_2$,$n\ge 2$, be a ladder admitting $L_m$ covering, where $m$ is a positive integer, $2\le m\le n$. Then $$\mathrm{vhs}(L_n,L_m)=⌈\frac{m+n}{2m}⌉.$$

Proof

Assume that $m$ is a positive integer, $2\le m\le n$. The ladder $L_n$, $n\ge 2$, admits a $L_m$-covering with exactly $(n-m+1)$ ladders $L_m$. According to Theorem 1 we have that $\mathrm{vhs}(L_n,L_m)\ge ⌈(m+n)∕2m⌉$. Put $k=⌈(m+n)∕2m⌉$. To show that $k$ is an upper bound for the vertex $L_m$-irregularity strength of $L_n$ we define a $L_m$-irregular vertex $k$-labeling ${\alpha }_m:V\left(L_n\right)\to \{1,2,\dots ,k\}$, $m=2,3,\dots ,n$, in the following way: $${\alpha }_m\left(v_i\right)=⌈\frac{i+m}{2m}⌉,\text{for}i=1,2,\dots ,n\text{,}$$$${\alpha }_m\left(u_i\right)=⌈\frac{i}{2m}⌉,\text{for}i=1,2,\dots ,n\text{.}$$ It is not difficult to see that under the vertex labelings ${\alpha }_m$ all vertex labels are at most $k$. For the $L_m$-weight of the ladder $L_m^j$, $j=1,2,\dots ,n-m+1$, under the vertex labeling ${\alpha }_m$, $m=2,3,\dots ,n$, we get $$w{t}_{{\alpha }_m}\left(L_m^j\right)=\sum _{v\in V\left(L_m^j\right)}{\alpha }_m\left(v\right).$$Let us consider the difference of weights of subgraphs $L_m^{j+1}$ and $L_m^j$ for $j=1,2,\dots ,n-m$ $$w{t}_{{\alpha }_m}\left(L_m^{j+1}\right)-w{t}_{{\alpha }_m}\left(L_m^j\right)={\alpha }_m\left(v_{j+m}\right)+{\alpha }_m\left(u_{j+m}\right)-{\alpha }_m\left(v_j\right)-{\alpha }_m\left(u_j\right)=⌈\frac{j+2m}{2m}⌉+⌈\frac{j+m}{2m}⌉-⌈\frac{j+m}{2m}⌉-⌈\frac{j}{2m}⌉$$$$=1.$$ Hence, $w{t}_{{\alpha }_m}\left(L_m^{j+1}\right)=w{t}_{{\alpha }_m}\left(L_m^j\right)+1$. This means that ${\alpha }_m$ is a vertex $L_m$-irregular labeling of $L_n$ and thus $\mathrm{vhs}(L_n,L_m)\le k$. This concludes the proof.□

The next theorem in this section gives the exact value for the edge ladder-irregularity strength for ladders.

Theorem 6

Let $L_n\cong P_n\square P_2$,$n\ge 2$, be a ladder admitting $L_m$ covering, where $m$ is a positive integer, $2\le m\le n$. Then $$\mathrm{ehs}(L_n,L_m)=⌈\frac{2m+n-2}{3m-2}⌉.$$

Proof

The ladder $L_n$, $n\ge 2$, admits a $L_m$-covering with exactly $(n-m+1)$ ladders $L_m$. From Theorem 2 it follows that $\mathrm{ehs}(L_n,L_m)\ge ⌈(2m+n-2)∕(3m-2)⌉$. Put $k=⌈(2m+n-2)∕(3m-2)⌉$. To show that $k$ is an upper bound for the edge $L_m$-irregularity strength of $L_n$ we define a $L_m$-irregular edge labeling ${\beta }_m:E\left(L_n\right)\to \{1,2,\dots ,⌈(2m+n-2)∕(3m-2)⌉\}$, in the following way: $${\beta }_m\left(v_i{v}_{i+1}\right)=⌈\frac{2m+i-1}{3m-2}⌉,\text{for}i=1,2,\dots ,n-1\text{,}$$$${\beta }_m\left(u_i{u}_{i+1}\right)=⌈\frac{i}{3m-2}⌉,\text{for}i=1,2,\dots ,n-1\text{,}$$$${\beta }_m\left(v_i{u}_i\right)=⌈\frac{m+i-1}{3m-2}⌉,\text{for}i=1,2,\dots ,n\text{.}$$ It is a routine matter to verify that under the labeling ${\beta }_m$ all edge labels are at most $k$. For the $L_m$-weight of the ladder $L_m^j$, $j=1,2,\dots ,n-m+1$, under the edge labeling ${\beta }_m$, we get $$w{t}_{{\beta }_m}\left(L_m^j\right)=\sum _{e\in E\left(L_m^j\right)}{\beta }_m\left(e\right).$$Let us consider the difference of weights of subgraphs $L_m^{j+1}$ and $L_m^j$ for $j=1,2,\dots ,n-m$ $$w{t}_{{\beta }_m}\left(L_m^{j+1}\right)-w{t}_{{\beta }_m}\left(L_m^j\right)={\beta }_m\left(v_{j+m}{u}_{j+m}\right)+{\beta }_m\left(v_{j+m-1}{v}_{j+m}\right)+{\beta }_m\left(u_{j+m-1}{u}_{j+m}\right)-{\beta }_m\left(v_j{u}_j\right)-{\beta }_m\left(v_j{v}_{j+1}\right)-{\beta }_m\left(u_j{u}_{j+1}\right)$$$$=⌈\frac{2m+j-1}{3m-2}⌉+⌈\frac{3m+j-2}{3m-2}⌉+⌈\frac{m+j-1}{3m-2}⌉-⌈\frac{m+j-1}{3m-2}⌉-⌈\frac{2m+j-1}{3m-2}⌉-⌈\frac{j}{3m-2}⌉=1.$$ This proves that $w{t}_{{\beta }_m}\left(L_m^{j+1}\right)=w{t}_{{\beta }_m}\left(L_m^j\right)+1$. Therefore, ${\beta }_m$ is an edge $L_m$-irregular labeling of $L_n$ and thus $\mathrm{ehs}(L_n,L_m)\le k$. This concludes the proof.□

3 Fan-irregularity strength of fan graphs

A fan graph $F_n$, $n\ge 2$, is a graph obtained by joining all vertices of a path $P_n$ to a further vertex, called the center. Thus $F_n$ contains $n+1$ vertices, say, $w,v_1,v_2,\dots ,v_n$ and $2n-1$ edges $w{v}_i$, $i=1,2,\dots ,n$, and $v_i{v}_{i+1}$, $i=1,2,\dots ,n-1$. Our next result gives the total fan-irregularity strength of a fan graph.

Theorem 7

Let $F_n$,$n\ge 2$, be a fan on$n+1$ vertices admitting$F_m$-covering, where$m$ is a positive integer, $2\le m\le n$. Then $$\mathrm{ths}(F_n,F_m)=⌈\frac{2m+n}{3m}⌉.$$

Proof

The fan graph $F_n$, $n\ge 2$, admits $F_m$-covering with exactly $(n-m+1)$ fan graphs $F_m$, where $2\le m\le n$. From Theorem 3 it follows that $\mathrm{ths}(F_n,F_m)\ge ⌈(2m+n)∕3m⌉$. Put $k=⌈(2m+n)∕3m⌉$. To show that $k$ is an upper bound for the total $F_m$-irregularity strength of $F_n$ we define a total $F_m$-irregular labeling ${\phi }_m:V\left(F_n\right)\cup E\left(F_n\right)\to \{1,2,\dots ,k\}$, $m=2,3,\dots ,n$, in the following way: $${\phi }_m\left(w\right)=1,$$$${\phi }_m\left(v_i\right)=⌈\frac{i+m}{3m-1}⌉,\text{for}i=1,2,\dots ,n\text{,}$$$${\phi }_m\left(v_i{v}_{i+1}\right)=⌈\frac{i+2m}{3m-1}⌉,\text{for}i=1,2,\dots ,n-1\text{,}$$$${\phi }_m\left(w{v}_i\right)=⌈\frac{i}{3m-1}⌉,\text{for}i=1,2,\dots ,n\text{.}$$ It is easy to verify that under the total labeling ${\phi }_m$ all vertex labels and edge labels are at most $k$.

Every fan graph $F_m^j$, $j=1,2,\dots ,n-m+1$, in $F_n$ has the vertex set $$V\left(F_m^j\right)=\{v_{j+i},w:i=0,1,\dots ,m-1\}$$and the edge set $$E\left(F_m^j\right)=\{w{v}_{j+i}:i=0,1,\dots ,m-1\}\cup \{v_{j+i}{v}_{j+i+1},:i=0,1,\dots ,m-2\}.$$Evidently every edge of $F_n$ belongs to at least one fan graph $F_m^j$ if $m=2,3,\dots ,n$.

For the $F_m$-weight of the fan graph $F_m^j$, $j=1,2,\dots ,n-m+1$, under the total labeling ${\phi }_m$, $m=2,3,\dots ,n$, we get $$w{t}_{{\phi }_m}\left(F_m^j\right)=\sum _{v\in V\left(F_m^j\right)}{\phi }_m\left(v\right)+\sum _{e\in E\left(F_m^j\right)}{\phi }_m\left(e\right).$$Let us consider the difference of weights of subgraphs $F_m^{j+1}$ and $F_m^j$ for $j=1,2,\dots ,n-m$ $$w{t}_{{\phi }_m}\left(F_m^{j+1}\right)-w{t}_{{\phi }_m}\left(F_m^j\right)={\phi }_m\left(w{v}_{j+m}\right)+{\phi }_m\left(v_{j+m-1}{v}_{j+m}\right)+{\phi }_m\left(v_{j+m}\right)-{\phi }_m\left(w{v}_j\right)-{\phi }_m\left(v_j\right)-{\phi }_m\left(v_j{v}_{j+1}\right)$$$$=⌈\frac{j+m}{3m-1}⌉+⌈\frac{j+3m-1}{3m-1}⌉+⌈\frac{j+2m}{3m-1}⌉-⌈\frac{j}{3m-1}⌉-⌈\frac{j+m}{3m-1}⌉-⌈\frac{j+2m}{3m-1}⌉=1.$$ Thus for $j=1,2,\dots ,n-m$ we get $w{t}_{{\phi }_m}\left(F_m^{j+1}\right)=w{t}_{{\phi }_m}\left(F_m^j\right)+1$. Therefore, ${\phi }_m$ is a total $F_m$-irregular labeling of $F_n$ and thus $\mathrm{ths}(F_n,F_m)\le k$. This concludes the proof.□

Now we will deal with the vertex fan-irregularity strength for fan graphs.

Theorem 8

Let $F_n$,$n\ge 2$, be a fan graph admitting $F_m$ covering, where $m$ is a positive integer, $2\le m\le n$. Then $$\mathrm{vhs}(F_n,F_m)=⌈\frac{n+1}{m+1}⌉.$$

Proof

Assume that $m$ is a positive integer, $2\le m\le n$. The fan graph $F_n$, $n\ge 2$, admits a $F_m$-covering with exactly $(n-m+1)$ fan graphs $F_m$. According to Theorem 1 we have that $\mathrm{vhs}(F_n,F_m)\ge ⌈(n+1)(m+1)⌉$. Put $k=⌈(n+1)(m+1)⌉$. To show that $k$ is an upper bound for the vertex $F_m$-irregularity strength of $F_n$ we define an $F_m$-irregular vertex $k$-labeling ${\alpha }_m:V\left(F_n\right)\to \{1,2,\dots ,k\}$, $m=2,3,\dots ,n$, in the following way: $${\alpha }_m\left(w\right)=1,$$$${\alpha }_m\left(v_i\right)=⌈\frac{i}{m}⌉,\text{for}i=1,2,\dots ,n\text{,}$$ Under the vertex labeling ${\alpha }_m$ all vertex labels are at most $k$. For the $F_m$-weight of the fan graph $F_m^j$, $j=1,2,\dots ,n-m+1$, under the vertex labeling ${\alpha }_m$, $m=2,3,\dots ,n$, we get $$w{t}_{{\alpha }_m}\left(F_m^j\right)=\sum _{v\in V\left(F_m^j\right)}{\alpha }_m\left(v\right).$$Let us consider the difference of weights of subgraphs $F_m^{j+1}$ and $F_m^j$ for $j=1,2,\dots ,n-m$ $$w{t}_{{\alpha }_m}\left(F_m^{j+1}\right)-w{t}_{{\alpha }_m}\left(F_m^j\right)={\alpha }_m\left(v_{j+m}\right)-{\alpha }_m\left(v_j\right)=⌈\frac{j+m}{m}⌉-⌈\frac{j}{m}⌉=1.$$Thus we have $w{t}_{{\alpha }_m}\left(F_m^{j+1}\right)=w{t}_{{\alpha }_m}\left(F_m^j\right)+1$. This means that ${\alpha }_m$ is a vertex $F_m$-irregular labeling of $F_n$ and thus $\mathrm{vhs}(F_n,F_m)\le k$.□

The last theorem in this section gives the exact value for the edge fan-irregularity strength for fan graphs.

Theorem 9

Let $F_n$,$n\ge 2$, be a fan graph on $n+1$ vertices admitting $F_m$-covering, where $m$ is a positive integer, $2\le m\le n$. Then $$\mathrm{ehs}(F_n,F_m)=⌈\frac{n+m-1}{2m-1}⌉.$$

Proof

The fan graph $F_n$, $n\ge 2$, admits a $F_m$-covering with exactly $(n-m+1)$ fan graphs $F_m$. From Theorem 2 it follows that $\mathrm{ehs}(F_n,F_m)\ge ⌈(n+m-1)∕(2m-1)⌉$. Put $k=⌈(n+m-1)∕(2m-1)⌉$. To show that $k$ is an upper bound for the edge $F_m$-irregularity strength of $F_n$ we define an $F_m$-irregular edge labeling ${\beta }_m:E\left(F_n\right)\to \{1,2,\dots ,⌈(n+m-1)∕(2m-1)⌉\}$, in the following way: $${\beta }_m\left(v_i{v}_{i+1}\right)=⌈\frac{i+m}{2m-1}⌉,\text{for}i=1,2,\dots ,n-1\text{,}$$$${\beta }_m\left(w{v}_i\right)=⌈\frac{i}{2m-1}⌉,\text{for}i=1,2,\dots ,n\text{.}$$ All edge labels are at most $k$. For the $F_m$-weight of the fan graph $F_m^j$, $j=1,2,\dots ,n-m+1$, under the edge labeling ${\beta }_m$, we get $$w{t}_{{\beta }_m}\left(F_m^j\right)=\sum _{e\in E\left(F_m^j\right)}{\beta }_m\left(e\right).$$Let us consider the difference of weights of subgraphs $F_m^{j+1}$ and $F_m^j$ for $j=1,2,\dots ,n-m$ $$w{t}_{{\beta }_m}\left(F_m^{j+1}\right)-w{t}_{{\beta }_m}\left(F_m^j\right)={\beta }_m\left(v_{j+m-1}{v}_{j+m}\right)+{\beta }_m\left(w{v}_{j+m}\right)-{\beta }_m\left(v_j{v}_{j+1}\right)-{\beta }_m\left(w{v}_j\right)$$$$=⌈\frac{2m+j-1}{2m-1}⌉+⌈\frac{j+m}{2m-1}⌉-⌈\frac{j+m}{2m-1}⌉-⌈\frac{j}{2m-1}⌉=1.$$ Which means that $w{t}_{{\beta }_m}\left(F_m^{j+1}\right)=w{t}_{{\beta }_m}\left(F_m^j\right)+1$. Therefore, ${\beta }_m$ is an edge $F_m$-irregular $k$-labeling of $F_n$ and thus $\mathrm{ehs}(F_n,F_m)\le k$.□

4 Conclusion

In the foregoing sections we studied the existence of the vertex (edge, total) $H$-irregularity strengths for the ladders $L_n$ and fan graphs $F_n$, $n\ge 2$. We determined the exact values of the vertex (edge, total) $H$-irregularity strengths of ladders $L_n$ (respectively fan graphs $F_n$) admitting $L_m$ covering (respectively $F_m$ covering) for every integer $m$, $2\le m\le n$.

Acknowledgments

The research for this article was supported by APVV-15-0116 and by VEGA 1/0233/18.