D-Magic Oriented Graphs

Abstract

In this paper, we define D-magic labelings for oriented graphs where D is a distance set. In particular, we label the vertices of the graph with distinct integers $\{1,2,\dots ,|V\left(G\right)\left|\right\}$ in such a way that the sum of all the vertex labels that are a distance in D away from a given vertex is the same across all vertices. We give some results related to the magic constant, construct a few infinite families of D-magic graphs, and examine trees, cycles, and multipartite graphs. This definition grew out of the definition of D-magic (undirected) graphs. This paper explores some of the symmetries we see between the undirected and directed version of D-magic labelings.

1. Introduction

A labeling of a graph or digraph is simply defined as an assignment of numbers (usually integers) to the vertices, edges, or both, such that certain conditions hold. There are many different types of labelings as can be seen in Gallian’s survey [1]. However, most of these labelings are defined on undirected graphs. In 1985, Bloom and Hsu introduced graceful labelings on directed graphs [2]. In 2008, magic labelings of directed graphs were introduced in [3]. Other magic-type labelings on directed graphs have been studied in [4,5,6,7,8,9].

In Vilfred’s 1994 Ph.D. thesis, distance magic labelings were introduced [10]. A distance magic labeling, or Σ labeling, of a graph G on n vertices is a bijection $f:V\left(G\right)\to \{1,2,\dots ,n\}$ such that at any vertex x, the weight of x, ${\sum }_{y\in N\left(x\right)}f\left(y\right)$ is constant, where $N\left(x\right)$ is the open neighbourhood of x, i.e., the set of vertices adjacent to x. Five years later, Jinah [11] defined a variation of the distance magic labeling, called the closed distance magic labeling, where the weight of a vertex x is summed over the closed neighbourhood of x, i.e., the set containing x and all vertices adjacent to x. D-magic labelings were first introduced by O’Neal and Slater as a generalization of these two previously mentioned labelings [12].

Definition 1.

Let G be a graph with n vertices and diameter $diam\left(G\right)$. Let $D\subseteq \{0,1,\dots ,diam(G\left)\right\}$ be a set of distances in G. G is said to be D-magic if there exists a bijection $f:V\to \{1,2,\dots ,n\}$ and a magic constant k such that for any vertex x, ${\sum }_{y\in N_D\left(x\right)}f\left(y\right)=k$, where $N_D\left(x\right)=\left\{y\right|d(x,y)=d,d\in D\}$ is the D-neighbourhood set of x.

One of the most important results for D-magic labelings is in [13,14] where it is shown that for a particular graph, the magic constant is unique and is determined by its fractional domination number. For more results, refer to survey articles [15,16].

In this paper, we explore the directed version of D-magic labelings.

2. Definitions and Notation

2.1. Oriented Graphs

An oriented graph G can be described as a collection $V=V\left(G\right)$ of vertices together with a collection $E=E\left(G\right)$ of ordered pairs of vertices called directed edges. If there is an edge $(x,y)$, we may write $x\to y$. By definition, oriented graphs do not contain any repeated directed edges, contain no loops (i.e., edges of the form $(x,x)$) and they do not contain bidirectional edges, i.e., if $(x,y)\in E$, then $(y,x)\notin E$. The underlying graph of an oriented graph G is the graph that is obtained by removing the orientations of the directed edges in G. We shall write $n=\left|V\right(G\left)\right|$ and $m=\left|E\right(G\left)\right|$.

2.2. Partitions

The ability to partition the integers into sets with equal sums is a critical component of creating magic-type labelings of graphs. Hence, we include a definition and useful result related to integer partitions here.

Definition 2

([17]). An $(s-t)$-partition of $Z_n=\{1,2,\dots ,n\}$ is a partition of $Z_n$ into s subsets, each with sum t.

Theorem 1

([17]). If $n(n+1)=2st$, $t\ge n$, then there exists an $(s-t)$-partition of $Z_n$.

2.3. D-Magic Oriented Graphs

Motivated by the previously mentioned definitions, we now introduce a definition for D-magic oriented graphs.

Definition 3.

