PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2011 | 31 | 4 | 763-773
Tytuł artykułu

Roman bondage in graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A Roman dominating function on a graph G is a function f:V(G) → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value $f(V(G)) = ∑_{u ∈ V(G)}f(u)$. The Roman domination number, $γ_R(G)$, of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage $b_R(G)$ of a graph G with maximum degree at least two to be the minimum cardinality of all sets E' ⊆ E(G) for which $γ_R(G -E') > γ_R(G)$. We determine the Roman bondage number in several classes of graphs and give some sharp bounds.
Słowa kluczowe
Wydawca
Rocznik
Tom
31
Numer
4
Strony
763-773
Opis fizyczny
Daty
wydano
2011
otrzymano
2010-06-14
poprawiono
2010-11-23
zaakceptowano
2010-11-23
Twórcy
  • Department of Mathematics, Shahrood University of Technology, Shahrood, Iran
  • School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran
  • Lehrstuhl II für Mathematik, RWTH Aachen University, Templergraben 55, D-52056 Aachen, Germany
Bibliografia
  • [1] D. Bauer, F. Harary, J. Nieminen and C.L. Suffel, Domination alteration sets in graphs, Discrete Math. 47 (1983) 153-161, doi: 10.1016/0012-365X(83)90085-7.
  • [2] E.J. Cockayne, P.M. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11-22, doi: 10.1016/j.disc.2003.06.004.
  • [3] J.E. Dunbar, T.W. Haynes, U. Teschner and L. Volkmann, Bondage, insensitivity, and reinforcement, in: T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998) 471-489.
  • [4] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, The bondage number of a graph, Discrete Math. 86 (1990) 47-57, doi: 10.1016/0012-365X(90)90348-L.
  • [5] B.L. Hartnell and D.F. Rall, Bounds on the bondage number of a graph, Discrete Math. 128 (1994) 173-177, doi: 10.1016/0012-365X(94)90111-2.
  • [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
  • [7] C.S. ReVelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer Math. Monthly 107 (2000) 585-594, doi: 10.2307/2589113.
  • [8] I. Stewart, Defend the Roman Empire!, Sci. Amer. 281 (1999) 136-139, doi: 10.1038/scientificamerican1299-136.
  • [9] U. Teschner, New results about the bondage number of a graph, Discrete Math. 171 (1997) 249-259, doi: 10.1016/S0012-365X(96)00007-6.
  • [10] D.B. West, Introduction to Graph Theory, (2nd edition) (Prentice Hall, USA, 2001).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1578
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.