ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 23-29
Product irregularity strength of certain graphs
Martin Anholcer *
Poznati University of Economics, Al. Niepodleglosci 10, 61-875 Poznati, Poland
Received 31 October 2011, accepted 2 October 2012, published online 7 January 2013
Consider a simple graph G with no isolated edges and at most one isolated vertex. A labeling w : E (G) ^ {1,2,... ,m} is called product - irregular, if all product degrees pdG(v) = f]e3v w(e) are distinct. The goal is to obtain a product - irregular labeling that minimizes the maximal label. This minimal value is called the product irregularity strength and denoted ps(G). We give the exact values of ps(G) for several families of graphs, as complete bipartite graphs Km,n, where 2 < m < n < (m+2), some families of forests, including complete d-ary trees, and other graphs with 5(G) = 1.
Keywords: Product-irregular labeling, product irregularity strength, tree. Math. Subj. Class.: 05C05, 05C15, 05C78
1 Introduction
Assume we are given simple undirected graph G = (V(G),E(G)) with neither loops nor isolated edges and with at most one isolated vertex. Let us define integer labelling
w : E(G) ^ {1, 2,... ,s}. For every vertex v G V (G) we define the product degree as
The product irregularity strength ps(G) of G is the smallest value of s that allows some product-irregular labelling.
*http://kbo.ue.poznan.pl/anholcer
E-mail address: m.anholcer@ue.poznan.pl (Marcin Anholcer) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
Abstract
(1.1)
(where dG(v) denotes the degree of vertex v in G).
We call w product-irregular if for every pair of vertices u,v G V (G), u = v
pdG(u) = pdG(v).
(1.2)
24
ArsMath. Contemp. 7(2014)23-29
The concept was introduced by M. Anholcer in [4]. As we can see, it is the multiplicative version of the well known irregularity strength introduced by Chartrand et al. in [5] and studied by numerous authors (the best result for general graphs can be found in Kalkowski, Karonski and Pfender [6], while e.g. trees and forests have been studied e.g. by Aigner and Triesch [1], and Amar and Togni [3]). On the other hand, the problem of founding the product irregularity strength of graph is connected with the product antimagic labellings investigated e.g. by Pikhurko [7]. Indeed, the result from the last publication implies that for sufficiently large graphs
ps(G) < |E(G)|.
Let nd denote the number of vertices of degree d, where S(G) < d < A(G). In [4] M. Anholcer showed that
ps(G) > max
5(G)<d<A(G)
d
1/d d
This reduces to
ps(G) >
r
—n
e
1/r
- r + 1
in the case of r-regular graph. Note that these bounds are not tight. Also the bounds on ps(Cn) were given, where Cn is cycle on n vertices. It was proved that if n > 17, then
ps(Cn) >
1 — ln 2
1/2"
while for every e > 0 there exists n0 such that for n > n0
ps(Cn) < [(1 + e)V2nlnn|.
Similarly the upper bounds on the irregularity strength of grids and toroidal grids were proved:
k k
Ps(Tn i xn2 x-xnk
j= 1 k
j = 1 k
ps(Gm
nixn2x-^^xnfc
) <[(1 + e)V2^2 vnj)ln^ nj)].
j=1
j=1
In [9] Skowronek-Kaziow showed, that Proposition 1.1. For every n > 3
ps(Kn) = 3.
Let us recall that nd denotes the number of vertices of degree d in G, where S(G) < d < A(G). In this paper we are going to give the exact value of ps(G) for complete bipartite graphs Km,n, where 2 < m < n < (m+2), and some families of graphs with S(G) = 1. The main results are as follows.
e
n
M. Anholcer: Product irregularity strength of certain graphs
25
Proposition 1.2. Let m and n be two integers such that 2 < m < n. Then
ps(Km,„ ) = 3
if and only if n < (m+2). Otherwise ps(Km,n) > 4.
Theorem 1.3. Let D > 3 be arbitrary integer For almost all forests F such that
(i)	A(F) = D, n2 =0 and no < 1,
(ii)	if we remove all the pendant edges, then in the resulting forest F', n2 = 0, the product irregularity strength equals to
ps(F ) = ni.
The proofs of the above results are given in two following sections.
2 Complete bipartite graphs Proof of Proposition 1.2
Let Km,n = (U, V, E), where U = {u1,..., um}, V = {v1,..., vn} and E = {{«j, vj},
1	< i < m, 1 < j < n}. If we used only labels 1 and 2, we would be able to obtain at most n +1 distinct products, 1,2,..., 2n while we have n + m > n + 2 vertices. Thus ps(Kn,n) > 3. On the other hand, assume that we are using only the labels 1,
2	and 3. The number of possible multisets of m elements is equal to (m+2), and it is the maximal number distinct products for the vertices in V. Thus it is impossible to find product-irregular labeling of Km,n if | V| = n > (m+2). Now we are going to prove that labels 1, 2 and 3 are enough if m < n < (m+2).
Let us consider the set of all (m+2) multisets of m elements equal to either 1, 2 or 3. Let
us denote the elements of jth multiset, where 1 < j < (m+2), with aj, where 1 < i < m.
Assume they are arranged in non decreasing order, i.e. in such a way that aj < aj+1 for
1 < j < (m+2) and 1 < i < m - 1. Now we arrange the obtained sequences in decreasing
lexicographic order, i.e. in such a way that for every 1 < j1 < j2 < (m+2) there exists i0,
1 < i0 < m such that aj = aj if 1 < i < i0 and aj0 > aj0. Now if m < n, then we put j1 j2 j1 j2
w({wj, Vj}) = aj, 1 < i < m, 1 < j < n.
Observe that the weighted degrees in V are distinct, as the respective multisets are. It is also straightforward to see that the degrees in U are distinct, as the numbers of factors equal to 3 are. Moreover the number of factors different than 1 in the weighted degrees in V are equal at most m, while in U they equal at least m +1. Thus finally the obtained labeling is product-irregular.
If m = n, then we label any Kn-1,n subgraph of Kn,n as above and then put 1 on all the edges incident to the remaining vertex. As in the case m = n - 1 none of the vertices obtains the weighted degree 1, the resulting labeling is product-irregular.	□
26
ArsMath. Contemp. 7(2014)23-29
3 Graphs with S(G) = 1 Proof of Theorem 1.3
Let us consider a forest F. We distinguish two kinds of non pendant vertices. The external vertex is such a vertex that at least one of its neighbours is pendant vertex. The internal vertex has no pendant vertices in the neighbourhood.
The product degree of every pendant vertex is equal to the label of the only edge incident to it. Thus ps(F) > n1. So in order to prove the theorem we have to show that there exists a product-irregular labelling of F with ni labels.
The proof consists of two parts. First using the Probabilistic Method (more precisely the Linearity of Expectation, see e.g. [2], pp.13-21) we will prove the existence of partial labeling that distinguishes the product degrees of internal vertices. Then, by labeling the pendant edges we will extend the product-irregular labeling on whole forest F.
Let us choose the label for every non-pendant edge uniformly at random from the set of all odd primes p, ni/2 < p < n1. The number of such primes n1/2 equals
1/2 ni - 2.51012ni1/2
ni/2 = n(n1) - n(n1 ) > -]-
'	In n1
provided n1 > 17 (see e.g. [8]).
Let us enumerate in any way all the m1 pairs of non-adjacent internal vertices and m2 pairs of adjacent internal vertices. As for every forest we have
D	D
ni > 2 + (i - 2)n >^2'nH,
it follows that the total number of internal vertices nint satisfies the inequality
n1
nint < "2.
Thus
n1
m-2 < nint - 1 < "2"
and
. fninA ni
mi n 2) < i".
For every i, 1 < i < m1 + m2, let vi and ui be the vertices forming pair i and let Xi be random variable such that
X = I 1, pd(ui) = pd(vi), l0, otherwise.
We have
ui vi
E(Xi) = Pr(pd(ui) = pd(vi)) ^ D;^1/2-3,	.
D!ni/2 3, otherwise.
Let X be random variable counting the"bad" pairs. Of course,
mi+m2
E(X)= ^ E(Xi) < m1D!n1/2-3 + m2D!n1/2-2 < 1,	(3.1)
i=i
M. Anholcer: Product irregularity strength of certain graphs
27
if only ni is large enough.
This implies that for almost every forest satisfying given conditions, there exists a labeling w* using only the primes lower or equal to n1 that distinguishes all the internal vertices. Moreover, for every internal vertex v we have
pd(v) > ni
and
pd(v) mod 2=1.
Let us choose any such labeling. Now we are going to extend w* on the pendant edges in order to obtain complete labeling w. We will do it in two steps. Let next be the number of external vertices. In the first step, for each such vertex we leave two pendant edges incident to it not labeled. If there are other pendant edges (i.e. for at least one external vertex v, d(v) > 3), then we put on them distinct labels from the set {1,,..., n1 - 2next} (in any order). Let pd*(v) be the product of all edges incident with v that have been labeled. In the second step we order the external vertices with non-decreasing value of pd*(v). Then we label two edges incident with ith external vertex (1 < i < next) using labels n1 - 2next + i and n1 - i + 1. Observe that the products of the pairs of labels increase with i.
After the second step, the product degrees of external vertices satisfy the conditions:
pd(vj) < pd(vj) if i < j, pd(vj) > n1
and
pd(vj) mod 2 = 0. For pendant vertices we have in turn:
pd(vj) < n1
and
pd(vi) = pd(vj) if i = j. As there can be at most one vertex v with pd(v) = 0, this finishes the proof.	□
Corollaries
From the above one can deduce the following two corollaries.
Corollary 3.1. Let d > 2 be arbitrary integer. Then for almost all the complete d-ary trees
ps(T) = n1.
Proof. We proceed as in the proof of Theorem 1.3. Even if d =2, there is only one vertex of degree 2 (the root) and its product degree is the product of two (not necessarily distinct) primes p1,p2 > n^2. It distinguishes this vertex from all other internal and pendant vertices. And even if n1 G {p1,p2}, it is impossible to obtain the external vertex with same product degree, as the triple 1, p1, p2 cannot appear (pendant edges should be labeled 1 and n1 this time, what would imply n1 mod 2 = 0, contradiction). Thus all the product degrees are distinct.	□
28
ArsMath. Contemp. 7(2014)23-29
One of the most important facts used in the proof of Theorem 1.3 is that n1 > n/2. However, as it may be easily checked, the inequality analogous to (3.1) will be satisfied even for smaller number of pendant vertices.
Corollary 3.2. Let D > d > 3 be arbitrary integers. For almost all graphs G such that
(i)	6(G) = 1, A(G) = D,
(ii)	if we remove all the pendant edges, then for the resulting graph G', S(G') = d > 4,
(d— 1)/2
(iii)	n1 >> n2/(d-1) lnn (i.e. n = o( niln )),
(iv)	none of the external vertices is adjacent to exactly one pendant vertex, the product irregularity strength equals to
ps(G) = ni.
Proof. We proceed as in the proof of Theorem 1.3. The difference is that this time we do not distinguish pairs of adjacent and non-adjacent vertices. The inequality (3.1) takes the form:
E(X) < D!nV2-d+1 < 1, and the deterministic part of the proof remains unchanged.	□
Two simple observations
Finally let us add two simple observations on some special families of trees.
Proposition 3.3. Let K1,n be star with n pendant vertices, n > 2. Then
ps(K1,n) = max{3,n}.
Proof. In the case n = 2, two labels 1 and 2 are not enough (either we use two equal labels and obtain same product degrees of pendant vertices, or we label the edges with 1 and 2 and obtain two product degrees 2). On the other hand, using labels 2 and 3 we produce product-irregular labeling. If n > 3, we need at least n labels to distinguish the product degrees of pendant vertices and this is enough, as the product degree of central vertex equals n! > n.	□
Centipede Qn is the graph with V(Qn) = {u1,..., un, v1,..., vn} and E(Qn) = {{Ui, Vi}, 1 < i < n} U {{Vi, vi+1}, 1 < i < n - 1}.
Proposition 3.4. Let Qn be a centipede, n > 2. Then
ps(Qn) = max{3, n}.
Proof. If n = 2, two labels are not enough as it would be possible to obtain at most three distinct products 1, 2 and 4 and we have four vertices. If n > 3, we need at least n labels to distinguish all the pendant vertices. So ps(Qn) > max{3, n}. The product-irregular labelings realizing this bound are given as follows:
M. Anholcer: Product irregularity strength of certain graphs
29
(i)	If n = 2, put w({wj,vj}) = i, i = 1, 2 and w({vi,v2}) = 3. Then pd(ui) = 1, pd(u2) = 2, pd(vi) = 3 and pd(v2) = 6.
(ii)	If n = 3, put ^({«2,^2}) = 1, w({ui,vi}) = w({vi,v2}) = 2, w({u3,V3}) = w({v2, V3}) = 3. Thenpd(ui) = 2,pd(«2) = 1,pd(«3) = 3,pd(vi) = 4,pd(v2) = 6 and pd(v3) = 9.
(iii)	If n > 4, put w({«i, vi}) = n — 1, w({un, vn}) = n — 2, w({un_i, vn_i}) = n, w({«j, vj}) = i — 1, 2 < i < n — 2 and w({vj, vj+i}) = n, 1 < i < n — 1. Then product degrees of pendant vertices are distinct numbers from the set {1,2,..., n} and the product degrees of external vertices - distinct numbers from the set {n(n — 2), n(n — 1)} U {in2, 1 < i < n — 3} U {n3}.
□
Aknowledgments
I would like to thank Professor Tomasz Luczak for inspiring discussions. I also thank two
anonymous referees for all the remarks that allowed to improve the quality of the paper.
References
[1]	M. Aigner M and Triesch, Irregular assignments of trees and forests, SIAM J. Discrete Math. 3 (1990), 439-449.
[2]	N. Alon and J. H. Spencer, The Probabilistic Method, John Wiley & Sons, 2000.
[3]	D. Amar and O. Togni, Irregularity strength of trees, Discrete Math. 190 (1998), 15-38.
[4]	M. Anholcer, Product irregularity strength of graphs, Discrete Math. 309 (2009), 6434-6439.
[5]	G. Chartrand, M. S. Jacobson, J. Lehel, O. R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congressus Numerantium 64 (1988), 187-192.
[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.
[7]	O. Pikhurko, Characterization of product anti-magic graphs of large order, Graphs Combinator. 23 (2007), 681-689.
[8]	J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64-97.
[9]	J. Skowronek-Kaziow, Multiplicative vertex-colouring weightings of graphs, Inform. Process. Lett. 112 (2012), 191-194.