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.
Authors
- dr inż. Joanna Raczek link open in new tab ,
- Rita Zuazua
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.3390/math9161846
- Category
- Publikacja w czasopiśmie
- Type
- artykuły w czasopismach
- Language
- angielski
- Publication year
- 2021
