Progress on Roman and Weakly Connected Roman Graphs
Open Access
- 5 August 2021
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 9 (16) , 1846
Abstract
A graph G for which is the Roman graph, and if , then G is the weakly connected Roman graph. In this paper, we show that the decision problem of whether a bipartite graph is Roman is a co-NP-hard problem. Next, we prove similar results for weakly connected Roman graphs. We also study Roman trees improving the result of M.A. Henning’s A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002). Moreover, we give a characterization of weakly connected Roman trees.
Keywords
Funding Information
- Universidad Nacional Autónoma de México (UNAM-PAPIIT IN-117219)
This publication has 9 references indexed in Scilit:
- Weakly connected Roman domination in graphsDiscrete Applied Mathematics, 2019
- Roman domination in regular graphsDiscrete Mathematics, 2009
- On weakly connected domination in graphs IIDiscrete Mathematics, 2005
- Roman domination in graphsDiscrete Mathematics, 2004
- Defending the Roman Empire—A new strategyDiscrete Mathematics, 2003
- A characterization of Roman treesDiscussiones Mathematicae Graph Theory, 2002
- Defend the Roman Empire!Scientific American, 1999
- Paired-domination in graphsNetworks, 1998
- On weakly connected domination in graphsDiscrete Mathematics, 1997