Gradual supermagic graphs

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.

Keywords:

• Gradual labeling
• Supermagic graphs
• Degree-magic graphs

1 Introduction

We consider finite undirected graphs without loops, multiple edges and isolated vertices. If $G$ is a graph, then $V\left(G\right)$ and $E\left(G\right)$ stand for the vertex set and edge set of $G$, respectively. Cardinalities of these sets are called the order and size of $G$. The union of two disjoint graphs $G$ and $H$ is denoted by $G\cup H$ and the union of $m$ disjoint copies of a graph $G$ is denoted by $mG$. For integers $p$, $q$ we denote by $[p,q]$ the set of all integers $z$ satisfying $p\le z\le q$.

Let a graph $G$ and a mapping $f$ from $E\left(G\right)$ into positive integers be given. The index-mapping of $f$ is the mapping $f^{\ast }$ from $V\left(G\right)$ into positive integers defined by $$f^{\ast }\left(v\right)=\sum _{uv\in E\left(G\right)}f\left(uv\right)\text{for every}v\in V\left(G\right)\text{.}$$An injective mapping $f$ from $E\left(G\right)$ into positive integers is called a magic labeling of $G$ for an index $\lambda$ if its index-mapping $f^{\ast }$ satisfies $$f^{\ast }\left(v\right)=\lambda \text{for all}v\in V\left(G\right)\text{.}$$A magic labeling $f$ of $G$ is called a supermagic labeling if the set $\{f\left(e\right):e\in E\left(G\right)\}$ consists of consecutive positive integers. We say that a graph $G$ is supermagic (magic) whenever there exists a supermagic (magic) labeling of $G$.

A bijective mapping $f$ from $E\left(G\right)$ to $\left[1,\left|E\left(G\right)\right|\right]$ is called a degree-magic labeling (or only d-magic labeling) of a graph $G$ if its index-mapping $f^{\ast }$ satisfies $$f^{\ast }\left(v\right)=\frac{1+\left|E\left(G\right)\right|}{2}deg\left(v\right)\text{for all}v\in V\left(G\right)\text{.}$$A d-magic labeling $f$ of $G$ is called balanced if for all $v\in V\left(G\right)$ it holds $$\left|\{uv\in E\left(G\right):f\left(uv\right)\le \lfloor |E\left(G\right)|∕2\rfloor \}\right|=\left|\{uv\in E\left(G\right):f\left(uv\right)>\lfloor |E\left(G\right)|∕2\rfloor \}\right|.$$ We say that a graph $G$ is degree-magic (balanced degree-magic) (or only d-magic) when there exists a d-magic (balanced d-magic) labeling of $G$.

The concept of magic graphs was introduced by Sedláček [1]. Supermagic graphs were introduced by M. B. Stewart [2]. There is by now a considerable number of papers published on magic and supermagic graphs; we single out [3–8] as being more particularly relevant to the present paper, and refer the reader to [9] for comprehensive references. The concept of degree-magic graphs was introduced in [10]. 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

[10] Let $G$ be a regular graph. Then $G$ 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 $H$ of a graph $G$ is called a proportional factor of $G$ whenever $\left|E\left(G\right)\right|{deg}_H\left(v\right)=\left|E\left(H\right)\right|{deg}_G\left(v\right)$ for every vertex $v\in V\left(G\right)$. For a positive integer $q$, $q\ge 2$, a proportional factor $H$ of a graph $G$ is called a $\frac{1}{q}$-factor of $G$ when $\left|E\left(H\right)\right|=\left|E\left(G\right)\right|∕q$ (i.e., ${deg}_H\left(v\right)={deg}_G\left(v\right)∕q$ for every vertex $v\in V\left(G\right)$). For conciseness, we will denote by $\mathcal{F}\left(q\right)$ the family of all graphs $G$ whose edge set can be decomposed into $q$ pairwise disjoint subsets each of which induces a $\frac{1}{q}$-factor of $G$. A bijection $f$ from $E\left(G\right)$ onto $\left[1,\left|E\left(G\right)\right|\right]$ is called $q$-gradual if the set $$F_q(f;i)≔\{e\in E\left(G\right):(i-1)\left|E\left(G\right)\right|∕q<f\left(e\right)\le i\left|E\left(G\right)\right|∕q\}$$induces a $\frac{1}{q}$-factor of $G$ for each $i\in [1,q]$. Evidently, $G$ admits a $q$-gradual bijection if and only if $G\in \mathcal{F}\left(q\right)$.

We say that a graph $G$ is $q$-gradual d-magic ($q$-gradual supermagic) when there exists a $q$-gradual d-magic (a $q$-gradual supermagic) labeling of $G$. The concept of gradual labelings was introduced in [6], where supermagic labelings of generalized double graphs were constructed using some gradual labelings.

The family of all $q$-gradual d-magic graphs we will denote by $\mathcal{G}\left(q\right)$. Clearly, $\mathcal{G}\left(2\right)$ is the family of all balanced d-magic graphs and $\mathcal{G}\left(q\right)\subset \mathcal{F}\left(q\right)$ for every $q\ge 2$. Moreover, we have

Theorem 1

The following statements hold:

(i)	Let $q$ be a divisor of a positive integer $k$ . Then $\mathcal{G}\left(k\right)\subset \mathcal{G}\left(q\right)$ .
(ii)	Let $G$ be a graph obtained from a graph $H$ by an identification of two vertices whose distance is at least three. If $H\in \mathcal{G}\left(q\right)$ , then $G\in \mathcal{G}\left(q\right)$ .
(iii)	Let $H_1$ ,…, $H_k$ be pairwise edge-disjoint proportional factors of a graph $G$ which form its decomposition. Let $H_j\in \mathcal{G}\left(q_j\right)$ for $j\in [1,k]$ . If there is an integer $m$ such that $\left|E\left(H_j\right)\right|∕q_j=m$ for each $j\in [1,k]$ , then $G\in \mathcal{G}\left(q\right)$ , where $q={\sum }_{j=1}^k{q}_j$ .

