Roman Domination over Some Graph Classes

Authors: Mathieu Liedloff Ton Kloks Jiping Liu ShengLung Peng

Publish Date: 2005/6/23

Volume: , Issue: , Pages: 103-114

PDF Link

Abstract

A Roman dominating function of a graph G = VE is a function f V → 012 such that every vertex x with fx = 0 is adjacent to at least one vertex y with fy = 2 The weight of a Roman dominating function is defined to be fV = ∑ x ∈ V fx and the minimum weight of a Roman dominating function on a graph G is called the Roman domination number of GIn this paper we answer an open problem mentioned in 2 by showing that the Roman domination number of an interval graph can be computed in linear time We also show that the Roman domination number of a cograph can be computed in linear time Besides we show that there are polynomial time algorithms for computing the Roman domination numbers of ATfree graphs and graphs with a doctopus

Keywords: