Twin signed domination numbers in directed graphs
Let D=(V,A) be a finite simple directed graph (shortly digraph). A function f:V⟶{−1,1} is called a twin signed dominating function (TSDF) if f(N⁻[v])≥1 and f(N⁺[v])≥1 for each vertex v∈V. The twin signed domination number of D is γs*(D)=min{ω(f)∣f is a TSDF of D}. In this paper, we initiate the stud...
Збережено в:
| Дата: | 2017 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2017
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/156254 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Twin signed domination numbers in directed graphs / M. Atapour, S. Norouzian, S.M. Sheikholeslami, L. Volkmann // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 1. — С. 71-89. — Бібліогр.: 10 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-156254 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1562542019-06-19T01:26:42Z Twin signed domination numbers in directed graphs Atapour, M. Norouzian, S. Sheikholeslami, S.M. Volkmann, L. Let D=(V,A) be a finite simple directed graph (shortly digraph). A function f:V⟶{−1,1} is called a twin signed dominating function (TSDF) if f(N⁻[v])≥1 and f(N⁺[v])≥1 for each vertex v∈V. The twin signed domination number of D is γs*(D)=min{ω(f)∣f is a TSDF of D}. In this paper, we initiate the study of twin signed domination in digraphs and we present sharp lower bounds for γs*(D) in terms of the order, size and maximum and minimum indegrees and outdegrees. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs. 2017 Article Twin signed domination numbers in directed graphs / M. Atapour, S. Norouzian, S.M. Sheikholeslami, L. Volkmann // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 1. — С. 71-89. — Бібліогр.: 10 назв. — англ. 1726-3255 2010 MSC:05C69. http://dspace.nbuv.gov.ua/handle/123456789/156254 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
Let D=(V,A) be a finite simple directed graph (shortly digraph). A function f:V⟶{−1,1} is called a twin signed dominating function (TSDF) if f(N⁻[v])≥1 and f(N⁺[v])≥1 for each vertex v∈V. The twin signed domination number of D is γs*(D)=min{ω(f)∣f is a TSDF of D}. In this paper, we initiate the study of twin signed domination in digraphs and we present sharp lower bounds for γs*(D) in terms of the order, size and maximum and minimum indegrees and outdegrees. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs. |
| format |
Article |
| author |
Atapour, M. Norouzian, S. Sheikholeslami, S.M. Volkmann, L. |
| spellingShingle |
Atapour, M. Norouzian, S. Sheikholeslami, S.M. Volkmann, L. Twin signed domination numbers in directed graphs Algebra and Discrete Mathematics |
| author_facet |
Atapour, M. Norouzian, S. Sheikholeslami, S.M. Volkmann, L. |
| author_sort |
Atapour, M. |
| title |
Twin signed domination numbers in directed graphs |
| title_short |
Twin signed domination numbers in directed graphs |
| title_full |
Twin signed domination numbers in directed graphs |
| title_fullStr |
Twin signed domination numbers in directed graphs |
| title_full_unstemmed |
Twin signed domination numbers in directed graphs |
| title_sort |
twin signed domination numbers in directed graphs |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2017 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/156254 |
| citation_txt |
Twin signed domination numbers in directed graphs / M. Atapour, S. Norouzian, S.M. Sheikholeslami, L. Volkmann // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 1. — С. 71-89. — Бібліогр.: 10 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT atapourm twinsigneddominationnumbersindirectedgraphs AT norouzians twinsigneddominationnumbersindirectedgraphs AT sheikholeslamism twinsigneddominationnumbersindirectedgraphs AT volkmannl twinsigneddominationnumbersindirectedgraphs |
| first_indexed |
2025-07-14T08:42:46Z |
| last_indexed |
2025-07-14T08:42:46Z |
| _version_ |
1837611160180883456 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 24 (2017). Number 1, pp. 71–89
c© Journal “Algebra and Discrete Mathematics”
Twin signed domination numbers
in directed graphs
M. Atapour, S. Norouzian, S. M. Sheikholeslami
and L. Volkmann
Communicated by D. Simson
Abstract. Let D = (V, A) be a finite simple directed graph
(shortly digraph). A function f : V −→ {−1, 1} is called a twin sig-
ned dominating function (TSDF) if f(N−[v]) > 1 and f(N+[v]) > 1
for each vertex v ∈ V . The twin signed domination number of D is
γ∗
s
(D) = min{ω(f) | f is a TSDF of D}. In this paper, we initiate
the study of twin signed domination in digraphs and we present
sharp lower bounds for γ∗
s
(D) in terms of the order, size and maxi-
mum and minimum indegrees and outdegrees. Some of our results
are extensions of well-known lower bounds of the classical signed
domination numbers of graphs.
1. Introduction
Throughout this paper, D is a finite simple directed graph with vertex
set V (D) and arc set A(D) (briefly V and A). A digraph without directed
cycles of length 2 is an oriented graph. We write d+
D(v) for the outdegree of
a vertex v and d−
D(v) for its indegree. The minimum and maximum indegree
and minimum and maximum outdegree of D are denoted by δ−(D) = δ−,
∆−(D) = ∆−, δ+(D) = δ+ and ∆+(D) = ∆+, respectively. A digraph D
is called regular or r-regular if δ−(D) = δ+(D) = ∆−(D) = ∆+(D) = r.
If uv is an arc of D, then we also write u → v, and we say that v is an
2010 MSC: 05C69.
Key words and phrases: twin signed dominating function, twin signed domina-
tion number, directed graph.
72 Twin signed domination numbers in directed graphs
out-neighbor of u and u is an in-neighbor of v. For every vertex v, we
denote the set of in-neighbors and out-neighbors of v by N−(v) = N−
D (v)
and N+(v) = N+
D (v), respectively. Let N−
D [v] = N−[v] = N−(v)∪{v} and
N+
D [v] = N+[v] = N+(v)∪{v}. If X ⊆ V (D), then D[X] is the subdigraph
induced by X. If X ⊆ V (D) and v ∈ V (D), then A(X, v) is the set of arcs
from X to v. We denote by A(X, Y ) the set of arcs from a subset X to a
subset Y . We denote by D−1 the digraph obtained from D by reversing
the arcs of D. For a real-valued function f : V (D) −→ R the weight of
f is w(f) =
∑
v∈V f(v), and for S ⊆ V , we define f(S) =
∑
v∈S f(v), so
w(f) = f(V ). Consult [8] for the notation and terminology which are not
defined here.
Let D = (V, A) be a finite simple digraph. A signed dominating
function (abbreviated SDF) of D is a function f : V → {−1, 1} such
that f(N−[v])] > 1 for every v ∈ V . The signed domination number for a
directed graph (digraph) D is
γs(D) = min{ω(f) | f is a SDF of D}.
A γs(D)-function is a SDF of D of weight γs(D). The signed domination
number of a digraph was introduced by by Zelinka in [9] and has been
studied by several authors (see for example [2, 6]).
A signed dominating function of D is called a twin signed dominating
function (briefly TSDF) if it also is a signed dominating function of
D−1, i.e., f(N+[v]) > 1 for every v ∈ V . The twin signed domination
number for a digraph D is γ∗
s (D) = min{ω(f) | f is a TSDF of D}. This
definition is analogously to the definition of twin domination number in
digraphs which was introduced by Chartrand et al. [3] and has been studied
by Arumugam et al. [1]. For any function f : V → {−1, 1}, we define
P = Pf = {v ∈ V | f(v) = 1} and M = Mf = {v ∈ V | f(v) = −1}.
Since every TSDF of D is a SDF on both D and D−1 and since the
constant function 1 is a TSDF of D, we have
max{γs(D), γs(D−1)} 6 γ∗
s (D) 6 n. (1)
In this paper, we initiate the study of the twin signed domination
number and establish some sharp lower bounds on twin signed domination
number of digraphs.
We make use of the following results and observations in this paper.
Proposition A ([9]). For any digraph D of order n > 2, γs(D) ≡
n (mod 2).
Atapour, Norouzian, Sheikholeslami, Volkmann 73
Observation 1. For any digraph D of order n > 2, γ∗
s (D) ≡ n (mod 2).
Proof. Let f be a γ∗
s (D)-function . Since n = |P |+|M | and γ∗
s (D) = |P |−
|M |, we deduce that n−γ∗
s (D) = 2|M | and hence γ∗
s (D) ≡ n (mod 2).
Corollary 2. For any digraph D of order n > 2, γ∗
s (D) ≡ γs(D) (mod 2).
Observation 3. Let D be a digraph of order n. Then γ∗
s (D) = n if and
only if every vertex has either an out-neighbor with indegree one or an
in-neighbor with outdegree one.
Proof. One side is clear. For the other side, assume that γ∗
s (D) = n.
Suppose to the contrary that there exists a vertex v ∈ V (D) such that
d−(u) > 2 for each u ∈ N+[v] and d+(w) > 2 for each w ∈ N−[v]. Define
f : V (D) → {−1, 1} by f(v) = −1 and f(x) = 1 for x ∈ V (D) \ {v}.
Obviously, f is a twin signed dominating function of D of weight less
than n, a contradiction. This completes the proof.
Corollary 4. If Cn and Pn are the directed cycle and path on n vertices,
then γ∗
s (Cn) = γ∗
s (Pn) = n.
Here we determine the exact value of the twin signed domination num-
ber for particular types of tournaments. Let n = 2r + 1 for some positive
integer r. We define the circulant tournament CT(n) with n vertices as
follows. The vertex set of CT(n) is V (CT(n)) = {u0, u1, . . . , un−1} and
for each i, the arcs go from ui to the vertices ui+1, . . . , ui+r, where the
indices are taken modulo n. The proof of the next result can be found
in [2].
Proposition B. Let n > 5 and n = 2r + 1, where r is a positive integer.
Then
γs(CT(n)) =
{
3 if r is even
5 if r is odd.
The next Proposition shows that γ∗
s (CT(n)) = γs(CT(n))
Proposition 5. Let n > 5 and n = 2r + 1, where r is a positive integer.
Then γ∗
s (CT(n)) = γs(CT(n)).
Proof. By (1) and Proposition B, we have
γ∗
s (CT(n)) >
{
3 if r is even
5 if r is odd.
74 Twin signed domination numbers in directed graphs
Assume that s = ⌊ r−2
2 ⌋, V − = {u0, u1, . . . , us, ur+1, . . . , ur+s} and V + =
V (CT(n)) − V −. For any vertex v ∈ V (CT(n)), we have |N−[v]| = r + 1,
|N+[v]| = r + 1, |N+[v] ∩ V −| 6 s + 1 and |N−[v] ∩ V −| 6 s + 1. Define
f : V (CT(n)) → {−1, 1} by f(v) = 1 if v ∈ V + and f(v) = −1 when
v ∈ V −. Clearly, f(N−[v]) > r−2s−1 > 1 and f(N+[v]) > r−2s−1 > 1
for each v ∈ V . Therefore f is a TSDF on CT(n) of weight 3 if r is even
and 5 when r is odd. Thus
γ∗
s (CT(n)) 6 ω(f) =
{
3 if r is even
5 if r is odd,
and the proof is complete.
As we observed in (1), γ∗
s (D) > max{γs(D), γs(D−1)}. Now we show
that the difference γ∗
s (D) − max{γs(D), γs(D−1)} can be arbitrarily large.
Theorem 6. For every positive integer k, there exists a digraph D such
that
γ∗
s (D) − max{γs(D), γs(D−1)} > 4k − 4.
Proof. Let k > 1 be an integer, and let D be a digraph with vertex set
V (D) = {x, y, u1, u2, . . . , u2k, v1, v2, . . . , v2k}
and edge set
E(D)={(x, ui),(vk+i, ui), (vk+i, y), (uk+i, x), (uk+i, vi), (y, vi) | 16 i6k}.
Obviously, D ∼= D−1 and so, γs(D) = γs(D−1). It is easy to verify that the
function f : V (D) → {−1, 1} defined by f(ui) = f(vi) = −1 for 1 6 i 6 k
and f(u) = 1 otherwise, is a SDF of D and so γs(D) 6 2. Now let g be
a γ∗
S(D)-function. Since N+[u] = {u} for each u ∈ {ui, vi | 1 6 i 6 k}
and N−[u] = {u} for each u ∈ {uk+i, vk+i | 1 6 i 6 k}, we must have
g(u) = 1 for each u ∈ V (D)−{x, y}. It follows that γ∗
s (D) > 4k −2. Thus
γ∗
s (D) − max{γs(D), γs(D−1)} > 4k − 4, and the proof is complete.
2. Lower bounds on γ∗
s
(D)
In this section we establish lower bounds for γ∗
s (D) in terms of the
order, size, the maximum and minimum indegree and outdegree of D. We
start with the following lemma.
Atapour, Norouzian, Sheikholeslami, Volkmann 75
Lemma 7. Let D be a digraph of order n and let f be a γ∗
s (D)-function.
Then
1) (1 + ⌈ δ−
2 ⌉)|M | 6 |A(P, M)| 6 ⌊∆+
2 ⌋|P |.
2) (1 + ⌈ δ+
2 ⌉)|M | 6 |A(M, P )| 6 ⌊∆−
2 ⌋|P |.
3) |A(P, P )| > max{⌈ δ+
2 ⌉|P |, ⌈ δ−
2 ⌉|P |}.
Proof. (1) Let v ∈ M . Since f(N−[v]) > 1, we deduce that |A(P, v)| >
1+⌈d−(v)
2 ⌉ > 1+⌈ δ−
2 ⌉. It follows that |A(P, M)| > (1+⌈ δ−
2 ⌉)|M |. Assume
now that v ∈ P . Since f(N+[v]) > 1, we have |A(v, M)| 6 ⌊d+(v)
2 ⌋ 6 ⌊∆+
2 ⌋
and so |A(P, M)| 6 ⌊∆+
2 ⌋|P |. Combining the inequalities, we obtain (1).
(2) The proof is similar to the proof of (1).
(3) Let v ∈ P . Then |A(v, P )| > ⌈d+(v)
2 ⌉ > ⌈ δ+
2 ⌉ and |A(P, v)| >
⌈d−(v)
2 ⌉ > ⌈ δ−
2 ⌉ because f(N+[v])>1 and f(N−[v]) > 1. Thus |A(P, P )| >
max{⌈ δ+
2 ⌉|P |, ⌈ δ−
2 ⌉|P |}, and the proof is complete.
Theorem 8. Let D be a digraph of order n, minimum indegree δ−,
minimum outdegree δ+, maximum indegree ∆− and maximum outdegree
∆+. Then
γ∗
s (D) > max
{
1 + ⌈ δ−
2 ⌉ − ⌊∆+
2 ⌋
1 + ⌈ δ−
2 ⌉ + ⌊∆+
2 ⌋
n,
1 + ⌈ δ+
2 ⌉ − ⌊∆−
2 ⌋
1 + ⌈ δ+
2 ⌉ + ⌊∆−
2 ⌋
n
}
.
Furthermore, this bound is sharp for directed cycles and paths.
Proof. Let f be a minimum TSDF of D. Using Lemma 7 and replacing
|M | and |P | by n−γ∗
s
(D)
2 and n+γ∗
s
(D)
2 in (1) and (2), the desired inequality
follows.
Theorem 8 implies the next result immediately.
Corollary 9. If D is an r-regular digraph with r > 1, then γ∗
s (D) >
n/(r + 1) when r is even and γ∗
s (D) > 2n/(r + 1) when r is odd.
Example 1. If K∗
n is the complete digraph of order n, then γ∗
s (K∗
n) = 1
when n is odd and γ∗
s (K∗
n) = 2 when n is even.
Proof. According to Corollary 9, we have γ∗
s (K∗
n) > 2 when n is even and
γ∗
s (K∗
n) > 1 when n is odd. On the other hand if n = 2p is even, then
assign to p + 1 vertices the value 1 and to p − 1 vertices the value -1.
Then f(N−[v]) = f(N+[v]) = 2 for each vertex v. Thus f is a TSDF of
K∗
n of weight 2 and so γ∗
s (K∗
n) = 2 when n is even. If n = 2p + 1 is odd,
76 Twin signed domination numbers in directed graphs
then assign to p + 1 vertices the value 1 and to p vertices the value -1.
Then f(N−[v]) = f(N+[v]) = 1 for each vertex v. Thus f is a TSDF of
K∗
n of weight 1 and so γ∗
s (K∗
n) = 1 when n is odd.
This is another example that shows the sharpness of Theorem 8. If G is
a graph, then a signed dominating function is defined in [4] as a function
f : V (G) −→ {−1, 1} such that f(N [v]) > 1 for all v ∈ V (G). The
signed domination number γs(G) of G is the minimum weight of a signed
dominating function on G. The associated digraph D(G) of a graph G is
the digraph obtained when each edge e of G is replaced by two oppositely
oriented arcs with the same ends as e. Since N−
D(G)[v] = N+
D(G)[v] = NG[v]
for each v ∈ V (G) = V (D(G)), the following useful observation is valid.
Observation 10. If D(G) is the associated digraph of a graph G, then
γ∗
s (D(G)) = γs(G).
Theorem 8 and Observation 10 lead immediately to an lower bound
for the signed domination number of graphs.
Corollary 11. Let G be a graph of order n, minimum degree δ and
maximum degree ∆. Then
γs(G) >
1 + ⌈ δ
2⌉ − ⌊∆
2 ⌋
1 + ⌈ δ
2⌉ + ⌊∆
2 ⌋
n.
Since
1 + ⌈ δ
2⌉ − ⌊∆
2 ⌋
1 + ⌈ δ
2⌉ + ⌊∆
2 ⌋
n >
δ + 2 − ∆
δ + 2 + ∆
n,
Corollary 11 implies the following known bound.
Corollary 12 ([10]). If G is a graph of order n, minimum degree δ and
maximum degree ∆, then
γs(G) >
δ + 2 − ∆
δ + 2 + ∆
n,
Using Corollary 9 and Observation 10, we obtain the next result.
Corollary 13. If G is an r-regular graph with r > 1, then γs(G) >
n/(r + 1) when r is even and γs(G) > 2n/(r + 1) when r is odd.
Corollary 13 can be found in [4] and [5].
Atapour, Norouzian, Sheikholeslami, Volkmann 77
Theorem 14. If D is a digraph of order n and maximum indegree ∆−,
then
γ∗
s (D) > 2
⌈
∆−
2
⌉
+ 2 − n.
Proof. Let w ∈ V (D) be a vertex of maximum indegree d−(w) = ∆−, and
let f be a γ∗
s (D)-function. Assume first that w ∈ M . Since f(N−[w]) > 1,
we deduce that |A(P, w)| > 1 + ⌈∆−
2 ⌉. It follows that
n + γ∗
s (D)
2
= |P | > |A(P, w)| > 1 +
⌈
∆−
2
⌉
,
and this leads to the desired inequality. If w ∈ P , then f(N−[w]) > 1
implies that |A(P, w)| > ⌈∆−
2 ⌉. We conclude that
n + γ∗
s (D)
2
= |P | > |A(P, w)| + 1 > 1 +
⌈
∆−
2
⌉
,
and the proof is complete.
The condition f(N+[v]) > 1 for each vertex v, yields analogously the
next result.
Theorem 15. If D is a digraph of order n and maximum outdegree ∆+,
then γ∗
s (D) > 2⌈∆+
2 ⌉ + 2 − n.
Example 1 demonstrates that Theorems 14 and 15 are sharp.
Theorem 16. For any digraph D of order n, size m, minimum indegree δ−
and minimum outdegree δ+,
γ∗
s (D) >
n(2 + 2⌈ δ+
2 ⌉ + ⌈ δ−
2 ⌉) − 2m
2 + ⌈ δ−
2 ⌉
.
This bound is sharp for directed cycles.
Proof. Let f be a γ∗
s (D)-function. By Lemma 7, we have
m > |A(M, P )| + |A(P, M)| + |A(P, P )|
> (1 + ⌈δ−
2
⌉)|M | + (1 + ⌈δ+
2
⌉)|M | + ⌈δ+
2
⌉|P |
= ⌈δ+
2
⌉n + (2 + ⌈δ−
2
⌉)(
n − γ∗
s (D)
2
).
This leads to the desired inequality.
78 Twin signed domination numbers in directed graphs
Theorem 17. Let D be a digraph of order n, maximum indegree ∆− and
maximum outdegree ∆+. Then γ∗
s (D) >
4−⌊ ∆−
2
⌋−⌊ ∆+
2
⌋
4+⌊ ∆−
2
⌋+⌊ ∆+
2
⌋
n. This bound is
sharp for directed cycles and paths.
Proof. Let f be a γ∗
s (D)-function and let v ∈ M . Since f(N+[v]) > 1 and
f(N−[v]) > 1, we conclude that |A(v, P )| > 2 and |A(P, v)| > 2 and thus
|A(M, P )| + |A(P, M)| > 4|M |. Using Lemma 7 (Parts 1, 2), it follows
that
|P |(⌊∆−
2
⌋ + ⌊∆+
2
⌋) > 4|M |. (2)
Replacing |M | and |P | by n−γ∗
s
(D)
2 and n+γ∗
s
(D)
2 in (2), we obtain the
desired bound.
Theorem 18. For any digraph D of order n and size m,
γ∗
s (D) > n − m
3
.
Furthermore, the bound is sharp.
Proof. Let f be a γ∗
s (D)-function. In view of the proof of Theorem 17,
|A(P, M)| > 2|M | and |A(M, P )| > 2|M |. If x ∈ P , then it follows from
f(N+[x]) > 1 that |A(x, P )| > |A(x, M)|. This implies that |A(P, P )| >
|A(P, M)| > 2|M |. Hence m > |A(M, P )|+ |A(P, M)|+ |A(P, P )| > 6|M |.
Since n = |P | + |M |, we deduce that γ∗
s (D) = |P | − |M | = n − 2|M | >
n − m
3 .
To prove the sharpness, let G be a graph of order n(G) and size m(G).
Assume that D is a digraph obtained from G by replacing every edge
xy ∈ E(G), by three new vertices zxy, uxy, vxy and arcs (x, zxy), (y, zxy),
(x, uxy), (y, vxy), (zxy, uxy) and (zxy, vxy). Then n(D) = n(G)+3m(G) and
m(D) = 6m(G). It is easy to see that the function f : V (D) → {−1, 1}
that assigns −1 to zxy for each edge xy ∈ E(G) and +1 otherwise, is a
TSDF of D with ω(f) = n(D) − m(D)
3 as desired.
Using an idea in [10], we prove the next sharp lower bound.
Theorem 19. Let D be a digraph of order n. Then
γ∗
s (D) > 2
⌈
−1 +
√
8n + 1
2
⌉
− n,
and this bound is sharp.
Atapour, Norouzian, Sheikholeslami, Volkmann 79
Proof. Let f be a γ∗
s (D)-function. In view of the proof of Theorem 17,
|A(M, P )| > 2|M |. Hence ther exists a vertex v ∈ P such that |A(M, v)| >
2|M |/|P |. Since f(N−[v]) > 1, we have |A(P, v)| > |A(M, v)|. Therefore
it follows that
|P | > |A(P, v)| + 1 > |A(M, v)| + 1 >
2|M |
|P | + 1
and so |P |2 + |P | − 2n > 0. This implies that
|P | > −1 +
√
8n + 1
2
,
and thus we obtain
γ∗
s (D) = 2|P | − n > 2
⌈
−1 +
√
8n + 1
2
⌉
− n.
We now show that for any positive integer n, there exists a digraph
H of order n with equality in the bound above. For n = 1, 2 let H = K∗
n.
Assume next that n > 3, and let t = ⌈(−1 +
√
8n + 1)/2⌉. Let H be the
associated digraph of the following graph G. Let G be the graph obtained
from Kt ∪ Kn−t by joining each vertex of Kn−t to a pair of vertices of
Kt such that each pair of vertices in Kt is joined to at most on vertex
in Kn−t. Note that this is possible since n − t 6
(t
2
)
. Define the function
f : V (H) −→ {−1, 1} by f(v) = 1 for v ∈ K∗
t and f(v) = −1 otherwise.
Then f is a TSDF of H, and thus γ∗
s (H) 6 2t − n. Applying the bound
above, we obtain γ∗
s (H) = 2t − n.
Following a procedure in [7], we improve Theorem 19 for bipartite
digraphs.
Theorem 20. Let D be a bipartite digraph of order n. Then
γ∗
s (D) > 4
√
n + 1 − n − 4,
and this bound is sharp.
Proof. Let f be a γ∗
s (D)-function, and let X and Y be the partite sets of
D. In addition, let X+ and X− (Y + and Y −) be the sets of vertices in
X (in Y ) assigning the values 1 and -1, respectively.
Assume first that Y − 6= ∅. Since f(N+[y]) > 1, we observe that
|A(y, X+)| > 2 for each vertex y ∈ Y − and thus |A(Y −, X+)| > 2|Y −|.
80 Twin signed domination numbers in directed graphs
Hence there exists a vertex v ∈ X+ such that |A(Y −, v)| > 2|Y −|/|X+|.
It follows that
1 6 f(N−[v]) 6 1 + |Y +| − |A(Y −, v)| 6 1 + |Y +| − 2|Y −|
|X+|
and therefore |Y +||X+| > 2|Y −|. Note that this inequality remains valid
when Y − = ∅. Analogously, one can show |Y +||X+| > 2|X−|. Adding
the last two inequalities, we obtain
2|X+||Y +| > 2|X−| + 2|Y −| = 2n − 2|X+| − 2|Y +|.
Using this inequality and the fact that 4|X+||Y +| 6 (|X+| + |Y +|)2, we
deduce that
(|X+| + |Y +| + 2)2
> 4n + 4
and so
|X+| + |Y +| > 2
√
n + 1 − 2.
This implies
γ∗
s (D) = 2(|X+| + |Y +|) − n > 4
√
n + 1 − n − 4.
To prove the sharpness, let t > 1 be an integer, and let H be the
associated digraph of the following bipartite graph G. Let G be the disjoint
union of K2t,2t with the partite sets X and Y , and the vertex sets A and
B with |A| = |B| = 2t2 by adding edges between A and X and B and
Y such that each vertex in A is joined to exactly 2 vertices in X, each
vertex in X is joined to exactly 2t vertices in A, and each vertex in B is
joined to exactly 2 vertices in Y , and each vertex in Y is joined to exactly
2t vertices in B. Then H has order n(H) = 4t2 + 4t. Define the function
f : V (H) −→ {−1, 1} by f(v) = 1 for v ∈ K∗
2t,2t and f(v) = −1 otherwise.
Then f is a TSDF of H and thus γ∗
s (H) 6 4t − 4t2. Applying the bound
above, we obtain γ∗
s (H) = 4t − 4t2 = 4
√
n(H) + 1 − n(H) − 4.
Theorem 21. Let D be a digraph of order n and let d1 > d2 > · · · > dn
be the degree sequence of the underling graph G of D. If s is the smallest
positive integer for which
∑s
i=1 di − ∑n
i=s+1 di > 4(n − s), then
γ∗
s (D) > 2s − n.
Furthermore, this bound is sharp.
Atapour, Norouzian, Sheikholeslami, Volkmann 81
Proof. Let f be a γ∗
s (D)-function and p = |P |. Since f([N+
D [v]) > 1 and
f(N−
D [v]) > 1 for each v ∈ V (D), we have
n 6
∑
v∈V
f(N+
D [v])
=
∑
v∈V
(d+
D(v) + 1)f(v) = |P | − |M | +
∑
v∈P
d+
D(v) −
∑
v∈M
d+
D(v)
and
n 6
∑
v∈V
f(N−
D [v])
=
∑
v∈V
(d−
D(v) + 1)f(v) = |P | − |M | +
∑
v∈P
d−
D(v) −
∑
v∈M
d−
D(v).
Summing the above inequalities, we deduce that
2n 6 2(|P | − |M |) +
∑
v∈P
(d+
D(v) + d−
D(v)) −
∑
v∈M
(d+
D(v) + d−
D(v))
= 2(2p − n) +
∑
v∈P
degG(v) −
∑
v∈M
degG(v)
6 4p − 2n +
p
∑
i=1
di −
n
∑
i=p+1
di.
Thus 4(n − p) 6
∑p
i=1 di − ∑n
i=p+1 di. By the assumption on s, we
must have p > s. This implies that γ∗
s (D) = 2p − n > 2s − n.
To prove the sharpness, let D be the digraph obtained from two
disjoint directed cycles (u1, u2, . . . , uk) and (v1, v2, . . . , vk) by adding k
new vertices w1, w2, . . . , wk and adding arcs uiwi, viwi, wiui+1, wivi+1
for each i, where n + 1 = 1. Obviously, the order of D is 3k and the
underlying graph of D is 4-regular. Therefore, the smallest positive integer
s satisfying
∑s
i=1 di − ∑n
i=s+1 di > 4(n − s) is s = 2k. Thus γ∗
s (D) > k.
Now define f : V (D) → {−1, 1} by f(wi) = −1, f(ui) = f(vi) = 1 for
each i. Obviously f is a TSDF of D with ω(f) = k. This completes the
proof.
3. Twin Signed Domination in Oriented Graphs
Let G be the complete bipartite graph K4,4 with bipartite sets V1 =
{v1, . . . , v4} and V2 = {u1, . . . , u4}. Let D1 be an orientation of G such
that all arcs go from V1 in to V2 and D2 be an orientation of G such that
82 Twin signed domination numbers in directed graphs
A(D2) = {(vi, uj), (uj , vr) | i = 1, 2, r = 3, 4 and 1 6 j 6 4}. It is easy
to see that γ∗
s (D1) = 8 and γ∗
s (D2) = 4. Thus two distinct orientations
of a graph can have distinct twin domination numbers. Motivated by
this observation, we define the lower orientable twin signed domination
number dom∗
s(G) and the upper orientable twin signed domination number
Dom∗
s(G) of a graph G as follows:
dom∗
s(G) = min{γ∗
s (D) | D is an orientation of G},
and
Dom∗
s(G) = max{γ∗
s (D) | D is an orientation of G}.
Proposition 22. For any graph G of order n, γs(G) 6 dom∗
s(G).
Proof. Let D be an orientation of G such that γ∗
s (D) = dom∗
s(G), and let
f be a γ∗
s (D)-function. Then f(NG[v]) = f(N+
D [v]) + f(N−
D [v]) − f(v) for
each v ∈ V . Since f(N+
D [v]) > 1 and f(N−
D [v]) > 1, we have f(NG[v]) > 1
for each v ∈ V , and so f is a SDF of G. Therefore γs(G) 6 ω(f) = dom∗
s(G)
as desired.
Lemma 23. Let G be a graph of order n and v ∈ V (G). Let D be an
orientation of G and f be a γ∗
s (D)-function. If v is a support vertex or
deg(v) 6 3, then f(v) = 1.
Proof. If v is a support vertex and u is a leaf adjacent to v, then it
follows from f(N+[u]) > 1 and f(N−[u]) > 1 that f(v) = 1. Assume that
deg(v) 6 3. Then deg+
D(v) 6 1 or deg−
D(v) 6 1. Since f(N+[v]) > 1 and
f(N−[v]) > 1, we deduce that f(v) = 1.
Proposition 24. Let G be a graph of order n. Then dom∗
s(G) = n if
and only if every vertex of G either is a support vertex or has degree at
most 3.
Proof. The sufficiency follows from Lemma 23. To prove the necessity,
assume that dom∗
s(G) = n and assume, to the contrary, that there exists
a vertex v ∈ V (G) such that v is not a support vertex and deg(v) > 4. Let
t be the maximum number of disjoint pairs ui, wi in N(v) such that the
subgraph induced by {v, ui, wi} is a triangle. Assume that r = deg(v)−2t
and N(v) \ {ui, wi : 1 6 i 6 t} = {z1, z2, . . . , zr} if r > 0. Since v is
not a support vertex, N(zi) \ {v} 6= ∅ for each 1 6 i 6 r. Suppose that
xi ∈ N(zi) \ {v} for 1 6 i 6 r. If t = 0, then let D be an orientation of G
such that
{(v, zi), (zj , v), (xi, zi), (zj , xj) | 1 6 i 6 2 and 3 6 j 6 r} ⊆ A(D).
Atapour, Norouzian, Sheikholeslami, Volkmann 83
If t = 1, then let D be an orientation of G such that
{(v, u1),(w1, v),(w1, u1),(v, z1),(zj , v),(x1, z1),(zj , xj) : 26j6r}⊆A(D).
Finally, if t > 2, then let D be an orientation of G such that
{(v, ui), (wi, v), (wi, ui), (v, zj), (xj , zj) | 16 i6 t and 16j6r} ⊆ A(D).
It is easy to verify that the function f : V (D) → {−1, 1} that assigns
−1 to v and +1 to the remaining vertices, is a TSDF of D of weight
n − 2 in all cases, and so dom∗
s(G) 6 n − 2 which is a contradiction. This
completes the proof.
An immediate consequence of Proposition 24 now follows.
Corollary 25. For n > 3, dom∗
s(Pn) = dom∗
s(Cn) = n.
The wheel, Wn, is a graph with vertex set {v0, v1, . . . , vn} and edge
set {v0vi | 1 6 i 6 n} ∪ {v1v2, v2v3, . . . , vn−1vn, vnv1}. Next we determine
the lower orientable twin signed domination number of wheels.
Proposition 26. For n > 4, dom∗
s(Wn) = n − 1.
Proof. Let D be an arbitrary orientation of Wn and f be a γ∗
s (D)-function.
It follows from Lemma 23 that f(vi) = +1 for each i > 1. This implies
that dom∗
s(Wn) = ω(f) > n − 1. Now, let D be an orientation of Wn in
which (v1v2 . . . vn) is a directed cycle and {(v0, v1), (v0, v2), (vj , v0) : 3 6
j 6 n} ⊆ A(D). Then the function f : V (D) → {−1, 1} that assigns −1
to v0 and +1 to the remaining vertices, is a TSDF of D of weight n − 1
implying that dom∗
s(G) 6 n − 1. Thus dom∗
s(G) = n − 1 as desired.
We now proceed to determine the lower orientable twin domination
numbers of several classes of graphs include complete graphs and complete
bipartite graphs.
Lemma 27. For n > 3,
dom∗
s(Kn) >
{
3 if n is odd
4 if n is even.
Proof. If n = 3, 4, then the result follows from Lemma 23. Let n > 5.
By Proposition 24 and Observation 1, we have dom∗
s(Kn) 6 n − 2. Let
D be an orientation of Kn such that γ∗
s (D) = dom∗
s(Kn) and let f be a
γ∗
s (D)-function. Assume that v ∈ M . We consider two cases.
84 Twin signed domination numbers in directed graphs
Case 1: n is odd. Since f(N+[v]) > 1 and f(N−[v]) > 1 and since
N+(v)∪N−(v) is a partition of V (Kn)\{v}, we deduce that dom∗
s(Kn) =
ω(f) = f(N+[v]) + f(N−[v]) − f(v) > 3.
Case 2: n is even. Since n−1 is odd and since N+(v)∪N−(v) is a partition
of V (Kn) \ {v}, one of the d+(v) or d−(v) must be odd. Assume, without
loss of generality, that d+(v) is odd. Then we must have f(N+[v]) > 2
and f(N−[v]) > 1. Proceeding as above, we obtain dom∗
s(Kn) > 4.
Theorem 28. For n > 3,
dom∗
s(Kn) =
{
3 if n is odd
4 if n is even.
Proof. The result is trivial for n = 3, 4, so assume n > 5. Let
V (Kn) =
{
ui, vi, wj | 1 6 i 6 ⌈n
2
⌉ − 2 and 2⌈n
2
⌉ − 3 6 j 6 n
}
and let D be an orientation of Kn such that
A(D) =
{
(uk, ul), (uk, vl), (vk, vl), (vr, us) | 1 6 k < l 6 ⌈n
2
⌉ − 2
and 1 6 r 6 s 6 ⌈n
2
⌉ − 2
}
∪
{
(ui, wj), (vi, wj), (w2⌈ n
2
⌉−3, ui), (w2⌈ n
2
⌉−3, vi) | 1 6 i 6 ⌈n
2
⌉ − 2
and 2⌈n
2
⌉ − 2 6 j 6 n
}
∪
{
(wk, wl) | 2⌈n
2
⌉ − 3 6 k < l 6 n
}
.
It is easy to see that the function f : V (D) → {−1, +1} defined by
f(ui) = −1 for 1 6 i 6 ⌈n
2 ⌉ − 2 and f(x) = +1 otherwise, is a TSDF of D
of weight 3 when n is odd and weight 4 when n is even. This implies that
dom∗
s(Kn) 6 ω(f) =
{
3 if n is odd
4 if n is even.
Now the result follows from Lemma 27.
Let m 6 n and Km,n be the bipartite graph with bipartite sets V1, V2
such that |V1| = m and |V2| = n.
Atapour, Norouzian, Sheikholeslami, Volkmann 85
Lemma 29. Let D be an orientation of Km,n with n > m > 4. If f is a
TSDF of D such that Vi ∩ Mf 6= ∅ for i = 1, 2, then
ω(f) >
8 if n and m are both even
9 if n and m have different parity
10 if n and m are both odd .
Proof. Let u ∈ V1 ∩ Mf and v ∈ V2 ∩ Mf . We consider three cases.
Case 1: m and n are both even. Since f(N+[u]) > 1 and f(N−[u]) > 1,
we must have
|N+(u) ∩ Pf ∩ V2| > |N+(u) ∩ Mf ∩ V2| + 2
and
|N−(u) ∩ Pf ∩ V2| > |N−(u) ∩ Mf ∩ V2| + 2.
Since V2 = N+(u) ∪ N−(u), we deduce that
|V2 ∩ Pf | > |V2 ∩ Mf | + 4. (3)
Similarly, we have
|V1 ∩ Pf | > |V1 ∩ Mf | + 4. (4)
Adding (3) and (4), we obtain |P | > |M |+8 and so ω(f) = |Pf |−|Mf | > 8
as desired.
Case 2: m and n have different parity. Assume, without loss of generality,
that m is even and n is odd. Since d+(u) + d−(u) = n is odd, we may
assume that d+(u) is odd. It follows that f(N+[u]) > 2 and hence
|N+(u) ∩ Pf ∩ V2| > |N+(u) ∩ Mf ∩ V2| + 3.
Using an argument similar to that described in Case 1, we obtain ω(f) =
|Pf | − |Mf | > 9.
Case 3: m and n are both odd. Since d+(u) + d−(u) = n and d+(v) +
d−(v) = m are both odd, we may assume, without loss of generality, that
d+(u) and d+(v) are both odd. As Cases 1, 2, we have
|N+(u) ∩ Pf ∩ V2| > |N+(u) ∩ Mf ∩ V2| + 3
|N−(u) ∩ Pf ∩ V2| > |N−(u) ∩ Mf ∩ V2| + 2
|N+(v) ∩ Pf ∩ V1| > |N+(v) ∩ Mf ∩ V1| + 3
|N−(v) ∩ Pf ∩ V1| > |N−(v) ∩ Mf ∩ V1| + 2.
Summing the above inequalities, we deduce that |P | > |M | + 10 and so
ω(f) > 10 as desired.
86 Twin signed domination numbers in directed graphs
Lemma 30. Let D be an orientation of Km,n and f be a TSDF of D.
If V1 ∩ Mf = ∅, then
ω(f) >
{
m if n is even
m + 1 if n is odd
Proof. Let u ∈ V1. If n is even, then it follows from f(N+[u]) > 1 and
f(N−[u]) > 1 that |N+(u)∩Pf ∩V2| > |N+(u)∩Mf | and |N−(u)∩Pf | >
|N−(u) ∩ Mf ∩ V2|. This implies that |V2 ∩ Pf | > |V2 ∩ Mf | and hence
ω(f) = |Pf | − |Mf | = |V1| + |V2 ∩ Pf | − |V2 ∩ Mf | > |V1| = m.
Assume that n is odd. Since d+(u)+d−(u) = n is odd, we may assume,
without loss of generality, that d+(u) is odd. This implies that f(N+[u])>2.
As above we have |N+(u) ∩ Pf ∩ V2| > |N+(u) ∩ Mf ∩ V2| + 1 and
|N−(u)∩Pf | > |N−(u)∩Mf ∩V2| implying that |V2 ∩Pf | > |V2 ∩Mf |+1.
It follows that ω(f) = |Pf | − |Mf | = |V1| + |V2 ∩ P | − |V2 ∩ Mf | > m + 1
as desired.
The next result is an immediate consequence of Lemmas 29 and 30.
Corollary 31. For 4 6 m 6 n,
dom∗
s(Km,n) >
min{m, 8} if n and m are both even
min{m + 1, 9} if n is odd and m is even
min{m, 9} if m is odd and n is even
min{m + 1, 10} if n and m are both odd .
Theorem 32. For 4 6 m 6 n,
dom∗
s(Km,n) =
min{m, 8} if n and m are both even
min{m + 1, 9} if n is odd and m is even
min{m, 9} if m is odd and n is even
min{m + 1, 10} if n and m are both odd .
Proof. Let V1 = {u1, u2, . . . , um} and V2 = {v1, v2, . . . , vn} be the partite
sets of Km,n. We consider four cases.
Case 1: assume that m and n are both even. First let m 6 6. Let D be
an orientation of Km,n such that
A(D) = {(ui, vj), (vj , us) | 1 6 i 6
m
2
, 1 6 j 6 n and
m
2
+ 1 6 s 6 m}.
Atapour, Norouzian, Sheikholeslami, Volkmann 87
Define f : V (G) → {−1, +1} by f(x) = +1 for x ∈ V1 ∪ {v1, . . . , v n
2
} and
f(x) = −1 otherwise. It is easy to see that f is an TSDF of D of weight
m and so dom∗
s(Km,n) 6 m. Let now m > 8 and let D be an orientation
of Km,n such that
A(D) = {(ui, vj), (ur, vs), (vl, ut) | i, j, t 6∈ {1, 2},
1 6 s 6 n and r, l ∈ {1, 2}}.
(5)
It is easy to verify that the function f : V (G) → {−1, +1} defined
by f(x) = +1 for x ∈ {u1, . . . , u m
2
+2} ∪ {v1, . . . , v n
2
+2} and f(x) = −1
otherwise, is a TSDF of D of weight 8 and so dom∗
s(Km,n) 6 8.
Case 2: assume that m is even and n is odd. If m 6 6, then orient the
edges of Km,n such that the resulting digraph has the arc set
A(D) = {(ui, vj), (vj , us) | 1 6 i 6
m
2
, 1 6 j 6 n,
m
2
+ 1 6 s 6 m}.
It is easy to see that the function f : V (G) → {−1, +1} defined by f(x) =
+1 for x ∈ V1 ∪ {v1, . . . , v n+1
2
} and f(x) = −1 otherwise, is an TSDF of D
of weight m and so dom∗
s(Km,n) 6 m+1. Let now m > 8. Assume that D
is an orientation of Km,n such that (5) holds. Define f : V (G) → {−1, +1}
by f(x) = +1 for x ∈ {u1, . . . , u m
2
+2} ∪ {v1, . . . , v n+1
2
+2} and f(x) = −1
otherwise. It is easy to verify that f is a TSDF of D of weight 9 and so
dom∗
s(Km,n) 6 9.
Case 3: assume that m is odd and n is even. If m 6 7, then let D be an
orientation of Km,n such that
A(D) = {(ui, vj), (vj , us) | 1 6 i 6
m + 1
2
, 1 6 j 6 n,
m + 1
2
+16s6m},
and define f : V (G) → {−1, +1} by f(x) = +1 for x ∈ V1 ∪ {v1, . . . , v n
2
}
and f(x) = −1 otherwise. It is easy to see that f is a TSDF of D of weight
m and so dom∗
s(Km,n) 6 m. Let now m > 9 and let D be an orientation
of Km,n such that (5) holds. Define f : V (G) → {−1, +1} by f(x) = +1
for x ∈ {u1, . . . , u m+1
2
+2} ∪ {v1, . . . , v n
2
+2} and f(x) = −1 otherwise.
Obviously, f is a TSDF of D of weight 9 implying that dom∗
s(Km,n) 6 9.
Case 4: assume that m and n are both odd. If m 6 7, then orient the
edges of Km,n such that the resulting digraph has the arc set
A(D) = {(ui, vj), (vj , us) | 1 6 i 6
m + 1
2
, 16j6n,
m + 1
2
+ 16s6m}.
88 Twin signed domination numbers in directed graphs
It is easy to see that the function f : V (G) → {−1, +1} defined by
f(x) = +1 for x ∈ V1 ∪ {v1, . . . , v n+1
2
} and f(x) = −1 otherwise, is
a TSDF of D of weight m + 1 and so dom∗
s(Km,n) 6 m + 1. Let now
m > 9 and let D be an orientation of Km,n such that
A(D) = {(ui, vj), (vr, us), (vl, ut) | i, j, t 6∈ {1, 2}, 16s6n, r, l∈{1, 2}}.
Define f : V (G) → {−1, +1} by f(x) = +1 for x ∈ {u1, . . . , u m+1
2
+2} ∪
{v1, . . . , v n+1
2
+2} and f(x) = −1 otherwise. It is easy to see that f is a
TSDF of D of weight 10 and so dom∗
s(Km,n) 6 10.
Now the result follows by Corollary 31.
References
[1] S. Arumugam, K. Ebadi and L. Sathikala, Twin domination and twin irredundance
in digraphs, Appl. Anal. Discrete Math. 7 (2013), 275–284.
[2] M. Atapour, R. Hajypory, S.M. Sheikholeslami and L. Volkmann, The signed
k-domination number of directed graphs, Cent. Eur. J. Math. 8 (2010), 1048-1057.
[3] G. Chartrand, P. Dankelmann, M. Schultz and H.C. Swart, Twin domination in
digraphs, Ars Combin. 67 (2003), 105–114.
[4] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and P.J. Slater, Signed domination in
graphs. In Y. Alavi and A.J. Schwenk, editors, Graph Theory, Combinatorics, and
Applications, Proc. 7th Internat. Conf. Combinatorics, Graph Theory, Applications,
volume 1, pages 311-322. John Wiley and Sons, Inc., 1995.
[5] M.A. Henning and P.J. Slater, Inequalities relating domination parameters in cubic
graphs, Discrete Math. 158 (1996), 87-98.
[6] H. Karami, A. Khodkar and S.M. Sheikholeslami, Lower bounds on signed domina-
tion number of a digraph, Discrete Math. 309 (2009), 2567–2570.
[7] C. Wang The signed k-domination numbers in graphs, Ars Combin. 106 (2012),
205-211.
[8] D.B. West, Introduction to Graph Theory, Prentice-Hall, Inc, 2000.
[9] B. Zelinka, Signed domination numbers of directed graphs, Czechoslovak Math. J.
55 (2005), 479–482.
[10] Z. Zhang, B. Xu, Y. Li and L. Liu, A note on the lower bounds of signed domination
number of a graph, Discrete Math. 195 (1999), 295–298.
Contact information
M. Atapour Department of Mathematics
University of Bonab
Bonab, I.R. Iran
E-Mail(s): m.atapour@bonabu.ac.ir
Atapour, Norouzian, Sheikholeslami, Volkmann 89
S. Norouzian,
S. M. Sheikholeslami
Department of Mathematics
Azarbaijan Shahid Madani University
Tabriz, I.R. Iran
E-Mail(s): s.m.sheikholeslami
@azaruniv.edu
L. Volkmann RWTH Aachen University
52056 Aachen, Germany
E-Mail(s): volkm@math2.rwth-aachen.de
Received by the editors: 21.09.2015
and in final form 10.11.2015.
|