Proof

(i) As $q$ is a divisor of $k$, there is a positive integer $s$ such that $k=sq$. Let $G$ be a graph belonging to $\mathcal{G}\left(k\right)$. Then there is a $k$-gradual d-magic labeling $f$ of $G$. Therefore, $F_k(f;i)$ induces a $\frac{1}{k}$-factor of $G$ for each $i\in [1,k]$. Moreover, $F_q(f;j)={\cup }_{i=(j-1)s+1}^{js}{F}_k(f;i)$ for every $j\in [1,q]$. So $F_q(f;j)$ induces a subgraph of $G$ in which every vertex $v$ has degree $s\frac{1}{k}{deg}_G\left(v\right)=\frac{1}{q}{deg}_G\left(v\right)$. This means that $f$ is $q$-gradual. Thus, $G\in \mathcal{G}\left(q\right)$.

(ii) Let $f$ be a $q$-gradual d-magic labeling of $H$. Let $u$ and $v$ be two vertices of $H$ such that the distance between them is at least three. Let $G$ be a graph obtained from $H$ by an identification of vertices $u$ and $v$, and let $w$ denote the vertex of $G$ obtained by the identification. Thus, we can assume that $H$ and $G$ have the same edges. However, if an edge $e$ is incident with $u$ or $v$ in $H$ then $e$ is incident with $w$ in $G$. Now it is easy to see that the mapping $g$ from $E\left(G\right)$ into integers given by $g\left(e\right)≔f\left(e\right)$ is a desired $q$-gradual d-magic labeling of $G$.

(iii) As $\left|E\left(H_j\right)\right|=q_{j}m$ for each $j\in [1,k]$, $$\left|E\left(G\right)\right|=\sum _{j=1}^k\left|E\left(H_j\right)\right|=\sum _{j=1}^k{q}_{j}m=\left(\sum _{j=1}^k{q}_j\right)m=qm.$$Thus, ${deg}_{H_j}\left(v\right)=\left|E\left(H_j\right)\right|{deg}_G\left(v\right)∕\left|E\left(G\right)\right|=q_j{deg}_G\left(v\right)∕q$ for every vertex $v\in V\left(G\right)$. As $H_j$ belongs to $\mathcal{G}\left(q_j\right)$, there is a $q_j$-gradual d-magic labeling $f_j$ of $H_j$. For any vertex $v\in V\left(G\right)$ we have $$f_j^{\ast }\left(v\right)=\frac{1}{2}\left(1+\left|E\left(H_j\right)\right|\right){deg}_{H_j}\left(v\right)=\frac{1}{2}\left(1+q_{j}m\right)\frac{q_j}{q}{deg}_G\left(v\right).$$Moreover, the set $F_{q_j}(f_j;i)$ induces a $\frac{1}{q_j}$-factor of $H_j$ for each $i\in [1,q_j]$. This means that any vertex $v\in V\left(G\right)$ has degree ${deg}_{H_j}\left(v\right)∕q_j$ in the induced subgraph. However, ${deg}_{H_j}\left(v\right)∕q_j={deg}_G\left(v\right)∕q$ and so the set $F_{q_j}(f_j;i)$ induces a $\frac{1}{q}$-factor of $G$ for each $i\in [1,q_j]$.

Now consider the mapping $g$ from $E\left(G\right)$ into the set of positive integers given by $$g\left(e\right)=f_j\left(e\right)+\sum _{i=1}^{j-1}\left|E\left(H_i\right)\right|\text{when}e\in E\left(H_j\right)\text{.}$$Clearly, $g$ is a bijection from $E\left(G\right)$ onto $\left[1,\left|E\left(G\right)\right|\right]$. Moreover, for every vertex $w\in V\left(G\right)$ we have $$g^{\ast }\left(w\right)=\sum _{j=1}^k\left(f_j^{\ast }\left(w\right)+{deg}_{H_j}\left(w\right)\sum _{i=1}^{j-1}\left|E\left(H_i\right)\right|\right)=\sum _{j=1}^k\left(\frac{1}{2}(1+q_{j}m)\frac{q_j}{q}{deg}_G\left(w\right)+\frac{q_j}{q}{deg}_G\left(w\right)\sum _{i=1}^{j-1}{q}_{i}m\right)=\frac{1}{2}\sum _{j=1}^k\left(q_j+q_j^{2}m+2\sum _{i=1}^{j-1}{q}_i{q}_{j}m\right)\frac{1}{q}{deg}_G\left(w\right)=\frac{1}{2}\left(\sum _{j=1}^k{q}_j+\sum _{j=1}^k\left(q_j^2+2\sum _{i=1}^{j-1}{q}_i{q}_j\right)m\right)\frac{1}{q}{deg}_G\left(w\right)=\frac{1}{2}\left(\sum _{j=1}^k{q}_j+\left(\sum _{j=1}^k\sum _{i=1}^k{q}_i{q}_j\right)m\right)\frac{1}{q}{deg}_G\left(w\right)=\frac{1}{2}\left(\sum _{j=1}^k{q}_j+{\left(\sum _{j=1}^k{q}_j\right)}^{2}m\right)\frac{1}{q}{deg}_G\left(w\right)=\frac{1}{2}\left(q+q^{2}m\right)\frac{1}{q}{deg}_G\left(w\right)=\frac{1}{2}\left(1+qm\right){deg}_G\left(w\right)=\frac{1}{2}\left(1+\left|E\left(G\right)\right|\right){deg}_G\left(w\right).$$Therefore, $g$ is a degree-magic labeling of $G$.

