Progress on Roman and Weakly Connected Roman Graphs

Joanna Raczek and Rita Zuazua
Additional contact information
Joanna Raczek: Department of Algorithms and Systems Modelling, Faculty of Electronics, Telecommunications and Informatics, Gdańsk Tech, 80-233 Gdańsk, Poland
Rita Zuazua: Department of Mathematics, Faculty of Sciences, Universidad Nacional Autónoma de México, Mexico City 4510, Mexico

Mathematics, 2021, vol. 9, issue 16, 1-8

Abstract: A graph G for which ? R ( G ) = 2 ? ( G ) is the Roman graph , and if ? R w c ( G ) = 2 ? w c ( G ) , 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: Roman domination number; weakly connected Roman domination number; weakly connected Roman graphs; NP completeness (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/16/1846/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/16/1846/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:16:p:1846-:d:608755

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().