Roman k-domination in graphs
1
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
Let k be a positive integer, and let G be a simple graph with vertex set V(G). A Roman k-dominating function on G is a function f:V(G)→{0,1,2} such that every vertex u for which f(u)=0 is adjacent to at least k vertices v_1,v_2,…,v_k with f(v_i)=2 for i=1,2,…,k. The weight of a Roman k-dominating function is the value f(V(G))=∑{u∈V(G)}f(u). The minimum weight of a Roman k-dominating function on a graph G is called the Roman k-domination number γ_{kR}(G) of G. Note that the Roman 1-domination number γ_{1R}(G) is the usual Roman domination number γ_R(G). In this paper, we investigate the properties of the Roman k-domination number. Some of our results extend these one given by Cockayne, Dreyer Jr., S. M. Hedetniemi, and S. T. Hedetniemi [2] in 2004 for the Roman domination number.
Abstract
Let k be a positive integer, and let G be a simple graph with vertex set V(G). A Roman k-dominating function on G is a function f:V(G)→{0,1,2} such that every vertex u for which f(u)=0 is adjacent to at least k vertices v_1,v_2,…,v_k with f(v_i)=2 for i=1,2,…,k. The weight of a Roman k-dominating function is the value f(V(G))=∑{u∈V(G)}f(u). The minimum weight of a Roman k-dominating function on a graph G is called the Roman k-domination number γ_{kR}(G) of G. Note that the Roman 1-domination number γ_{1R}(G) is the usual Roman domination number γ_R(G). In this paper, we investigate the properties of the Roman k-domination number. Some of our results extend these one given by Cockayne, Dreyer Jr., S. M. Hedetniemi, and S. T. Hedetniemi [2] in 2004 for the Roman domination number.
참고문헌 (10)
- E. W. Chambers, "Extremal problems for Roman domination", ~ (2007)
- E. J. Cockayne, "Roman domination in graphs", Discrete Math., 278(1), pp.11~22 (2004)
- E. J. Cockayne, "Protection of a graph", Util. Math., 67, pp.19~32 (2005)
- J. F. Fink, "Jacobson, n-domination in graphs, Graph theory with applications to algorithms and computer science", pp.283~300 (1985), Wiley-Intersci. Publ.
- J. F. Fink, "On n-domination, n-dependence and forbidden subgraphs, Graph theory with applications to algorithms and computer science", pp.301~311 (1985), Wiley-Intersci. Publ.
- T. W. Haynes, "Fundamentals of Domination in Graphs", Monographs and Textbooks in Pure and Applied Mathematics, 208 (1998), Marcel Dekker, Inc.
- T. W. Haynes, "Domination in Graphs: Advanced Topics, Monographs and Textbooks in Pure and Applied Mathematics" (1998), Marcel Dekker, Inc.
- C. S. ReVelle, "Defendens imperium romanum: a classical problem in military strategy", Amer. Math. Monthly, 107(7), pp.585~594 (2000)
- I. Steward, "Defend the Roman Empire", Sci. Amer., 281, pp.136~139 (1999)
- "Graphen an allen Ecken und Kanten, RWTH Aachen"[URL]