Perfect Roman domination in trees

Michael A. Henning; William F. Klostermeyer; Gary MacGillivray

doi:10.1016/j.dam.2017.10.027

Perfect Roman domination in trees

Michael A. Henning
, William F. Klostermeyer
, Gary MacGillivray

Mathematics and Applied Mathematics

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

47 Citations (Scopus)

Abstract

A perfect Roman dominating function on a graph G is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u with f(u)=0 is adjacent to exactly one vertex v for which f(v)=2. The weight of a perfect Roman dominating function f is the sum of the weights of the vertices. The perfect Roman domination number of G, denoted γ_R^p(G), is the minimum weight of a perfect Roman dominating function in G. We show that if G is a tree on n≥3 vertices, then γ_R^p(G)≤[Formula presented]n, and we characterize the trees achieving equality in this bound.

Original language	English
Pages (from-to)	235-245
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	236
DOIs	https://doi.org/10.1016/j.dam.2017.10.027
Publication status	Published - 19 Feb 2018

Keywords

Dominating set
Perfect dominating set
Roman dominating function
Tree

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2017.10.027

Cite this

@article{fd33ff24bd214df4b9734a855106b0cb,

title = "Perfect Roman domination in trees",

abstract = "A perfect Roman dominating function on a graph G is a function f:V(G)→\{0,1,2\} satisfying the condition that every vertex u with f(u)=0 is adjacent to exactly one vertex v for which f(v)=2. The weight of a perfect Roman dominating function f is the sum of the weights of the vertices. The perfect Roman domination number of G, denoted γRp(G), is the minimum weight of a perfect Roman dominating function in G. We show that if G is a tree on n≥3 vertices, then γRp(G)≤[Formula presented]n, and we characterize the trees achieving equality in this bound.",

keywords = "Dominating set, Perfect dominating set, Roman dominating function, Tree",

author = "Henning, \{Michael A.\} and Klostermeyer, \{William F.\} and Gary MacGillivray",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2018",

month = feb,

day = "19",

doi = "10.1016/j.dam.2017.10.027",

language = "English",

volume = "236",

pages = "235--245",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Perfect Roman domination in trees

AU - Henning, Michael A.

AU - Klostermeyer, William F.

AU - MacGillivray, Gary

PY - 2018/2/19

Y1 - 2018/2/19

N2 - A perfect Roman dominating function on a graph G is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u with f(u)=0 is adjacent to exactly one vertex v for which f(v)=2. The weight of a perfect Roman dominating function f is the sum of the weights of the vertices. The perfect Roman domination number of G, denoted γRp(G), is the minimum weight of a perfect Roman dominating function in G. We show that if G is a tree on n≥3 vertices, then γRp(G)≤[Formula presented]n, and we characterize the trees achieving equality in this bound.

AB - A perfect Roman dominating function on a graph G is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u with f(u)=0 is adjacent to exactly one vertex v for which f(v)=2. The weight of a perfect Roman dominating function f is the sum of the weights of the vertices. The perfect Roman domination number of G, denoted γRp(G), is the minimum weight of a perfect Roman dominating function in G. We show that if G is a tree on n≥3 vertices, then γRp(G)≤[Formula presented]n, and we characterize the trees achieving equality in this bound.

KW - Dominating set

KW - Perfect dominating set

KW - Roman dominating function

KW - Tree

UR - https://www.scopus.com/pages/publications/85035085465

U2 - 10.1016/j.dam.2017.10.027

DO - 10.1016/j.dam.2017.10.027

M3 - Article

AN - SCOPUS:85035085465

SN - 0166-218X

VL - 236

SP - 235

EP - 245

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Perfect Roman domination in trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this