Roman Bondage Numbers of Some Graphs

Abstract

A Roman dominating function on a graph $G=(V,E)$ is a function $f:V\to \{0,1,2\}$ satisfying the condition that every vertex $u$ with $f(u)=0$ is adjacent to at least one vertex $v$ with $f(v)=2$. The weight of a Roman dominating function is the value $f(G)={\sum }_{u\in V}f(u)$. The Roman domination number of $G$ is the minimum weight of a Roman dominating function on $G$. The Roman bondage number of a nonempty graph $G$ is the minimum number of edges whose removal results in a graph with the Roman domination number larger than that of $G$. This paper determines the exact value of the Roman bondage numbers of two classes of graphs, complete $t$-partite graphs and $(n-3)$-regular graphs with order $n$ for any $n\ge 5$.

10 pages

Cited by in corpus (2)

• On Bondage Numbers of Graphs -- a survey with some comments
• On the Roman bondage number of a graph