Perfect Roman domination in middle graphs

Kijung Kim

doi:10.47443/dml.2021.0066

Author(s)

Kijung Kim Department of Mathematics, Pusan National University, Busan 46241, Republic of Korea

Abstract

The middle graph M (G) of a graph G is the graph obtained by subdividing each edge of G exactly once and joining all these newly introduced vertices of adjacent edges of G. A perfect Roman dominating function on a graph G is a function f : V (G) ! f0; 1; 2g satisfying the condition that every vertex v with f (v) = 0 is adjacent to exactly one vertex u for which f (u) = 2. The weight of a perfect Roman dominating function f is the sum of weights of vertices. The perfect Roman domination number is the minimum weight of a perfect Roman dominating function on G. In this paper, a characterization of middle graphs with equal Roman domination and perfect Roman domination numbers is given.

Publication Details

Page(s) 94-97

DOI 10.47443/dml.2021.0066

Published Journal: Discrete Mathematics Letters, Volume: 7, Issue: 0, Year: 2021

Request the full text from PASTIC

Keywords

perfect Roman domination, perfect domination, Roman domination, Middle Graph

References

Basilio L. A.,Simon J. C.,Cayetano O. R. .2020 .The differential on graph operator Q(G. Symmetry, 12 : 751.

Bondy J. A.,Murty U. S. R. .2008 .. , : .

Cockayne E. J.,Dreyer P. A.,Hedetniemi S. M.,Hedetniemi S. T. .2004 .. , 278 : 11-22.

Darkooti M.,Alhevaz A.,Rahimi S.,Rahbani H. .2019 .On perfect Roman domination number in trees: complexity and bounds. J. Comb. Optim, 38 : 712-720.

Hamada T.,I. Yoshimura T. .1976 .Traversability and connectivity of the middle graph of a graph. Discrete Math, 14 : 247-255.

Henning M. A.,Klostermeyer W. F.,G. W. F. .2018 .MacGillivray, Perfect Roman domination in trees. Discrete Appl. Math, 236 : 235-245.

Kazemnejad F.,Pahlavsay B.,Torielli M. .2020 .Domination number of middle graphs. , : .

Kim K. . .Middle domination and 2-independence in trees. Discrete Math. Algorithms Appl, : .

Kim K. . .-rainbow and Roman domination numbers in middle graphs. , : .

C. S. ReVelle .2000 .Defendens imperium Romanum: a classical problem in military strategy. Amer. Math. Monthly, 107 : 585-594.

I. Stewart .1999 .. Sci. Amer, 281 : 136-139.

Yue J. . .. J. Song, Note on perfect Roman domination number of graphs, Appl. Math. Comput, 364(2020) : 124685.