For any $t\in [1,q]$ there is $j\in [1,k]$ such that ${\sum }_{i=1}^{j-1}{q}_i<t\le {\sum }_{i=1}^j{q}_i$. Then $r≔t-{\sum }_{i=1}^{j-1}{q}_i$ belongs to $[1,q_j]$ and $F_q(g;t)=F_{q_j}(f_j;r)$. Thus, $F_q(g;t)$ induces a $\frac{1}{q}$-factor of $G$ for each $t\in [1,q]$, i.e., $g$ is a $q$-gradual d-magic labeling of $G$. □

Theorem 2

A graph $G$ is $q$ -gradual d-magic if and only if there exist a mapping $\phi$ from $E\left(G\right)$ onto $[1,\left|E\left(G\right)\right|∕q]$ and a decomposition of $E\left(G\right)$ into pairwise disjoint subsets $X_1$ , $X_2$ , …, $X_q$ with the following properties

•	each $X_i$ induces a $\frac{1}{q}$ -factor of $G$ ,
•	$\phi \left(X_i\right)=[1,\left|E\left(G\right)\right|∕q]$ for each $i$ ,
•	${\phi }^{\ast }\left(v\right)=\frac{1+\left|E\left(G\right)\right|∕q}{2}deg\left(v\right)$ for all $v\in V\left(G\right)$ .

Proof

First suppose that $G$ is a $q$-gradual d-magic graph. Then there is a $q$-gradual d-magic labeling $f$ of $G$. For any $j\in [1,q]$, put $X_j=F_q(f;j)$ and define a mapping $\phi$ from $E\left(G\right)$ into the set of integers by $$\phi \left(e\right)=f\left(e\right)-(j-1)\left|E\left(G\right)\right|∕q\text{when}e\in X_j\text{.}$$As $f$ is a $q$-gradual labeling, each $X_j$ induces a $\frac{1}{q}$-factor of $G$ and consequently $\phi \left(X_j\right)=[1,\left|E\left(G\right)\right|∕q]$. Moreover, for any vertex $v\in V\left(G\right)$, we have $${\phi }^{\ast }\left(v\right)=f^{\ast }\left(v\right)-\sum _{j=1}^q(j-1)\left(\left|E\left(G\right)\right|∕q\right)\left(deg\left(v\right)∕q\right)=f^{\ast }\left(v\right)-(0+1+\cdots +q-1)\left|E\left(G\right)\right|deg\left(v\right)∕q^2=\frac{1+\left|E\left(G\right)\right|}{2}deg\left(v\right)-\frac{(q-1)\left|E\left(G\right)\right|}{2}deg\left(v\right)∕q=\frac{1+\left|E\left(G\right)\right|∕q}{2}{deg}_G\left(v\right).$$

On the other hand, assume that $\phi$ is a mapping from $E\left(G\right)$ onto the set $[1,\left|E\left(G\right)\right|∕q]$ and that $X_1$, $X_2$, …, $X_q$ is a decomposition of $E\left(G\right)$ into pairwise disjoint subsets with the considered properties. Define a mapping $f$ from $E\left(G\right)$ into the set of integers by $$f\left(e\right)=\phi \left(e\right)+(j-1)\left|E\left(G\right)\right|∕q\text{when}e\in X_j\text{.}$$It is easy to see that $f$ is a bijection onto $[1,\left|E\left(G\right)\right|]$. Similarly, for any vertex $v\in V\left(G\right)$, we have $$f^{\ast }\left(v\right)={\phi }^{\ast }\left(v\right)+\sum _{j=1}^q(j-1)\left(\left|E\left(G\right)\right|∕q\right)\left(deg\left(v\right)∕q\right)={\phi }^{\ast }\left(v\right)+(0+1+\cdots +q-1)\left|E\left(G\right)\right|deg\left(v\right)∕q^2=\frac{1+\left|E\left(G\right)\right|∕q}{2}deg\left(v\right)+\frac{(q-1)\left|E\left(G\right)\right|}{2}deg\left(v\right)∕q=\frac{1+\left|E\left(G\right)\right|}{2}{deg}_G\left(v\right).$$Therefore, $f$ is a d-magic labeling of $G$. Moreover, the set $F_q(f;j)=X_j$ induces a $\frac{1}{q}$-factor of $G$, i.e., $f$ is $q$-gradual. □

3 Complete graphs

A complete $k$ -partite graph is a graph whose vertices can be partitioned into $k$ ($k\ge 2$) disjoint classes $V_1,\dots ,V_k$ such that two vertices are adjacent whenever they belong to distinct classes. If $\left|V_i\right|=n$, for each $i\in [1,k]$, then the complete $k$-partite graph is denoted by $K_{k\left[n\right]}$. The complete graph $K_{k\left[1\right]}$ is usually denoted by $K_k$ and the complete bipartite graph $K_{2\left[n\right]}$ is mostly denoted by $K_{n,n}$.

For any graph $G$ we define a graph $G^{\bowtie }$ by $V\left(G^{\bowtie }\right)={\bigcup }_{v\in V\left(G\right)}\{v^0,v^1\}$ and $E\left(G^{\bowtie }\right)={\bigcup }_{vu\in E\left(G\right)}\{v^0{u}^1,v^1{u}^0\}\cup {\bigcup }_{v\in V\left(G\right)}\left\{v^0{v}^1\right\}$. It is easy to see that $G^{\bowtie }$ is a generalized double graph denoted by $D(G;0̸,V\left(G\right))$ in [6]. Therein there was also proved the following result.

