Progress on Roman and Weakly Connected Roman Graphs - Publication - MOST Wiedzy

Search

Progress on Roman and Weakly Connected Roman Graphs

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 4 times
Publication version
Accepted or Published Version
DOI:
Digital Object Identifier (open in new tab) 10.3390/math9161846
License
Creative Commons: CC-BY 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 12 times

Recommended for you

Meta Tags