Let G be an oriented graph with n vertices and diameter $diam\left(G\right)$. Let $D\subseteq \{0,1,\dots ,diam(G\left)\right\}$ be a set of distances in G. An oriented graph G has a D-magic labeling if there is a bijection $f:V\left(G\right)\to \{1,2,\dots ,n\}$ and a magic constant k such that at any vertex $x\in V\left(G\right)$

$$w\left(x\right)=\sum _{y\in N_D\left(x\right)}f\left(y\right)=k,$$

where

$$N_D\left(x\right)=\left\{y\right|d(x,y)\in D\}.$$

If G admits a D-magic labeling, then G is D-magic. The sum, $w\left(x\right)$, at each vertex is the weight.

The smallest example of a D-magic oriented graph is $K_1$, which is $\left\{0\right\}$-magic. This is the only oriented graph that is $\left\{0\right\}$-magic as any graph with two or more vertices would produce distinct weights at each vertex. As we will see in Section 4, there are no D-magic oriented graphs of order 2. For graphs of order 3, there is a $\{0,1,2\}$-magic labeling of $\overrightarrow{C_3}$. The smallest non-trivial example is $\overrightarrow{C_4}$, which is $\{0,2\},\{1,3\}$, and $\{0,1,2,3\}$-magic.

3. Properties of $\mathit{D}$-Magic Oriented Graphs

In this section, we prove some general properties of D-magic oriented graphs. We start with an observation that is a direct consequence of Definition 3.

Remark 1.

Let $D_1$ and $D_2$ be two disjoint sets of distances. If a labeling is both $D_1$-magic and $D_2$-magic then it is also $(D_1\cup D_2)$-magic.

In the next lemma we show that a D-magic oriented graph consists of at most one sink, i.e., a vertex of outdegree zero.

Lemma 1.

If G is D-magic, then G contains at most one vertex of outdegree zero. If there is such a vertex, $0\in D$ and the magic constant is n.

Proof. 

If a vertex has outdegree zero, then it has no vertices of distance $d>0$ away from it. Hence, the only label that could contribute to the sink’s weight would be the label on the vertex itself. Thus, $0\in D$. In addition, if two or more vertices were of outdegree zero, then their weights would not be equal as the only contributing values would be the label on that vertex and vertex labels are not repeated. Finally, if any vertex other than the sink had label n, then the weight at that vertex would be at least n, while the sink’s weight would be no larger than $n-1$. This is a contradiction as all the weights must be equal. Hence, the sink must have label n and thus, the magic constant of any graph with a sink is n. □

There is an infinite family of graphs with a single vertex of outdegree zero that permit an orientation that is D-magic. Consider the graph G with $4k+2$ vertices with $k\ge 2$. G consists of two distinct cycles of length $2k$ with vertex sets $\{x_1,\dots ,x_{2k}\}$ and $\{y_1,\dots ,y_{2k}\}$, a vertex v that is connected to exactly one vertex in each cycle and a vertex w that is only connected to vertex v. The oriented edges are as follows: $\{x_{2k}{x}_1,y_{2k}{y}_1,v{x}_1,v{y}_1,vw,x_i{x}_{i+1},y_i{y}_{i+1}$ for $1\le i\le 2k-1\}$. Then, we can create the bijection $f:V\left(G\right)\to \{1,\dots ,4k+2\}$ such that

$f\left(v\right)$	=	$2k+1$
$f\left(w\right)$	=	$4k+2$
$f\left(x_i\right)$	=	$k+i$	$1\le i\le k$
$f\left(x_i\right)$	=	$4k+2-i$	$k+1\le i\le 2k$
$f\left(y_i\right)$	=	$k-i+1$	$1\le i\le k$
$f\left(y_i\right)$	=	$2k+1+i$	$k+1\le i\le 2k.$

Then, f is a $\{0,k\}$-magic labeling of G with magic constant $4k+2$ and vertex w has outdegree zero. Figure 1 provides an example of this construction when $k=2$.

In the remainder of this section, we discuss properties of the magic constants. Contrary to the fact that the magic constant for an undirected graph is unique, the D-magic constant does not have to be the same for any given oriented graph. The proof of the uniqueness in [15] relies on the fact that the graph’s adjacency matrix is the same as its transpose which does not occur for oriented graphs. The example in Figure 2 shows two different magic constants for the same oriented graph.