Proposition 2

[6] Let $G$ be a $2r$ -regular Hamiltonian graph of odd order. Then $G^{\bowtie }$ is a $(2r+1)$ -gradual supermagic graph.

As $K_n^{\bowtie }$ is isomorphic to $K_{n,n}$, we immediately have

Corollary 1

The complete bipartite graph $K_{n,n}$ is $n$ -gradual supermagic for every odd integer $n\ge 3$ .

The complete bipartite graph $K_{n,n}$ is balanced d-magic (i.e., 2-gradual supermagic) for every even integer $n\ge 4$ (see [10]). Similarly, the complete graph $K_{4n+1}$ is 2-gradual supermagic for every integer $n\ge 2$ (see [11]) and $K_{4n}$ is not supermagic for every integer $n\ge 1$ (see [16]). Using Theorem 2, we obtain similar results for other complete graphs.

Theorem 3

The complete graph $K_{2n}$ is $(2n-1)$ -gradual supermagic for every odd integer $n\ge 3$ .

Proof

Denote the vertices of $K_{2n}$ by $w$, $v_0$, $v_1$, …, $v_{2n-2}$ and for every $k\in [0,2n-2]$ define the set of edges $X_k=\left\{w{v}_k\right\}\cup \{v_{k-i}{v}_{k+i}:i\in [1,n-1]\}$, the indices being taken modulo $2n-1$. It is easy to see that $X_0$, $X_1$, …$X_{2n-2}$ form a decomposition of $E\left(K_{2n}\right)$ and each $X_k$ is a perfect matching (i.e., induces a $\frac{1}{2n-1}$-factor) of $K_{2n}$. Now consider a mapping $\phi$ from $E\left(K_{2n}\right)$ into the set of positive integers given by $$\phi \left(e\right)=\left\{\begin{array}{cc}i\hfill & \text{if}e=v_{k-i}{v}_{k+i}\text{, for}k\in [0,2n-2]\text{,}1\le i\le \frac{n-1}{2}\text{,}\hfill \\ \frac{n+1}{2}\hfill & \text{if}e=w{v}_k\text{, for}k\in [0,2n-2]\text{,}\hfill \\ 1+i\hfill & \text{if}e=v_{k-i}{v}_{k+i}\text{, for}k\in [0,2n-2]\text{,}\frac{n+1}{2}\le i\le n-1\text{.}\hfill \end{array}\right.$$Evidently, $\phi \left(X_k\right)=[1,n]$. Each vertex $v_j$, $j\in [0,2n-2]$, is incident with two edges of type $v_{k-i}{v}_{k+i}$ ($v_{j-2i}{v}_j$, $v_j{v}_{j+2i}$) for each $i\in [1,n-1]$ and with one edge of type $w{v}_k$ ($w{v}_j$). Thus, we have $${\phi }^{\ast }\left(v_j\right)=2\sum _{i=1}^{n}i-\frac{n+1}{2}=\frac{1}{2}(1+n)(2n-1)$$Any edge incident with $w$ is of type $w{v}_k$, so ${\phi }^{\ast }\left(w\right)=\frac{1}{2}(1+n)(2n-1)$. Therefore, by Theorem 2, $K_{2n}$ is a $(2n-1)$-gradual supermagic graph. □

Theorem 4

The complete graph $K_{4n+3}$ is $(2n+1)$ -gradual supermagic for every positive integer $n$ .

Proof

Denote the vertices of $K_{4n+3}$ by $w$, $v_0$, $v_1$, …, $v_{2n}$, $u_0$, $u_1$, …, $u_{2n}$ and for every $k\in [0,2n\}$ define the set of edges $$X_k=\{v_k{u}_k,w{u}_k,w{v}_k\}\cup \bigcup _{i=1}^n\{v_{k-i}{v}_{k+i},u_{k-i}{v}_{k+i},u_{k-i}{u}_{k+i},v_{k-i}{u}_{k+i}\},$$the indices being taken modulo $2n+1$. It is not difficult to see that the sets $X_0$, $X_1$, …$X_{2n}$ form a decomposition of $E\left(K_{4n+3}\right)$ and each $X_k$ induces a 2-regular spanning subgraph (i.e., a $\frac{1}{2n+1}$-factor) of $K_{4n+3}$ isomorphic to $K_3\cup n{K}_{2,2}$. Now consider a mapping $\phi$ from $E\left(K_{4n+3}\right)$ into positive integers given by $$\phi \left(e\right)=\left\{\begin{array}{cc}1\hfill & \text{if}e=v_k{u}_k\text{, for}k\in [0,2n]\text{,}\hfill \\ 2\hfill & \text{if}e=w{u}_k\text{, for}k\in [0,2n]\text{,}\hfill \\ 4n+2\hfill & \text{if}e=w{v}_k\text{, for}k\in [0,2n]\text{,}\hfill \\ 3i\hfill & \text{if}e=v_{k-i}{v}_{k+i}\text{, for}k\in [0,2n]\text{,}i\in [1,n]\text{,}\hfill \\ 3i+1\hfill & \text{if}e=u_{k-i}{v}_{k+i}\text{, for}k\in [0,2n]\text{,}i\in [1,n]\text{,}\hfill \\ 3i+2\hfill & \text{if}e=u_{k-i}{u}_{k+i}\text{, for}k\in [0,2n]\text{,}i\in [1,n]\text{,}\hfill \\ 3n+2+i\hfill & \text{if}e=v_{k-i}{u}_{k+i}\text{, for}k\in [0,2n]\text{,}i\in [1,n-1]\text{,}\hfill \\ 4n+3\hfill & \text{if}e=v_{k-n}{u}_{k+n}\text{, for}k\in [0,2n]\text{.}\hfill \end{array}\right.$$Evidently, $\phi \left(X_k\right)=[1,4n+3]$. Each vertex $v_j$, $j\in [0,2n]$, is incident with two edges of type $v_{k-i}{v}_{k+i}$ ($v_{j-2i}{v}_j$, $v_j{v}_{j+2i}$) for each $i\in [1,n]$, with one edge of type $u_{k-i}{v}_{k+i}$ ($u_{j-2i}{v}_j$) for each $i\in [1,n]$, with one edge of type $v_{k-i}{u}_{k+i}$ ($v_j{u}_{j+2i}$) for each $i\in [1,n]$, with one edge of type $v_k{u}_k$ ($v_j{u}_j$), and with one edge of type $w{v}_k$ ($w{v}_j$). Thus, we have $${\phi }^{\ast }\left(v_j\right)=1+(4n+2)+\sum _{i=1}^n\left(2\cdot 3i+(3i+1)\right)+\sum _{i=1}^{n-1}(3n+2+i)+(4n+3)=8n^2+12n+4=\left(1+(4n+3)\right)(4n+2)∕2.$$Similarly, for every vertex $u_j$, $j\in [0,2n]$, we have $${\phi }^{\ast }\left(u_j\right)=1+2+\sum _{i=1}^n\left((3i+1)+2\cdot (3i+2)\right)+\sum _{i=1}^{n-1}(3n+2+i)+(4n+3)=8n^2+12n+4=\left(1+(4n+3)\right)(4n+2)∕2$$The vertex $w$ is incident with $(2n+1)$ edges of type $w{u}_k$ and with $(2n+1)$ edges of type $w{v}_k$. Thus $${\phi }^{\ast }\left(w\right)=\left(2+(4n+2)\right)(2n+1)=\left(1+(4n+3)\right)(4n+2)∕2.$$Therefore, by Theorem 2, $K_{4n+3}$ is a $(2n+1)$-gradual supermagic graph. □

4 Union of graphs

M. Doob [3] proved that a regular graph of degree $d\ge 3$ with connected components $G_1$, …, $G_n$ is magic if and only if $G_i$ is magic for each $i$. A similar characterization of all disconnected magic graphs was given by R.H. Jeurissen [4]. For supermagic graphs the following holds:

Proposition 3

[5] Let $G$ be a $kr$ -regular supermagic graph which can be decomposed into $k$ pairwise edge-disjoint $r$ -regular spanning subgraphs. Then the following statements hold:

•	if $k$ is even, then $mG$ is supermagic for every positive integer $m$ ,
•	if $k$ is odd, then $mG$ is supermagic for every odd positive integer $m$ .

A similar result for $k$-regular supermagic $k$-edge-colorable graphs (they admit a decomposition into $k$ $1$-regular spanning subgraphs) was presented in [7]. For degree-magic graphs we have

Proposition 4

[10] Let $H_1$ and $H_2$ be edge-disjoint subgraphs of a graph $G$ which form its decomposition. If $H_1$ is d-magic and $H_2$ is balanced d-magic then $G$ is a d-magic graph. Moreover, if $H_1$ and $H_2$ are both balanced d-magic then $G$ is a balanced d-magic graph.

Evidently, if $G$ is an $r$-regular balanced d-magic (and so supermagic) graph and $H$ is an $r$-regular supermagic graph then $G\cup H$ 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 $q$-gradual d-magic graphs which is usable for graphs of odd size. For the family $\mathcal{G}\left(q\right)$ we have

Theorem 5

Let $G\in \mathcal{F}\left(q\right)$ , $q\ge 2$ , be a d-magic graph. Then the graph $qG$ belongs to $\mathcal{G}\left(q\right)$ .

Proof

As $G$ is d-magic, there is a d-magic labeling $f$ of $G$. As $G\in \mathcal{F}\left(q\right)$, there is a decomposition of the edge set of $G$ into pairwise disjoint subsets $Y^1$, $Y^2$, …, $Y^q$ such that $Y^i$ induces a $\frac{1}{q}$-factor of $G$ for each $i\in [1,q]$. For $j\in [1,q]$, let $G_j$ be a copy of $G$ and let $e_j$ ($v_j$) be its edge (vertex) corresponding to $e\in E\left(G\right)$ ($v\in V\left(G\right)$). Suppose that $qG=G_1\cup G_2\cup \cdots \cup G_q$.

For $i,j\in [1,q]$, denote by $Y_j^i$ the set $\{e_j\in E\left(G_j\right):e\in Y^i\}$. Clearly, $Y_j^i$ induces a $\frac{1}{q}$-factor of $G_j$ for each $i\in [1,q]$. For any $k\in [1,q]$ set $$X_k=\{e_j\in E\left(qG\right):e\in Y^i\text{when}i+j\equiv k(modq)\}.$$Evidently, for any $j\in [1,q]$ there exists unique $i\in [1,q]$ such that $X_k\cap E\left(G_j\right)=Y_j^i$. Similarly, for any $e\in E\left(G\right)$ there exists unique $j\in [1,q]$ such that $e_j\in X_k$. Therefore, $X_1$, $X_2$, …$X_q$ form a decomposition of $E\left(qG\right)$ and each $X_k$ induces a $\frac{1}{q}$-factor of $qG$. Now consider a mapping $\phi$ from $E\left(qG\right)$ into positive integers given by $$\phi \left(e_j\right)=f\left(e\right)$$Clearly, $\phi \left(X_k\right)=[1,\left|E\left(G\right)\right|]$ and for every vertex $v_j$, we have $${\phi }^{\ast }\left(v_j\right)=f^{\ast }\left(v\right)=\frac{1+\left|E\left(G\right)\right|}{2}{deg}_G\left(v\right)=\frac{1+\left|E\left(qG\right)\right|∕q}{2}{deg}_{qG}\left(v_j\right).$$Thus, by Theorem 2, $qG$ is a $q$-gradual d-magic graph. □

Theorem 6

Let $m$ and $q$ be odd integers, $m\ge 3$ , $q\ge 3$ . If $G_1$ , $G_2$ , …, $G_m$ are $q$ -gradual d-magic graphs of the same size, then $G_1\cup G_2\cup \cdots \cup G_m\in \mathcal{G}\left(q\right)$ .

Proof

First consider a mapping $r$ from $[1,m]\times [1,q]$ to integers defined by $$r(i,j)=\left\{\begin{array}{cc}i-1\hfill & \text{for}j\equiv 1(mod2)\text{and}j<q\text{,}\hfill \\ m-i\hfill & \text{for}j\equiv 0(mod2)\text{and}j<q-1\text{,}\hfill \\ i+(m-3)∕2\hfill & \text{for}j=q-1\text{and}i\le (m+1)∕2\text{,}\hfill \\ i-(m+3)∕2\hfill & \text{for}j=q-1\text{and}i>(m+1)∕2\text{,}\hfill \\ m-2i+1\hfill & \text{for}j=q\text{and}i\le (m+1)∕2\text{,}\hfill \\ 2m-2i+1\hfill & \text{for}j=q\text{and}i>(m+1)∕2\text{.}\hfill \end{array}\right.$$It is easy to see that $\{r(1,j),r(2,j),\dots ,r(m,j)\}=[0,m-1]$, for each $j\in [1,q]$, and $r(i,1)+r(i,2)+\cdots +r(i,q)=q(m-1)∕2$, for each $i\in [1,m]$.

Let $\epsilon$ denote the size of $G_i$ for each $i\in [1,m]$. Since $G_i\in \mathcal{G}\left(q\right)$, there is a $q$-gradual d-magic labeling $f_i$ of $G_i$. Set $H=G_1\cup G_2\cup \cdots \cup G_m$ and define a mapping $h$ from $E\left(H\right)$ into integers by $$h\left(e\right)=f_i\left(e\right)+\left(r(i,j)+(j-1)(m-1)\right)\epsilon ∕q\text{when}e\in F_q(f_i;j)\text{.}$$Since $f_i\left(F_q(f_i;j)\right)=\left[1+(j-1)\epsilon ∕q,\epsilon ∕q+(j-1)\epsilon ∕q\right]$, $$h\left(F_q(f_i;j)\right)=\left[1+\left((j-1)m+r(i,j)\right)\epsilon ∕q,\epsilon ∕q+\left((j-1)m+r(i,j)\right)\epsilon ∕q\right].$$As ${\cup }_{i=1}^{m}r(i,j)=[0,m-1]$, $$h\left({\cup }_{i=1}^m{F}_q(f_i;j)\right)=\left[1+\left((j-1)m+0\right)\epsilon ∕q,\epsilon ∕q+\left((j-1)m+0\right)\epsilon ∕q\right]$$$$\cup \left[1+\left((j-1)m+1\right)\epsilon ∕q,\epsilon ∕q+\left((j-1)m+1\right)\epsilon ∕q\right]$$$$\dots$$$$\cup \left[1+\left((j-1)m+m-1\right)\epsilon ∕q,\epsilon ∕q+\left((j-1)m+m-1\right)\epsilon ∕q\right]$$$$=\left[1+(j-1)m\epsilon ∕q,m\epsilon ∕q+(j-1)m\epsilon ∕q\right].$$Now it is easy to see that $h$ is a bijection onto $[1,\left|E\left(H\right)\right|]$ and that $${\cup }_{i=1}^m{F}_q(f_i;j)=F_q(h;j).$$As $F_q(f_i;j)$ induces a $\frac{1}{q}$-factor of $G_i$, the set $F_q(h;j)$ induces a $\frac{1}{q}$-factor of $H$ for each $j\in [1,q]$. Moreover, for any vertex $v\in V\left(G_i\right)$ we have $$h^{\ast }\left(v\right)=\sum _{uv\in E\left(H\right)}h\left(uv\right)=\sum _{uv\in E\left(G_i\right)}h\left(uv\right)=\sum _{j=1}^q\sum _{uv\in F_q(f_i;j)}h\left(uv\right)=\sum _{j=1}^q\sum _{uv\in F_q(f_i;j)}\left(f_i\left(uv\right)+\left(r(i,j)+(j-1)(m-1)\right)\epsilon ∕q\right)=f_i^{\ast }\left(v\right)+\sum _{j=1}^q\left(\left(r(i,j)+(j-1)(m-1)\right)\epsilon ∕q\right){deg}_{G_i}\left(v\right)∕q=f_i^{\ast }\left(v\right)+\left(\sum _{j=1}^{q}r(i,j)+\sum _{j=1}^q(j-1)(m-1)\right)\epsilon {deg}_{G_i}\left(v\right)∕q^2=f_i^{\ast }\left(v\right)+\left(q(m-1)∕2+q(q-1)(m-1)∕2\right)\epsilon {deg}_{G_i}\left(v\right)∕q^2=f_i^{\ast }\left(v\right)+(m-1)\epsilon {deg}_{G_i}\left(v\right)∕2.$$ Since $f_i^{\ast }\left(v\right)=(1+\epsilon ){deg}_{G_i}\left(v\right)∕2$, ${deg}_{G_i}\left(v\right)={deg}_H\left(v\right)$, $\left|E\left(H\right)\right|=m\epsilon$, we obtain $$h^{\ast }\left(v\right)=(1+m\epsilon ){deg}_{G_i}\left(v\right)∕2=\frac{1+\left|E\left(H\right)\right|}{2}{deg}_H\left(v\right).$$Therefore, $h$ is a $q$-gradual d-magic labeling of $H$. □

Corollary 2

Let $m$ and $q$ be odd integers, $m\ge 3$ , $q\ge 3$ . For $i\in [1,m]$ , let $G_i\in \mathcal{F}\left(q\right)$ be a supermagic $r$ -regular graph. Let $\epsilon$ be a common multiple of integers $\left|E\left(G_1\right)\right|$ , $\left|E\left(G_2\right)\right|$ , …, $\left|E\left(G_m\right)\right|$ . If ${\epsilon }_i≔\epsilon ∕\left|E\left(G_i\right)\right|$ is an odd integer for each $i\in [1,m]$ , then the graph ${\epsilon }_{1}q{G}_1\cup {\epsilon }_{2}q{G}_2\cup \cdots \cup {\epsilon }_{m}q{G}_m$ is $q$ -gradual supermagic.

Proof

By Proposition 1, $G_i$ is a d-magic graph for each $i\in [1,m]$. According to Theorem 5, $q{G}_i$ belongs to $\mathcal{G}\left(q\right)$. As ${\epsilon }_i$ is odd, ${\epsilon }_{i}q{G}_i$ is a $q$-gradual d-magic graph of size $\epsilon q$ and consequently $G={\epsilon }_{1}q{G}_1\cup {\epsilon }_{2}q{G}_2\cup \cdots \cup {\epsilon }_{m}q{G}_m\in \mathcal{G}\left(q\right)$. Since $G$ is a d-magic $r$-regular graph, it is supermagic. □

As any regular graph of even degree contains a $2$-regular spanning subgraph, any $2r$-regular graph belongs to $\mathcal{F}\left(r\right)$. Thus, we immediately have

Corollary 3

Let $m$ and $q$ be odd integers, $m\ge 3$ , $q\ge 3$ . For $i\in [1,m]$ , let $G_i$ be a supermagic $2r$ -regular graph. Let $\epsilon$ be a common multiple of integers $\left|E\left(G_1\right)\right|$ , $\left|E\left(G_2\right)\right|$ , …, $\left|E\left(G_m\right)\right|$ . If ${\epsilon }_i≔\epsilon ∕\left|E\left(G_i\right)\right|$ is an odd integer for each $i\in [1,m]$ , then the graph ${\epsilon }_{1}q{G}_1\cup {\epsilon }_{2}q{G}_2\cup \cdots \cup {\epsilon }_{m}q{G}_m$ is $q$ -gradual supermagic.

Let $G$ be a graph and let $n$ be a positive integer. Denote the lexicographic product of $G$ and a totally disconnected graph of order $n$ by $G^{\left(n\right)}$. Thus, the vertices of $G^{\left(n\right)}$ are all ordered pairs $(v,i)$, where $v$ is a vertex of $G$, $1\le i\le n$, and two vertices $(u,i)$, $(v,j)$ are joined by an edge in $G^{\left(n\right)}$ if and only if $u$, $v$ are adjacent in $G$.

Theorem 7

Let $G$ be a graph of odd size. Then the graph $G^{\left(n\right)}$ belongs to $\mathcal{G}\left(n\right)$ for every odd integer $n$ , $n\ge 3$ . Moreover, if $G\in \mathcal{F}\left(q\right)$ , then $G^{\left(n\right)}\in \mathcal{G}\left(qn\right)$ .

Proof

For any edge $e=uv\in E\left(G\right)$, let $G_e^{\left(n\right)}$ be a subgraph of $G^{\left(n\right)}$ induced by $\{(u,i):1\le i\le n\}\cup \{(v,j):1\le j\le n\}$. Evidently, $G_e^{\left(n\right)}$ is isomorphic to $K_{n,n}$. According to Corollary 1, it is $n$-gradual d-magic. Then the disjoint union ${\cup }_{e\in E\left(G\right)}{G}_e^{\left(n\right)}$ belongs to $\mathcal{G}\left(n\right)$ because of Theorem 6. The graph $G^{\left(n\right)}$ is decomposed into edge-disjoint subgraphs $G_e^{\left(n\right)}$ for all $e\in E\left(G\right)$. Therefore, by Theorem 1 (multiple using (ii)), $G^{\left(n\right)}\in \mathcal{G}\left(n\right)$.

Now suppose that $G\in \mathcal{F}\left(q\right)$. Then there is a decomposition of $E\left(G\right)$ into pairwise disjoint subsets $X_1$, $X_2$, …, $X_q$ such that the subgraph $S_i$ induced by $X_i$ is a $\frac{1}{q}$-factor of $G$ for each $i\in [1,q]$. As $G$ is a graph of odd size, $q$ and $\left|X_i\right|=\left|E\left(G\right)\right|∕q$ are odd integers. For each $i\in [1,q]$, let $H_i$ be the subgraph of $G^{\left(n\right)}$ induced by ${\cup }_{e\in X_i}E\left(G_e^{\left(n\right)}\right)$. Clearly, $H_i$ is isomorphic to $S_i^{\left(n\right)}$. Since $S_i^{\left(n\right)}\in \mathcal{G}\left(n\right)$, $H_i$ is an $n$-gradual d-magic spanning subgraph of $G^{\left(n\right)}$. Moreover, ${deg}_{H_i}\left(v\right)=\frac{1}{q}{deg}_{G^{\left(n\right)}}\left(v\right)=\frac{n}{nq}{deg}_{G^{\left(n\right)}}\left(v\right)$ for every vertex $v\in V\left(G^{\left(n\right)}\right)$. Thus, according to Theorem 1 (statement (iii)), $G^{\left(n\right)}$ is a $qn$-gradual d-magic graph. □

For regular graphs we immediately obtain

Corollary 4

Let $G$ be a regular graph of odd size. Then the graph $G^{\left(n\right)}$ is $n$ -gradual supermagic for any odd integer $n$ , $n\ge 3$ .

Corollary 5

Let $r$ , $\nu$ , and $m$ be odd positive integers. For each $i\in [1,m]$ , let $r_i$ and $n_i$ be divisors of $r$ such that $r_i\cdot n_i=r$ and $n_i>1$ . Suppose that $G_1$ , $G_2$ , …, $G_m$ are graphs satisfying one of the following conditions

•	$G_i\in \mathcal{F}\left(r_i\right)$ is an $r_i$ -regular graph of order $2\nu r_i$ for all $i$ ,
•	$G_i$ is a $2r_i$ -regular graph of order $\nu r_i$ for all $i$ .

Then the graph $G_1^{\left(n_1\right)}\cup G_2^{\left(n_2\right)}\cup \cdots \cup G_m^{\left(n_m\right)}$ is $r$ -gradual supermagic.

Proof

For each $i\in [1,m]$, the graph $G_i\in \mathcal{F}\left(r_i\right)$ has $\nu r_i^2$ edges in both cases. Since $r$ is odd, $r_i$ and also $n_i$ are odd integers. As $n_i>1$, $n_i\ge 3$. According to Theorem 7, $G_i^{\left(n_i\right)}$ belongs to $\mathcal{G}\left(r\right)$ and it has $\nu r^2$ edges. Therefore, the graph $H={\cup }_{i=1}^m{G}_i^{\left(n_i\right)}$ belongs to $\mathcal{G}\left(r\right)$ by Theorem 6. Since $H$ is a d-magic regular graph, it is supermagic. □

Corollary 6

Let $K_{k\left[n\right]}$ be a regular complete multipartite graph of odd size. If $kn\ge 6$ , then the following statements hold:

•	if $k$ is even, then $K_{k\left[n\right]}\in \mathcal{G}\left((k-1)n\right)$ ,
•	if $k$ is odd, then $K_{k\left[n\right]}\in \mathcal{G}((k-1)n∕2)$ .

Proof

Evidently, the size of $K_{k\left[n\right]}$ is odd if and only if $n$ is odd and either $k\equiv 2(mod4)$ or $k\equiv 3(mod4)$.

Suppose that $k\equiv 2(mod4)$. If $n=1$, then $K_k$ belongs to $\mathcal{G}(k-1)$ by Theorem 3. Since $K_k\in \mathcal{G}(k-1)\subset \mathcal{F}(k-1)$, the graph $K_{k\left[n\right]}$ (isomorphic to $K_k^{\left(n\right)}$) belongs to $\mathcal{G}\left((k-1)n\right)$, for every odd integer $n\ge 3$, because of Theorem 7.

Suppose that $k\equiv 3(mod4)$. If $n=1$, then $K_k$ belongs to $\mathcal{G}((k-1)∕2)$ by Theorem 4. As $K_k\in \mathcal{G}((k-1)∕2)\subset \mathcal{F}((k-1)∕2)$, the graph $K_{k\left[n\right]}$ (isomorphic to $K_k^{\left(n\right)}$) belongs to $\mathcal{G}((k-1)n∕2)$, for every odd integer $n\ge 3$, according to Theorem 7. □

Corollary 7

Let $m$ be an odd positive integer. For $i\in [1,m]$ , let $G_i$ be an $r$ -regular complete multipartite graph of odd size, where $r\ge 3$ . Let $\epsilon$ be an odd common multiple of integers $\left|E\left(G_1\right)\right|$ , $\left|E\left(G_2\right)\right|$ , …, $\left|E\left(G_m\right)\right|$ , and let ${\epsilon }_i≔\epsilon ∕\left|E\left(G_i\right)\right|$ for each $i\in [1,m]$ . Then ${\epsilon }_1{G}_1\cup {\epsilon }_2{G}_2\cup \cdots \cup {\epsilon }_m{G}_m$ is a $q$ -gradual supermagic graph, where $q$ is equal to $r$ when $r$ is odd, and $r∕2$ otherwise.

Proof

As $\epsilon$ is odd, its divisors ${\epsilon }_i$ are odd for all $i\in [1,m]$. The complete multipartite graph $G_i$ belongs to $\mathcal{G}\left(q\right)$ by Corollary 6. According to Theorem 6, the graph ${\epsilon }_i{G}_i$ is $q$-gradual d-magic. As ${\epsilon }_i{G}_i$ has $\epsilon$ edges for each $i\in [1,m]$, $G={\epsilon }_1{G}_1\cup {\epsilon }_2{G}_2\cup \cdots \cup {\epsilon }_m{G}_m\in \mathcal{G}\left(q\right)$. Since $G$ is a d-magic $r$-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.