![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
A graph is called supermagic if it admits a labeling of the edges by pairwise different consecutive positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper we deal with special supermagic labelings of regular graphs and their using to construction of supermagic labelings of disconnected graphs.
1 Introduction
We consider finite undirected graphs without loops, multiple edges and isolated vertices. If is a graph, then
and
stand for the vertex set and edge set of
, respectively. Cardinalities of these sets are called the order and size of
. The union of two disjoint graphs
and
is denoted by
and the union of
disjoint copies of a graph
is denoted by
. For integers
,
we denote by
the set of all integers
satisfying
.
Let a graph and a mapping
from
into positive integers be given. The index-mapping of
is the mapping
from
into positive integers defined by
An injective mapping
from
into positive integers is called a magic labeling of
for an index
if its index-mapping
satisfies
A magic labeling
of
is called a supermagic labeling if the set
consists of consecutive positive integers. We say that a graph
is supermagic (magic) whenever there exists a supermagic (magic) labeling of
.
A bijective mapping from
to
is called a degree-magic labeling (or only d-magic labeling) of a graph
if its index-mapping
satisfies
A d-magic labeling
of
is called balanced if for all
it holds
We say that a graph
is degree-magic (balanced degree-magic) (or only d-magic) when there exists a d-magic (balanced d-magic) labeling of
.
The concept of magic graphs was introduced by Sedláček Citation[1]. Supermagic graphs were introduced by M. B. Stewart Citation[2]. There is by now a considerable number of papers published on magic and supermagic graphs; we single out Citation[3–8] as being more particularly relevant to the present paper, and refer the reader to Citation[9] for comprehensive references. The concept of degree-magic graphs was introduced in [Citation10]. Some properties of degree-magic graphs and characterizations of some classes of degree-magic and balanced degree-magic graphs were described in [10–15]. Clearly, any degree-magic labeling of a regular graph is supermagic. Nay, degree-magic graphs extend supermagic regular graphs because the following result holds.
Proposition 1
[Citation10] Let be a regular graph. Then
is supermagic if and only if it is degree-magic.
In the paper we deal with special degree-magic labelings of graphs. Inter alia we describe a construction of supermagic labeling of the disjoint union of graphs admitting such special labelings.
2 Gradual labelings
A spanning subgraph of a graph
is called a proportional factor of
whenever
for every vertex
. For a positive integer
,
, a proportional factor
of a graph
is called a
-factor of
when
(i.e.,
for every vertex
). For conciseness, we will denote by
the family of all graphs
whose edge set can be decomposed into
pairwise disjoint subsets each of which induces a
-factor of
. A bijection
from
onto
is called
-gradual if the set
induces a
-factor of
for each
. Evidently,
admits a
-gradual bijection if and only if
.
We say that a graph is
-gradual d-magic (
-gradual supermagic) when there exists a
-gradual d-magic (a
-gradual supermagic) labeling of
. The concept of gradual labelings was introduced in Citation[6], where supermagic labelings of generalized double graphs were constructed using some gradual labelings.
The family of all -gradual d-magic graphs we will denote by
. Clearly,
is the family of all balanced d-magic graphs and
for every
. Moreover, we have
Theorem 1
The following statements hold:
(i) | Let | ||||
(ii) | Let | ||||
(iii) | Let |
Proof
(i) As is a divisor of
, there is a positive integer
such that
. Let
be a graph belonging to
. Then there is a
-gradual d-magic labeling
of
. Therefore,
induces a
-factor of
for each
. Moreover,
for every
. So
induces a subgraph of
in which every vertex
has degree
. This means that
is
-gradual. Thus,
.
(ii) Let be a
-gradual d-magic labeling of
. Let
and
be two vertices of
such that the distance between them is at least three. Let
be a graph obtained from
by an identification of vertices
and
, and let
denote the vertex of
obtained by the identification. Thus, we can assume that
and
have the same edges. However, if an edge
is incident with
or
in
then
is incident with
in
. Now it is easy to see that the mapping
from
into integers given by
is a desired
-gradual d-magic labeling of
.
(iii) As for each
,
Thus,
for every vertex
. As
belongs to
, there is a
-gradual d-magic labeling
of
. For any vertex
we have
Moreover, the set
induces a
-factor of
for each
. This means that any vertex
has degree
in the induced subgraph. However,
and so the set
induces a
-factor of
for each
.
Now consider the mapping from
into the set of positive integers given by
Clearly,
is a bijection from
onto
. Moreover, for every vertex
we have
Therefore,
is a degree-magic labeling of
.
For any there is
such that
. Then
belongs to
and
. Thus,
induces a
-factor of
for each
, i.e.,
is a
-gradual d-magic labeling of
. □
Theorem 2
A graph is
-gradual d-magic if and only if there exist a mapping
from
onto
and a decomposition of
into pairwise disjoint subsets
,
, …,
with the following properties
• | each | ||||
• |
| ||||
• |
|
Proof
First suppose that is a
-gradual d-magic graph. Then there is a
-gradual d-magic labeling
of
. For any
, put
and define a mapping
from
into the set of integers by
As
is a
-gradual labeling, each
induces a
-factor of
and consequently
. Moreover, for any vertex
, we have
On the other hand, assume that is a mapping from
onto the set
and that
,
, …,
is a decomposition of
into pairwise disjoint subsets with the considered properties. Define a mapping
from
into the set of integers by
It is easy to see that
is a bijection onto
. Similarly, for any vertex
, we have
Therefore,
is a d-magic labeling of
. Moreover, the set
induces a
-factor of
, i.e.,
is
-gradual. □
3 Complete graphs
A complete -partite graph is a graph whose vertices can be partitioned into
(
) disjoint classes
such that two vertices are adjacent whenever they belong to distinct classes. If
, for each
, then the complete
-partite graph is denoted by
. The complete graph
is usually denoted by
and the complete bipartite graph
is mostly denoted by
.
For any graph we define a graph
by
and
. It is easy to see that
is a generalized double graph denoted by
in Citation[6]. Therein there was also proved the following result.
Proposition 2
Citation[6] Let be a
-regular Hamiltonian graph of odd order. Then
is a
-gradual supermagic graph.
As is isomorphic to
, we immediately have
Corollary 1
The complete bipartite graph is
-gradual supermagic for every odd integer
.
The complete bipartite graph is balanced d-magic (i.e., 2-gradual supermagic) for every even integer
(see [Citation10]). Similarly, the complete graph
is 2-gradual supermagic for every integer
(see [Citation11]) and
is not supermagic for every integer
(see [Citation16]). Using Theorem 2, we obtain similar results for other complete graphs.
Theorem 3
The complete graph is
-gradual supermagic for every odd integer
.
Proof
Denote the vertices of by
,
,
, …,
and for every
define the set of edges
, the indices being taken modulo
. It is easy to see that
,
, …
form a decomposition of
and each
is a perfect matching (i.e., induces a
-factor) of
. Now consider a mapping
from
into the set of positive integers given by
Evidently,
. Each vertex
,
, is incident with two edges of type
(
,
) for each
and with one edge of type
(
). Thus, we have
Any edge incident with
is of type
, so
. Therefore, by Theorem 2,
is a
-gradual supermagic graph. □
Theorem 4
The complete graph is
-gradual supermagic for every positive integer
.
Proof
Denote the vertices of by
,
,
, …,
,
,
, …,
and for every
define the set of edges
the indices being taken modulo
. It is not difficult to see that the sets
,
, …
form a decomposition of
and each
induces a 2-regular spanning subgraph (i.e., a
-factor) of
isomorphic to
. Now consider a mapping
from
into positive integers given by
Evidently,
. Each vertex
,
, is incident with two edges of type
(
,
) for each
, with one edge of type
(
) for each
, with one edge of type
(
) for each
, with one edge of type
(
), and with one edge of type
(
). Thus, we have
Similarly, for every vertex
,
, we have
The vertex
is incident with
edges of type
and with
edges of type
. Thus
Therefore, by Theorem 2,
is a
-gradual supermagic graph. □
4 Union of graphs
M. Doob Citation[3] proved that a regular graph of degree with connected components
, …,
is magic if and only if
is magic for each
. A similar characterization of all disconnected magic graphs was given by R.H. Jeurissen Citation[4]. For supermagic graphs the following holds:
Proposition 3
Citation[5] Let be a
-regular supermagic graph which can be decomposed into
pairwise edge-disjoint
-regular spanning subgraphs. Then the following statements hold:
• | if | ||||
• | if |
A similar result for -regular supermagic
-edge-colorable graphs (they admit a decomposition into
-regular spanning subgraphs) was presented in Citation[7]. For degree-magic graphs we have
Proposition 4
[Citation10] Let and
be edge-disjoint subgraphs of a graph
which form its decomposition. If
is d-magic and
is balanced d-magic then
is a d-magic graph. Moreover, if
and
are both balanced d-magic then
is a balanced d-magic graph.
Evidently, if is an
-regular balanced d-magic (and so supermagic) graph and
is an
-regular supermagic graph then
is a supermagic graph. Therefore, we have a technique for constructing supermagic labeling of the disjoint union of some supermagic regular graphs. However, all balanced d-magic graphs are of even size, thus this method cannot be used for graphs of odd size.
In this section we introduce a construction of d-magic (supermagic, for regular graphs) labeling of the disjoint union of -gradual d-magic graphs which is usable for graphs of odd size. For the family
we have
Theorem 5
Let ,
, be a d-magic graph. Then the graph
belongs to
.
Proof
As is d-magic, there is a d-magic labeling
of
. As
, there is a decomposition of the edge set of
into pairwise disjoint subsets
,
, …,
such that
induces a
-factor of
for each
. For
, let
be a copy of
and let
(
) be its edge (vertex) corresponding to
(
). Suppose that
.
For , denote by
the set
. Clearly,
induces a
-factor of
for each
. For any
set
Evidently, for any
there exists unique
such that
. Similarly, for any
there exists unique
such that
. Therefore,
,
, …
form a decomposition of
and each
induces a
-factor of
. Now consider a mapping
from
into positive integers given by
Clearly,
and for every vertex
, we have
Thus, by Theorem 2,
is a
-gradual d-magic graph. □
Theorem 6
Let and
be odd integers,
,
. If
,
, …,
are
-gradual d-magic graphs of the same size, then
.
Proof
First consider a mapping from
to integers defined by
It is easy to see that
, for each
, and
, for each
.
Let denote the size of
for each
. Since
, there is a
-gradual d-magic labeling
of
. Set
and define a mapping
from
into integers by
Since
,
As
,
Now it is easy to see that
is a bijection onto
and that
As
induces a
-factor of
, the set
induces a
-factor of
for each
. Moreover, for any vertex
we have
Since
,
,
, we obtain
Therefore,
is a
-gradual d-magic labeling of
. □
Corollary 2
Let and
be odd integers,
,
. For
, let
be a supermagic
-regular graph. Let
be a common multiple of integers
,
, …,
. If
is an odd integer for each
, then the graph
is
-gradual supermagic.
Proof
By Proposition 1, is a d-magic graph for each
. According to Theorem 5,
belongs to
. As
is odd,
is a
-gradual d-magic graph of size
and consequently
. Since
is a d-magic
-regular graph, it is supermagic. □
As any regular graph of even degree contains a -regular spanning subgraph, any
-regular graph belongs to
. Thus, we immediately have
Corollary 3
Let and
be odd integers,
,
. For
, let
be a supermagic
-regular graph. Let
be a common multiple of integers
,
, …,
. If
is an odd integer for each
, then the graph
is
-gradual supermagic.
Let be a graph and let
be a positive integer. Denote the lexicographic product of
and a totally disconnected graph of order
by
. Thus, the vertices of
are all ordered pairs
, where
is a vertex of
,
, and two vertices
,
are joined by an edge in
if and only if
,
are adjacent in
.
Theorem 7
Let be a graph of odd size. Then the graph
belongs to
for every odd integer
,
. Moreover, if
, then
.
Proof
For any edge , let
be a subgraph of
induced by
. Evidently,
is isomorphic to
. According to Corollary 1, it is
-gradual d-magic. Then the disjoint union
belongs to
because of Theorem 6. The graph
is decomposed into edge-disjoint subgraphs
for all
. Therefore, by Theorem 1 (multiple using (ii)),
.
Now suppose that . Then there is a decomposition of
into pairwise disjoint subsets
,
, …,
such that the subgraph
induced by
is a
-factor of
for each
. As
is a graph of odd size,
and
are odd integers. For each
, let
be the subgraph of
induced by
. Clearly,
is isomorphic to
. Since
,
is an
-gradual d-magic spanning subgraph of
. Moreover,
for every vertex
. Thus, according to Theorem 1 (statement (iii)),
is a
-gradual d-magic graph. □
For regular graphs we immediately obtain
Corollary 4
Let be a regular graph of odd size. Then the graph
is
-gradual supermagic for any odd integer
,
.
Corollary 5
Let ,
, and
be odd positive integers. For each
, let
and
be divisors of
such that
and
. Suppose that
,
, …,
are graphs satisfying one of the following conditions
• |
| ||||
• |
|
Then the graph is
-gradual supermagic.
Proof
For each , the graph
has
edges in both cases. Since
is odd,
and also
are odd integers. As
,
. According to Theorem 7,
belongs to
and it has
edges. Therefore, the graph
belongs to
by Theorem 6. Since
is a d-magic regular graph, it is supermagic. □
Corollary 6
Let be a regular complete multipartite graph of odd size. If
, then the following statements hold:
• | if | ||||
• | if |
Proof
Evidently, the size of is odd if and only if
is odd and either
or
.
Suppose that . If
, then
belongs to
by Theorem 3. Since
, the graph
(isomorphic to
) belongs to
, for every odd integer
, because of Theorem 7.
Suppose that . If
, then
belongs to
by Theorem 4. As
, the graph
(isomorphic to
) belongs to
, for every odd integer
, according to Theorem 7. □
Corollary 7
Let be an odd positive integer. For
, let
be an
-regular complete multipartite graph of odd size, where
. Let
be an odd common multiple of integers
,
, …,
, and let
for each
. Then
is a
-gradual supermagic graph, where
is equal to
when
is odd, and
otherwise.
Proof
As is odd, its divisors
are odd for all
. The complete multipartite graph
belongs to
by Corollary 6. According to Theorem 6, the graph
is
-gradual d-magic. As
has
edges for each
,
. Since
is a d-magic
-regular graph, it is supermagic. □
Acknowledgments
This work was supported by the Slovak VEGA Grant 1/0368/16 and by the Slovak Research and Development Agency under the contract No. APVV-15-0116.
References
- SedláčekJ., Problem 27, in theory of graphs and its applications Proc. Symp. Smolenice, Praha1963 163–164
- StewartB.M., Magic graphs Canad. J. Math. 181966 1031–1059
- DoobM., Characterizations of regular magic graphs J. Combin. Theory, Ser. B 251978 94–104
- JeurissenR.H., Disconnected graphs with magic labelings Discrete Math. 431983 47–53
- IvančoJ., On supermagic regular graphs Math. Bohem. 1252000 99–114
- IvančoJ., Supermagic generalized double graphs Discuss. Math. Graph Theory 362016 211–225
- KovářP., Unified approach to magic labelings of copies of regular graphs Congr. Numer. 1682004 197–205
- ShiuW.C.LamP.C.B.ChengH.L., Supermagic labeling of an s-duplicate of Kn,n Congr. Numer. 1462000 119–124
- GallianJ.A., A dynamic survey of graph labeling Electron. J. Combin.2017#DS6
- BezegováL’.IvančoJ., An extension of regular supermagic graphs Discrete Math. 3102010 3571–3578
- BezegováL’.IvančoJ., On conservative and supermagic graphs Discrete Math. 3112011 2428–2436
- BezegováL’.IvančoJ., A characterization of complete tripartite degree-magic graphs Discuss. Math. Graph Theory 322012 243–253
- BezegováL’.IvančoJ., Number of edges in degree-magic graphs Discrete Math. 3132013 1349–1357
- BezegováL’., Balanced degree-magic complements of bipartite graphs Discrete Math. 3132013 1918–1923
- WangT.LiD., A class of degree-magic join graphs Ars Combin. 1342017 43–50
- StewartB.M., Supermagic complete graphs Canad. J. Math. 191967 427–438