In the next theorem, we provide tight lower and upper bounds for the magic constants of an oriented graph.

Theorem 2.

If G is a D-magic oriented graph with magic constant k and $n\ge 3$, then $5\le k\le \frac{n(n+1)}{2}$. Furthermore, $k=\frac{n(n+1)}{2}$ iff $diam\left(G\right)<\infty$ and $D=\{0,1,\dots ,diam(G\left)\right\}$.

Proof. 

First, we will show the magic constant cannot be less than 5. Suppose $k<5$. Let $v_i$ be the vertex with label i.

• If $k=1$ and $0\in D$ then $w\left(v_2\right)\ge 2$ and thus $v_2$ would not have the magic constant as its weight. Thus, $0\notin D$, but then there is no way for $w\left(v_1\right)=1$.
• If $k=2$ and $0\in D$, $w\left(v_1\right)\ne 2$. Thus, $0\notin D$, but then $w\left(v_2\right)\ne 2$ as there are no sums of the remaining vertex labels that would total to two.
• If $k=3$ and $0\in D$, then in order for $w\left(v_1\right)=w\left(v_2\right)=3$ we would need both $v_1\to v_2$ and $v_2\to v_1$, creating a bidirectional edge. Since $0\notin D$, we would have that $v_3$ would need to be some distance $d_1\in D$ away from $v_1$. However, $v_1$ would also have to be distance $d_2\in D$ away from $v_3$ (as this is the only way for $w\left(v_1\right)=3$). Suppose without loss of generality that $d_2\le d_1$. If $d_1=d_2$, then $d_1>1$ and we would have a vertex x on the path from $v_1$ to $v_3$ that would be distance $d_1$ away from something larger than three, and thus $w\left(x\right)>3$. If $d_2<d_1$, then $v_1$ would also be distance $d_1$ away from something other than $v_3$, giving $w\left(v_1\right)>3$. Thus, in all cases, we arrive at a contradiction.
• A similar argument holds if $k=4$ using $v_1$ and $v_3$ (instead of $v_1$ and $v_2$).

Thus, k must be at least 5 and the construction in Theorem 3 shows that $k=5$ is possible. If $D=\{0,1,\dots ,diam(G\left)\right\}$, then every label is counted at each vertex giving $k=\frac{n(n+1)}{2}$. Conversely, we know that if $k=\frac{n(n+1)}{2}$, the sum at every vertex is equal to the sum of the first n positive integers which would only happen if every vertex label was included. Hence, $D=\{0,1,\dots ,diam(G\left)\right\}$ and $diam\left(G\right)<\infty$. □

OpenQuestion 1.

Characterize all oriented graphs with $k=5$.

OpenQuestion 2.

Find a better upper bound for k if $D\ne \{0,1,\dots ,diam(G\left)\right\}$.

In the following theorem, we construct a $\left\{1\right\}$-magic oriented graph of order n for each value of k from 5 up to n.

Theorem 3.

For $5\le k\le n,n\ge 5$, there exists an oriented graph G of order n which is $\left\{1\right\}$-magic with magic constant k.

Proof. 

Figure 3 gives the construction technique for any n. All vertices with labels between 2 and $k-2$ are directed towards the vertex labeled k. All vertices with labels between $k+1$ and n are also directed towards the vertex labeled k. The vertex with label k can be directed towards the vertices labeled 1 and $k-1$. Finally, the vertices 1 and $k-1$ are directed towards the vertices labeled 2 and $k-2$. □

OpenQuestion 3.

For $n<k\le \frac{n(n+1)}{2}$, construct an oriented graph of order n which is $\left\{1\right\}$-magic with magic constant k.

OpenQuestion 4.

For $5\le k\le \frac{n(n+1)}{2}$ and $D\ne \left\{1\right\}$, construct an oriented graph G of order n which is D-magic with magic constant k.

4. Classes of $\mathit{D}$-Magic Oriented Graphs

4.1. Trees

