Upper bounds on Roman domination numbers of graphs

Chun Hung Liu; Gerard Jennhwa Chang

doi:10.1016/j.disc.2011.12.021

Upper bounds on Roman domination numbers of graphs

Chun Hung Liu, Gerard Jennhwa Chang

Mathematics

Research output: Contribution to journal › Article › peer-review

42 Scopus citations

Abstract

A Roman dominating function of a graph G is a function fV(G)→0,1,2 such that whenever f(v)=0 there exists a vertex u adjacent to v with f(u)=2. The weight of f is w(f)=∑ _v∈V(G)f(v). The Roman domination number ^γR(G) of G is the minimum weight of a Roman dominating function of G. This paper establishes a sharp upper bound on the Roman domination numbers of graphs with minimum degree at least 3. An upper bound on the Roman domination numbers of connected, big-claw-free and big-net-free graphs is also given.

Original language	English (US)
Pages (from-to)	1386-1391
Number of pages	6
Journal	Discrete Mathematics
Volume	312
Issue number	7
DOIs	https://doi.org/10.1016/j.disc.2011.12.021
State	Published - Apr 6 2012

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Cocomparability graph
Domination
Forbidden subgraph
Minimum degree
Roman domination

Access to Document

10.1016/j.disc.2011.12.021

Cite this

@article{42b1bd82b1194bfeb90bae187e429d7c,

title = "Upper bounds on Roman domination numbers of graphs",

abstract = "A Roman dominating function of a graph G is a function fV(G)→0,1,2 such that whenever f(v)=0 there exists a vertex u adjacent to v with f(u)=2. The weight of f is w(f)=∑ v∈V(G)f(v). The Roman domination number γR(G) of G is the minimum weight of a Roman dominating function of G. This paper establishes a sharp upper bound on the Roman domination numbers of graphs with minimum degree at least 3. An upper bound on the Roman domination numbers of connected, big-claw-free and big-net-free graphs is also given.",

keywords = "Cocomparability graph, Domination, Forbidden subgraph, Minimum degree, Roman domination",

author = "Liu, {Chun Hung} and Chang, {Gerard Jennhwa}",

note = "Funding Information: Supported in part by the National Science Council under grant NSC99-2923-M-002-007-MY3 . ",

year = "2012",

month = apr,

day = "6",

doi = "10.1016/j.disc.2011.12.021",

language = "English (US)",

volume = "312",

pages = "1386--1391",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "7",

}

TY - JOUR

T1 - Upper bounds on Roman domination numbers of graphs

AU - Liu, Chun Hung

AU - Chang, Gerard Jennhwa

N1 - Funding Information: Supported in part by the National Science Council under grant NSC99-2923-M-002-007-MY3 .

PY - 2012/4/6

Y1 - 2012/4/6

N2 - A Roman dominating function of a graph G is a function fV(G)→0,1,2 such that whenever f(v)=0 there exists a vertex u adjacent to v with f(u)=2. The weight of f is w(f)=∑ v∈V(G)f(v). The Roman domination number γR(G) of G is the minimum weight of a Roman dominating function of G. This paper establishes a sharp upper bound on the Roman domination numbers of graphs with minimum degree at least 3. An upper bound on the Roman domination numbers of connected, big-claw-free and big-net-free graphs is also given.

AB - A Roman dominating function of a graph G is a function fV(G)→0,1,2 such that whenever f(v)=0 there exists a vertex u adjacent to v with f(u)=2. The weight of f is w(f)=∑ v∈V(G)f(v). The Roman domination number γR(G) of G is the minimum weight of a Roman dominating function of G. This paper establishes a sharp upper bound on the Roman domination numbers of graphs with minimum degree at least 3. An upper bound on the Roman domination numbers of connected, big-claw-free and big-net-free graphs is also given.

KW - Cocomparability graph

KW - Domination

KW - Forbidden subgraph

KW - Minimum degree

KW - Roman domination

UR - http://www.scopus.com/inward/record.url?scp=84862817100&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862817100&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2011.12.021

DO - 10.1016/j.disc.2011.12.021

M3 - Article

AN - SCOPUS:84862817100

SN - 0012-365X

VL - 312

SP - 1386

EP - 1391

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 7

ER -

Upper bounds on Roman domination numbers of graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this