Search
Abstract
A graph G for which γR(G)=2γ(G) is the Roman graph, and if γwcR(G)=2γwc(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.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Cite as
Full text
download paper
downloaded 56 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.3390/math9161846
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
Mathematics
no. 9,
ISSN: 2227-7390 - Language:
- English
- Publication year:
- 2021
- Bibliographic description:
- Raczek J., Zuazua R.: Progress on Roman and Weakly Connected Roman Graphs// Mathematics -Vol. 9,iss. 16 (2021), s.1846-
- DOI:
- Digital Object Identifier (open in new tab) 10.3390/math9161846
- Sources of funding:
-
- Drugi autor otrzymała wsparcie na koszty podróży z grantu UNAM-PAPIIT IN-117219.
- Verified by:
- Gdańsk University of Technology
seen 114 times
Recommended for you
On the connected and weakly convex domination numbers
- M. Lemańska,
- M. Dettlaff,
- D. Osula
- + 1 authors
2020
Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph
- M. Lemańska,
- J. A. RODRíGUEZ-VELáZQUEZ,
- R. Trujillo-Rasua
2017