Lemma 2.

Any tree with only one sink (vertex of outdegree zero) must have all edges directed towards the sink.

Proof. 

Suppose a tree has a least one edge directed away from the sink. Suppose this edge goes from vertex v to vertex u. Then, vertex u must have at least one edge that is directed outward (otherwise u would also be a sink) and away from the sink, to some new vertex w. This new vertex, w, would also have an edge directed outward and away from the sink. This would continue at each new vertex in this outward directed path until we reach a leaf. However, then this leaf would have outdegree zero, a contradiction. Thus, all edges must be directed toward the sink. □

Theorem 4.

Trees with $n\ge 2$ are not D-magic for any distance set D.

Proof. 

Suppose there is an oriented tree that is D-magic. By Lemma 1, any D-magic tree can have at most one vertex of outdegree zero, and since any oriented tree has at least one vertex of outdegree zero, we know the tree will have exactly one vertex of outdegree zero, say vertex v. If the tree contains only one vertex of outdegree zero, than all edges must be directed towards that vertex by Lemma 2. This oriented tree will have a path of longest length, say length d. We know $0\in D$, but we also know $d\notin D$ as this would cause the weight of some vertex to be greater than n. In addition, no value less than d can be in D as this would allow a vertex on that longest path to have a weight greater than n. Finally, there are no paths of length greater than d, so no other values can be added to D. Hence, the only possible element in D is 0, but that does not create a D-magic graph. Thus, no orientation of trees are D-magic for any set D. □

4.2. Cycles

Lemma 3.

If an oriented cycle is D-magic, then the orientation must be unidirectional.

Proof. 

By Lemma 1, any oriented cycle can have at most one vertex of outdegree zero. Hence, the only orientations which would satisfy this would be the unidirectional cycle (with no vertices of outdegree zero) or the cycle where there is a source and a sink with two unidirectional paths leaving the source and leading to the sink. However, this second orientation is not possible. The vertex of outdegree zero must have label n. Furthermore, at least one of the two vertices coming into that vertex must have outdegree one (otherwise we would have two vertices of outdegree zero); let that vertex be v. Then, v is at distance one from the vertex with label n and that is its only out-neighbor. Hence, any contributions to the weight of that vertex will come from values that are at distance zero or one away. However, this is a problem as the magic constant must be n, $0\in D$, and we know at least one other number must be in D in order for vertex v to have a sum equal to n, but the only other possibility to add to D to increase the weight of v is to add one to D, but this makes the weight of v greater than n. Hence a D-magic labeling of this orientation is not possible and thus the only orientations of a cycle that are D-magic are unidirectional. □

Theorem 5.

There exist D such that $\overrightarrow{C_n}$ is D-magic for all $n\ge 3$. In particular, let $d_1,d_2,\dots ,d_r$ be the divisors of n. If $\exists k\in \mathbb{N}$ such that $n(n+1)=2d_{i}k$ and $k\ge n$, then $\overrightarrow{C_n}$ is D-magic with $D=\{0,d_i,2d_i,\dots ,(\frac{n}{d_i}-1)d_i\}$ and $\left|D\right|=n/d_i$.

Proof. 

For any cycle, $\overrightarrow{C_n}$, $D=\{0,1,\dots ,n-1\}$ will give a D-magic graph with magic constant $n(n+1)/2$ as at any vertex, all labels will be counted in the sum.

Let $d_i$ be a divisor of n. Let $D=\{0,d_i,2d_i,(n/d_i-1)d_i\}$. Then, if $v_0,v_2,\dots ,v_{n-1}$ is the vertex set of $C_n$, we can partition this set into $d_i$ sets, $P_1,P_2,\dots ,P_{d_i}$, each of size $n/d_i$, where $P_1=\{v_0,v_{d_i},v_{2d_i},\dots ,v_{(n/d_i-1)d_i}\}$ and $P_j$ is formed by adding $j-1$ (modulo n) to each of the subscripts of the entries of $P_1$. Since this partitions the set n into $d_i$ sets and $n(n+1)=2d_{i}k$ for some $k\ge n\in \mathbb{N}$, by Theorem 1, we know there is a way to label the vertices with values from $\{1,\dots ,n\}$ so that the sum of the labels of each of these vertex sets is the same. □

