数学外文的中文翻译.docx

SIAM J. DISCRETE MATH.Vol. 26, No. 1, pp. 193–205ROMAN DOMINATION ON 2-CONNECTED GRAPHS?CHUN-HUNG LIU?AND GERARD J. CHANG?Abstract. A Roman dominating function of a graph G is a function f: V (G) → {0, 1, 2} such that whenever f(v) = 0, there exists a vertex u adjacent to v such that f(u) = 2. The weight of f is w(f) = . The Roman domination number of G is the minimum weight of a Roman dominating function of G Chambers,Kinnersley, Prince, and West [SIAM J. Discrete Math.,23 (2009), pp. 1575–1586] conjectured that ≤ [2n/3] for any 2-connected graph G of n vertices.This paper gives counterexamples to the conjecture and proves that≤ max{[2n/3], 23n/34}for any 2-connected graph G of n vertices. We also characterize 2-connected graphs G for which = 23n/34 when 23n/34 [2n/3].Key words. domination, Roman domination, 2-connected graphAMS. subject classifications. 05C69, 05C35DOI. 10.1137/0807330851. Introduction. Articles by ReVelle [14, 15] in the Johns Hopkins Magazine suggested a new variation of domination called Roman domination; see also [16] for an integer programming formulation of the problem. Since then, there have been several articles on Roman domination and its variations [1, 2, 3, 4, 5, 7, 8, 9, 10,11, 13, 17, 18, 19]. Emperor Constantine imposed the requirement that an army or legion could be sent from its home to defend a neighboring location only if there was a second army which would stay and protect the home. Thus, there are two types of armies, stationary and traveling. Each vertex (city) that has no army must have a neighboring vertex with a traveling army. Stationary armies then dominate their own vertices; a vertex with two armies is dominated by its stationary army, and its open neighborhood is dominated by the traveling army. In this paper, we consider (simple) graphs and loopless multigraphs G with vert ex set V (G) and edge set E(G). The degree of a vertex v∈V (G) is the number of edges incident to v. Note that the number of neighbors of v may