Roman domination excellent graphs: trees

A Roman dominating function (RDF) on a graph \(G = (V, E)\) is a labeling \(f : V \rightarrow \{0, 1, 2\}\) such that every vertex with label \(0\) has a neighbor with label \(2\). The weight of \(f\) is the value \(f(V) = \Sigma_{v\in V} f(v)\). The Roman domination number, \(\gamma_R(G)\), of \(G\...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-10
Main Author: Samodivkin, Vladimir
Format: Article
Language:English
Subjects:
Mathematical functions
Minimum weight
Trees (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A Roman dominating function (RDF) on a graph \(G = (V, E)\) is a labeling \(f : V \rightarrow \{0, 1, 2\}\) such that every vertex with label \(0\) has a neighbor with label \(2\). The weight of \(f\) is the value \(f(V) = \Sigma_{v\in V} f(v)\). The Roman domination number, \(\gamma_R(G)\), of \(G\) is the minimum weight of an RDF on \(G\). An RDF of minimum weight is called a \(\gamma_R\)-function. A graph G is said to be \(\gamma_R\)-excellent if for each vertex \(x \in V\) there is a \(\gamma_R\)-function \(h_x\) on \(G\) with \(h_x(x) \not = 0\). We present a constructive characterization of \(\gamma_R\)-excellent trees using labelings. A graph \(G\) is said to be in class \(UVR\) if \(\gamma(G-v) = \gamma (G)\) for each \(v \in V\), where \(\gamma(G)\) is the domination number of \(G\). We show that each tree in \(UVR\) is \(\gamma_R\)-excellent.
ISSN:2331-8422