By construction of these D-magic labelings, if $\overrightarrow{C_n}$ is D-magic, it is also $D+c$-magic where $D+c$ consists of the elements of D that have each been increased by c (mod n) and $c\in \{1,2,\dots ,n-1\}$. So, for example, $\overrightarrow{C_6}$ is $\{0,3\}$-magic and thus also $\{1,4\}$-magic and $\{2,5\}$-magic. Combining this with Remark 1, we also know $\overrightarrow{C_6}$ is $\{0,1,3,4\}$-magic, $\{0,2,3,5\}$-magic, $\{1,2,4,5\}$-magic, and of course $\{0,1,2,3,4,5\}$-magic.

OpenQuestion 5.

Find all Ds s.t. $\overrightarrow{C_n}$ is D-magic.

4.3. Multipartite Graphs

Theorem 6.

For $m\equiv 0$ (mod 4), there is an orientation of $K_{m,m}$ that is D-magic for $D\in \left\{\right\{0,4\},\{1\},\{2\},\{3\left\}\right\}$ or any D that is a union of these sets.

Proof. 

Let $K_{m,m}$ be the complete bipartite graph with partite sets $A=\{a_1,\dots ,a_m\}$ and $B=\{b_1,\dots ,b_m\}$. Note that $K_{m,m}$ has $n=2m$ vertices. First, we group the vertices within each partite set into pairs. In A, this would give sets ${\alpha }_1=\{a_1,a_2\},\dots ,{\alpha }_{m/2}=\{a_{m-1},a_m\}$ and ${\beta }_1=\{b_1,b_2\},\dots ,{\beta }_{m/2}=\{b_{m-1},b_m\}$. Within each set of two, label one vertex s and the other vertex $2m+1-s$ for $1\le s\le m$. This would give a sum of $2m+1$ for each set of pairs. Then, orient the edges in the following way: vertices in ${\alpha }_i$ will be oriented to vertices in the sets ${\beta }_i,{\beta }_{i+1},\dots ,{\beta }_{\frac{m}{4}+i-1}$ and vertices in ${\beta }_i$ will be oriented to vertices in the sets ${\alpha }_{i+1},\dots ,{\alpha }_{\frac{m}{4}+i}$ where all additions are done modulo $m/2$. Thus, each vertex is oriented towards $m/4$ pairs of vertices and hence each vertex is oriented towards $m/2$ vertices. This gives a total of $2·\frac{m}{4}·2m=m^2$ edges and thus each edge is accounted for and has only one orientation. This gives a magic constant of $k=\frac{m}{4}(2m+1)$ for any $D\in \left\{\right\{0,4\},\{1\},\{2\},\{3\left\}\right\}$. The magic constant would be $2k$ for any union of two sets, $3k$ for any union of three sets, and $4k=m(2m+1)=n(n+1)/2$ for the union of all four sets. Figure 4 gives an example of this labeling when $m=4$. □

OpenQuestion 6.

Is $K_{m,m}$ D-magic for $m\neg \equiv 0$ (mod 4)?

Theorem 7. 

(a) Let $s\ge 3$ be odd and $n\ge 5$. If $n(n+1)=2st$ and $t\ge n$, then there exists a partition of n into s parts such that $n=n_1+n_2+\dots +n_s$ and $K_{n_1,n_2,\dots ,n_s}$ has an orientation that is $\left\{1\right\}$-magic with magic constant $\frac{(s-1)t}{2}$, $\left\{2\right\}$-magic with magic constant $\frac{(s-1)t}{2}$, and $\{1,2\}$-magic with magic constant $(s-1)t$.

(b) Let $s\ge 4$ be even and $n\ge 7$. If $n(n+1)=2st$ and $t\ge n$, then there is a partition of n into s parts with $n=n_1+n_2+\dots +n_s$ and $K_{n_1,n_2,\dots ,n_s}-I$ (where I is a 1-factor) has an orientation that is $\left\{1\right\}$-magic with magic constant $\frac{(s-2)t}{2}$, $\left\{2\right\}$-magic with magic constant $\frac{st}{2}$, and $\{1,2\}$-magic with magic constant $(s-1)t$.

