Roman Bondage Number of a Graph

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

21 pages with 1 figures

Scientific paper

The Roman dominating function on a graph $G=(V,E)$ is a function $f: V\rightarrow\{0,1,2\}$ such that each vertex $x$ with $f(x)=0$ is adjacent to at least one vertex $y$ with $f(y)=2$. The value $f(G)=\sum\limits_{u\in V(G)} f(u)$ is called the weight of $f$. The Roman domination number $\gamma_{\rm R}(G)$ is defined as the minimum weight of all Roman dominating functions. This paper defines the Roman bondage number $b_{\rm R}(G)$ of a nonempty graph $G=(V,E)$ to be the cardinality among all sets of edges $B\subseteq E$ for which $\gamma_{\rm R}(G-B)>\gamma_{\rm R}(G)$. Some bounds are obtained for $b_{\rm R}(G)$, and the exact values are determined for several classes of graphs. Moreover, the decision problem for $b_{\rm R}(G)$ is proved to be NP-hard even for bipartite graphs.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Roman Bondage Number of a Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Roman Bondage Number of a Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Roman Bondage Number of a Graph will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-96208

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.