![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
For a graph we define
-labeling
such that the edges of
are labeled with integers
and the vertices of
are labeled with even integers
, where
. The labeling
is called a vertex irregular reflexive
-labeling if distinct vertices have distinct weights, where the vertex weight is defined as the sum of the label of that vertex and the labels of all edges incident this vertex. The smallest
for which such labeling exists is called the reflexive vertex strength of
.
In this paper, we give exact values of reflexive vertex strength for prisms, wheels, fan graphs and baskets.
1 Introduction
All graphs considered in this article are connected, finite and undirected. A graph consists of a vertex set
and an edge set
or just
and
when the graph
is clear. The graphs are also simple though they have their origin in multigraphs. In [Citation1] the problem was posed “In a loopless multigraph, determine the fewest parallel edges required to ensure that all vertices have distinct degree”. In terms of simple graphs the problem becomes a graph labeling problem in which the number of parallel edges is represented as a positive integer on an edge and irregularity requires that the sum of all edge labels at vertices be pairwise distinct. The problem may be now expressed “assign positive values to the edges of a simply connected graph of order at least 3, in such a way that the graph becomes irregular. What is the minimum largest label over all such irregular assignments”? This minimum largest label is known as irregularity strength. Finding the irregularity strength of a graph seems to be hard even for graphs with simple structure, see [Citation2–7].
Once the problem was considered as an edge labeling it is a simple step to pose it as a problem in total labeling in which both vertices and edges are labeled. This was first introduced by Bača et al. [Citation8] where the authors defined vertex weight as the sum of all incident edge labels along with the label of the vertex. Now the problem is the same as in paragraph 1 except that the positive values are ascribed to both vertices and edges and we can remove the restriction of the graph being of order at least 3. The question remains one of finding the minimum largest label over all assignments. Such labeling is known as vertex irregular total -labeling and total vertex irregularity strength of graph is the minimum
for which the graph has a vertex irregular total
-labeling. The bounds for the total vertex irregularity strength given in [Citation8] were then improved in [Citation9,10] and recently by Majerski and Przybylo in [Citation11].
In [Citation12] the authors combined the total labeling problem with the original multigraph problem by identifying the vertex labels as representing loops. They referred to this labeling as an irregular reflexive labeling. This helped pose the problem in terms of real world networks but also had an effect on the vertex labels. Firstly, the vertex labels were required to be non-negative even integers (since each loop adds 2 to the vertex degree) and secondly, the vertex label 0 was permitted as representing a loopless vertex.
For a graph we define
-labeling
such that the edges of
are labeled with integers
and the vertices of
are labeled with even integers
, where
.
Specifically, under a total labeling the weight of a vertex
, denoted by
, is defined as
while the weight of an edge
, denoted by
, is defined as
A labeling is said to be a vertex irregular reflexive
-labeling (resp. edge irregular reflexive
-labeling) if for
is
(resp. for
is
). The smallest
for which such labelings exist is called the reflexive vertex strength (resp. reflexive edge strength).
In this paper we provide exact values for the reflexive vertex strength for prisms, wheels, fans and baskets.
2 Vertex irregular reflexive labeling of prisms
Before we give the exact value of reflexive vertex strength for prisms we first prove one auxiliary lemma.
Lemma 1
The largest vertex weight of a graph of order
and the minimum degree
under any vertex irregular reflexive labeling is at least
1. |
| ||||
2. |
|
Proof
Let be a vertex irregular reflexive labeling of a graph
of order
and the minimum degree
. Let us denote the vertices of
by the symbols
such that
for
.
Then the vertex weight of a vertex is
As the vertex weights are distinct we get
Let us consider that
which means that
Thus the sum of all vertex weights is
Evidently, this sum must be an even integer as
and every vertex label is even. Thus
but it is not possible if
and
,
, or
and
.
For regular graphs we immediately deduce the following corollary.
Corollary 1
Let be an
-regular graph of order
. Then
The prism ,
, is a trivalent graph which can be defined as the Cartesian product
of a path on two vertices with a cycle on
vertices. We denote the vertex set and the edge set of
such that
and
, where indices are taken modulo
.
Theorem 1
For ,
Proof
As the prism is a 3-regular graph of order
, by Corollary 1 we obtain that
.
We define the total labeling of
in the following way
Evidently
is
-labeling and the vertices are labeled with even numbers.
For the vertex weights of the vertices ,
in
under the labeling
we have
If
and
then
and for
and
Thus
.
For the vertex weights of the vertices ,
in
under the labeling
we have the following
Which means
Thus the vertex weights are all distinct, that is
is a vertex irregular reflexive
-labeling of a prism
.
3 Vertex irregular reflexive labeling of wheels
The wheel ,
, is a graph obtained by joining all vertices of
to a further vertex called the center. We denote the vertex set and the edge set of
such that
and
, where indices are taken modulo
. The wheel is of order
and size
. We prove the following result for wheels.
Theorem 2
For ,
Proof
Let . As
then the smallest vertex weight is at least 3. The wheel
contains
vertices of degree 3 thus the largest weight over all vertices of degree 3 is at least
. Every vertex weight of a vertex of degree 3 is the sum of four labels from which at least one is even thus we have
However, if
,
, we get that the fraction
is odd. The number
can be realizable as the sum of four labels not greater than
only in the following way
but this is a contradiction as the vertex label must be even. Thus, for
we obtain
Let
Let us denote by
the largest even number not greater than
. Thus
For we get that
. The corresponding vertex irregular reflexive
-labelings for
and
are illustrated on .
For we define the total
-labeling
of
such that
For the weight of vertices of degree 3 under the labeling we obtain
It is easy to see that the weights of vertices
,
,
and
are distinct numbers from the set
. For
we have
.
The weight of the vertex is
Evidently, for
, the vertex weights are distinct.
A fan graph is obtained from wheel
if one rim edge, say
is deleted. A basket
is obtained by removing a spoke, say
, from wheel
. Before we will give the exact value of reflexive vertex strength of fans and baskets we give the following observation.
Observation 1
Let be a vertex irregular reflexive
-labeling of a graph
. If there exists an edge
in
such that
then
is a vertex irregular reflexive
-labeling of a graph
.
Proof
The proof is trivial.
Immediately from this observation we get the following corollary.
Corollary 2
Let and let
be the corresponding vertex irregular reflexive
-labeling of a graph
. If the vertex weights of vertices
are the smallest over all vertex weights under the labeling
and
then
Proof
Let be a vertex irregular reflexive
-labeling of a graph
. Let
,
be two adjacent vertices and let the vertex weights of these vertices be the smallest over all vertices in
. Without loss of generality assume
. This means that for every
,
(1)
(1) Let
be the restriction of the labeling
on
. Evidently
Combining with (1) we obtain
Thus, immediately using Observation 1 we have
.
For the fan graph we prove
Theorem 3
For ,
Proof
The fan graph contains two vertices of degree 2, thus the smallest vertex weight is at least 2. The fan graph
contains
vertices of degree 3, thus the largest weight of a vertex of degree 3 is at least
.
If all vertex weights of vertices of degree 3 are at most , then one of the vertices of degree 2 has to have weight at least
and thus
. If a vertex of degree 3 has weight greater than
then
. As we are trying to minimize the parameter
for which there exists vertex irregular reflexive
-labeling of
we obtain
which can be obtained when both vertices of degree 2 in
will have weights less than
.
According to the proof of Theorem 2 and Corollary 2, for , we get
Moreover, we can derive a vertex irregular reflexive
-labeling of
from a vertex irregular reflexive
-labeling of
.
Combining the previous facts we have that for
and for
For we get that
. The corresponding vertex irregular reflexive
-labelings for
and
are illustrated on .
Let ,
, then
. As this value is odd we cannot get the number
as the sum of four labels less or equal to
from which at least one is even. Thus
but in this case
and we are done.
We denote the vertex set and the edge set of such that
and
.
If ,
then
. We define a
-labeling of
such that
It is easy to verify that the set of all vertex weights is
.
If ,
then
. We define
-labeling of
in the following way
Evidently the vertex weights are distinct.
Theorem 4
For ,
Proof
The basket contains one vertex of degree 2, therefore the smallest vertex weight is at least 2 and it contains
vertices of degree 3, hence the largest weight of a vertex of degree 3 is at least
. Thus
Analogously as in the proof of the previous theorem, using Theorem 2 and Observation 1, for
, we have
Moreover, we can derive a vertex irregular reflexive
-labeling of
from the vertex irregular reflexive
-labeling of
defined in the proof of Theorem 2 by deleting the spoke
in
.
Combining the previous facts we get that for
and
For we get that
. The basket
is isomorphic to the fan
. The vertex irregular reflexive
-labelings for
is illustrated on .
Let ,
, then
. As this is odd we cannot get the number
as the sum of four labels less or equal to
from which at least one is even. Thus
but in this case
and we are done.
Let us denote the vertex set and the edge set of the basket such that
and
.
If ,
then
. We define
-labeling of
such that
If ,
then
. We define
-labeling of
in the following way
It is not difficult to show that in both cases the described labelings have desired properties.
4 Conclusion
In this paper we determined exact values of the reflexive vertex strength for prisms , wheels
, fan graphs
and for baskets
,
.
Acknowledgments
This work was supported by the Slovak Science and Technology Assistance Agency, Slovak Republic under the contract no. APVV-15-0116 and by VEGA, Slovak Republic 1/0233/18.
References
- ChartrandG., JacobsonM.S., LehelJ., OellermannO.R., RuizS., SabaF., Irregular networks, Cong. Numer., 64 1988 187–192
- AignerM., TrieschE., Irregular assignments of trees and forests, SIAM J. Discrete Math., 3 1990 439–449
- AmarD., TogniO., Irregularity strength of trees, Discrete Math., 190 1998 15–38
- AnholcerM., PalmerC., Irregular labelings of circulant graphs, Discrete Math., 312232012 3461–3466
- BohmanT., KravitzD., On the irregularity strength of trees, J. Graph Theory, 45 2004 241–254
- FriezeA., GouldR.J., KaronskiM., PfenderF., On graph irregularity strength, J. Graph Theory, 41 2002 120–137
- MajerskiP., PrzybyłoJ., On the irregularity strength of dense graphs, SIAM J. Discrete Math., 2812014 197–205
- BačaM., Jendrol’S., MillerM., RyanJ., Total irregular labelings, Discrete Math., 307 2007 1378–1388
- PrzybyłoJ., Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math., 23 2009 511–516
- AnholcerM., KalkowskiM., PrzybyłoJ., A new upper bound for the total vertex irregularity strength of graphs, Discrete Math., 309 2009 6316–6317
- MajerskiP., PrzybyłoJ., Total vertex irregularity strength of dense graphs, J. Graph Theory, 7612014 34–41
- J. Ryan, B. Munasinghe, D. Tanna, Reflexive irregular labelings, preprint.