Proof. 

Let $u_o,u_1,\dots ,u_s$ be the vertices of $K_s$. We decompose $K_s$ into Hamiltonian cycles using Walecki’s construction where each cycle starts at $u_0$ [18]. Then, orient each cycle in a clockwise direction starting at the vertex $u_0$. This will give each vertex $(s-1)/2$ edges directed outward and $(s-1)/2$ edges directed inward. Then, we replace each vertex of $K_s$ with $n_i$ vertices for $1\le i\le s$ and maintain all the original connections. For example, in $K_s$, $u_0$ would be connected to $u_1$ and so in our newly constructed graph, all the vertices now at $u_0$ would be connected to all the vertices now at $u_1$. Using Theorem 1, we label the vertices of each new set of replaced vertices with values so that each new set of vertices has the same sum, t.

Thus, every vertex will be at distance one away from $(s-1)/2$ sets of vertices and each set sums to t, giving a $\left\{1\right\}$-magic constant of $(s-1)t/2$. Similarly, since every vertex in a oriented complete graph is at distance one or two away from any other vertex, we also have that every vertex will be at distance two away from $(s-1)/2$ sets of vertices and each set sums to t, giving a $\left\{2\right\}$-magic constant of $(s-1)t/2$. Finally, since all vertices are at distance one or two away from each other, the $\{1,2\}$-magic constant is $(s-1)t$.

In a similar way, we can decompose $K_s-I$ into $\frac{s}{2}-1$ Hamiltonian cycles using Walecki’s construction where each cycle starts at $u_0$ [18]. Then, orient each cycle in a clockwise direction starting at the vertex $u_0$. This gives each vertex $\frac{s}{2}-1$ edges directed outward. Then, we replace each vertex of $K_s$ with $n_i$ vertices for $1\le i\le s$ and maintain all the original connections. In this case, every vertex will be at distance one away from $\frac{s}{2}-1$ sets of vertices and each set sums to t, giving a $\left\{1\right\}$-magic constant of $(s-2)t/2$. Similarly, since every vertex in this orientation of $K_s-I$ is at distance one or two away from any other vertex, we also have that every vertex is at distance two away from $s/2$ sets of vertices and each set sums to t, giving a $\left\{2\right\}$-magic constant of $\left(st\right)/2$. Finally, since all vertices are distance one or two away from each other, the $\{1,2\}$-magic constant is $(s-1)t$. □

OpenQuestion 7.

Let $s\ge 2$, s even, $n\ge s$ and $n_1+\dots +n_s=n$. Is $K_{n_1,\dots ,n_s}$ D-magic for some nontrivial D-set?

5. Conclusions

As can be seen by the questions posed, the study of D-magic oriented graphs is rich with future directions. One possible avenue of additional research is to determine for a given arbitrary oriented graph which D sets make the graph D-magic. Conversely, one could start with a given D set and ask which oriented graphs are D-magic.

Exploring the symmetries between oriented D-magic graphs and D-magic graphs, we see that both have trivial D sets that produce a D-magic labeling (when $diam\left(G\right)<\infty$ and $D=\{0,1,2,\dots ,diam(G\left)\right\}$). While trees, cycles, and multipartite graphs have been studied in both cases, the results are quite different. For example, a complete multipartite graph is not $\left\{2\right\}$-magic, but we have shown there is an orientation of various complete multipartite graphs with a $\left\{2\right\}$-magic labeling. We also know that $P_3$ is $\left\{1\right\}$-magic, but there is no orientation that makes it a $\left\{1\right\}$-magic oriented graph. Hence, it would be worth knowing under what conditions a D-magic graph has an orientation that is also D-magic.

Similarly, while the magic constant is unique in the unoriented case, the magic constant does not have to be unique in the oriented case. While we did not allow for bidirectional edges, if bidirectional edges were allowed, any D-magic graph could be oriented to be D-magic by replacing each edge with a bidirectional edge. Exploring these symmetries further is also an interesting line of future work.