Upper bounds for the Roman bondage number of graphs on closed surfaces

機関リポジトリ 機関リポジトリ (HANDLE)

この論文をさがす

説明

Let G be a simple graph, and its vertex sets is denoted by V (G). A set D V (G) is the dominating set if every vertex not in D is adjacent to at least one vertex in D. The minimum cadinality of a dominatin set of G is the dominationg number (G). Clearly, for any spanning subgraph H of G, (H) (G). The bondage number of G, denoted by b(G), is the minimum cardinality of a set of edges B E(G) such that (G - B) > (G), where G - B is the graph with V (G - B) = V (G) and E(G - B) = E(G) B. A function f : V (G) {0, 1, 2} is a Roman dominating function if every vertex v for which f(v) = 0 is adjacent to at least one vertex u for which f(u) = 2. The weight of a Roman dominating function is the value v V (G) f(v). The Roman domination number of a graph G, denoted by R(G), is the minimum weight of a Roman dominating function of G. The Roman bondage number bR(G) of a graph G is the cardinality of a smallest set of edges B E(G) for which R(G-B) > R(G), where V (G - B) = V (G) and E(G - B) = E(G) B. In this paper, for a graph G on a closed surface M, we get an upper bound for the Roman bondage number bR(G) of G by Euler characteristic (M) of M.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