The Roman bondage number of a digraph

  • Seyed Mahmoud Sheikholeslami
  • Nasrin Dehgardi
  • Lutz Volkmann
  • Dirk Meierling
Keywords: Roman dominating function, Roman domination number, Roman bondage number, digraph

Abstract

Let $D=(V,A)$ be a finite and simple digraph. A  Roman dominating function on $D$ is a labeling $f:V (D)\rightarrow \{0, 1, 2\}$ such that every vertex with label 0 has an in-neighbor with label 2. The weight of an RDF $f$ is the value $\omega(f)=\sum_{v\in V}f (v)$. The minimum weight of a Roman dominating function on a digraph $D$ is called the Roman domination number, denoted by $\gamma_{R}(D)$. The Roman bondage number $b_{R}(D)$ of a digraph $D$ with maximum out-degree at least two is the minimum cardinality of all sets $A'\subseteq A$ for which $\gamma_{R}(D-A')>\gamma_R(D)$. In this paper, we initiate the study of the Roman bondage number of a digraph. We determine the Roman bondage number in several classes of digraphs and give some sharp bounds.

Author Biographies

Seyed Mahmoud Sheikholeslami
Department ofMathematics, Azarbaijan ShahidMadani University, Tabriz, I.R. Iran.
Nasrin Dehgardi
Department ofMathematics and Computer Science, Sirjan University of Technology, Sirjan, I.R. Iran.
Lutz Volkmann
Lehrstuhl II fürMathematik, RWTH Aachen University, 52056 Aachen, Germany.
Dirk Meierling
Lehrstuhl II fürMathematik, RWTH Aachen University, 52056 Aachen, Germany. 432 N. DEHGARDI, D.MEIERLING, S.M. SHEIKHOLESLAMI AND L. VOLKMANN

References

J. Amjadi, N. Mohammadi, S. M. Sheikholeslami and L. Volkmann,The $k$-rainbow bondage number of a digraph, Discuss. Math. Graph Theory, 35(2015), 261--270.

A. Bahremandpour, F.-T. Hu, S. M. Sheikholeslami and J.-M. Xu, On the Roman bondage number of a graph}, Discrete Math. Algorithms Appl. 5(2013), 1350001 (15 pages)

K. Carlson and M. Develin, On the bondage number of planar and directed graphs}, Discrete Math., 306(2006), 820--826.

E.W. Chambers, B. Kinnersley, N. Prince and D. B. West, Extremal problems for Roman domination, SIAM J. Discrete Math., 23(2009), 1575--1586.

E. J. Cockayne, P. M. Dreyer Jr., S. M. Hedetniemi, and S.T. Hedetniemi,On Roman domination in graphs, Discrete Math., 278(2004),11--22.

N. Dehgardi, D. Meierling, S. M. Sheikholeslami and L. Volkmann, Roman reinforcement numbers of digraphs, J. Combin. Math. Combin. Comput., 89(2014) 53--64.

N. Dehgardi, S. M. Sheikholeslami and L. Volkmann, On the Roman $k$-bondage number of a graph, AKCE Int. J. Graphs Comb., 8(2011), 169--180.

O. Favaron, H. Karami and S. M. Sheikholeslami, On the Roman domination number in graphs}, Discrete Math., 309(2009), 3447--3451.

T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.

J. Huang and J.-M. Xu, The bondage numbers of extended de Bruijn and Kautz digraphs, Comput. Math. Appl., 51(2006), 1137--1147.

J. Huang and J.-M. Xu,The bondage numbers and efficient dominations of vertex-transitive graphs, Discrete Math., 308(2008), 571--582.

J. Huang and J.-M. Xu, The total domination and total bondage numbers of extended de Bruijn and Kautz digraphs, Comput. Math. Appl., 53(2007), 1206--1213.

N. J. Rad and L. Volkmann, Roman bondage in graphs, Discuss. Math. Graph Theory, 31(2011), 763--773.

N. J. Rad and L. Volkmann, On the Roman bondage number of planar graphs, Graphs Combin., 27(2011), 531--538.

C.S. Revelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly, 107(2000), 585--594.

E. Shan and L. Kang, Bondage number in oriented graphs, Ars Combin., 84(2007), 319--331.

S. M. Sheikholeslami and L. Volkmann, The Roman domination number of a digraph, Acta Univ. Apulensis Math. Inform., 27(2011), 77--86.

I. Stewart, Defend the Roman Empire, Sci. Amer., 281(1999), 136--139.

J.-M. Xu, On bondage numbers of graphs: a survey with some comments, Int. J. Combin. Volume 2013, Article ID 595210, 34 pages.

D. B. West, Introduction to Graph Theory, Prentice-Hall, Inc, 2000.

Published
2016-12-30
How to Cite
Sheikholeslami, S. M., Dehgardi, N., Volkmann, L., & Meierling, D. (2016). The Roman bondage number of a digraph. Tamkang Journal of Mathematics, 47(4), 421-431. https://doi.org/10.5556/j.tkjm.47.2016.2100
Section
Papers

Most read articles by the same author(s)