On maximal Roman domination in graphs: complexity and algorithms Article Swipe

View

Zehui Shao , Yonghao Song , Qiyun Liu , Zhixing Duan , Huiqin Jiang ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.1051/ro/2024038

For a simple undirected connected graph G = ( V, E ), a maximal Roman dominating function (MRDF) of G is a function f : V ( G ) → {0, 1, 2} with the following properties: ( i ) For every vertex v ∈ { v ∈ V | f ( v ) = 0}, there exists a vertex u ∈ N ( v ) such that f ( u ) = 2. ( ii ) The set { v ∈ V|f ( v ) = 0} is not a dominating set of G ; In other words, there exists a vertex v ∈ { v ∈ V | f ( v ) ≠ 0} such that N ( v ) ∩ { u ∈ V | f ( u ) = 0} ∅ . The weight of an MRDF of G is the sum of its function values over all vertices, denoted as f ( G ) = ∑ v ∈ V ( G ) f ( v ), and the maximal Roman domination number of G , denoted by γ mR ( G ), is the minimum weight of an MRDF of G . In this paper, we establish some bounds of the maximal Roman domination number of graphs. Additionally, we develop an integer linear programming formulation to compute the maximal Roman domination number of any graph. Furthermore, we prove that maximal Roman domination problem (MRD) is NP-complete even restricted to star convex bipartite graphs and chordal bipartite graphs. Lastly, we show the maximal Roman domination number of threshold graphs, trees, and block graphs can be computed in linear time.

Related Topics

Concepts

Computer science Algorithm Combinatorics Mathematics

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.1051/ro/2024038
OA Status: diamond
References: 16
Related Works: 10
OpenAlex ID: https://openalex.org/W4391772559

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4391772559

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1051/ro/2024038

Digital Object Identifier
Title: On maximal Roman domination in graphs: complexity and algorithms

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-02-13

Full publication date if available
Authors: Zehui Shao, Yonghao Song, Qiyun Liu, Zhixing Duan, Huiqin Jiang

List of authors in order
Landing page: https://doi.org/10.1051/ro/2024038

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: diamond

Open access status per OpenAlex
OA URL: https://doi.org/10.1051/ro/2024038

Direct OA link when available
Concepts: Computer science, Algorithm, Combinatorics, Mathematics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
References (count): 16

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4391772559
doi	https://doi.org/10.1051/ro/2024038
ids.doi	https://doi.org/10.1051/ro/2024038
ids.openalex	https://openalex.org/W4391772559
fwci	0.0
type	article
title	On maximal Roman domination in graphs: complexity and algorithms
awards[0].id	https://openalex.org/G5657167529
awards[0].funder_id	https://openalex.org/F4320321001
awards[0].display_name
awards[0].funder_award_id	62172116
awards[0].funder_display_name	National Natural Science Foundation of China
biblio.issue	4
biblio.volume	58
biblio.last_page	2731
biblio.first_page	2709
topics[0].id	https://openalex.org/T10374
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9990000128746033
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Advanced Graph Theory Research
topics[1].id	https://openalex.org/T12541
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9902999997138977
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1703
topics[1].subfield.display_name	Computational Theory and Mathematics
topics[1].display_name	Graph Labeling and Dimension Problems
topics[2].id	https://openalex.org/T10720
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9869999885559082
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1703
topics[2].subfield.display_name	Computational Theory and Mathematics
topics[2].display_name	Complexity and Algorithms in Graphs
funders[0].id	https://openalex.org/F4320321001
funders[0].ror	https://ror.org/01h0zpd94
funders[0].display_name	National Natural Science Foundation of China
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.4511435031890869
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C11413529
concepts[1].level	1
concepts[1].score	0.45113405585289
concepts[1].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[1].display_name	Algorithm
concepts[2].id	https://openalex.org/C114614502
concepts[2].level	1
concepts[2].score	0.38474440574645996
concepts[2].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[2].display_name	Combinatorics
concepts[3].id	https://openalex.org/C33923547
concepts[3].level	0
concepts[3].score	0.37049493193626404
concepts[3].wikidata	https://www.wikidata.org/wiki/Q395
concepts[3].display_name	Mathematics
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.4511435031890869
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/algorithm
keywords[1].score	0.45113405585289
keywords[1].display_name	Algorithm
keywords[2].id	https://openalex.org/keywords/combinatorics
keywords[2].score	0.38474440574645996
keywords[2].display_name	Combinatorics
keywords[3].id	https://openalex.org/keywords/mathematics
keywords[3].score	0.37049493193626404
keywords[3].display_name	Mathematics
language	en
locations[0].id	doi:10.1051/ro/2024038
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4393919633
locations[0].source.issn	2804-7303
locations[0].source.type	journal
locations[0].source.is_oa	True
locations[0].source.issn_l	2804-7303
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	RAIRO. Operations research
locations[0].source.host_organization
locations[0].source.host_organization_name
locations[0].license	cc-by
locations[0].pdf_url
locations[0].version	publishedVersion
locations[0].raw_type	journal-article
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	RAIRO - Operations Research
locations[0].landing_page_url	https://doi.org/10.1051/ro/2024038
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5012636371
authorships[0].author.orcid	https://orcid.org/0000-0003-0764-4135
authorships[0].author.display_name	Zehui Shao
authorships[0].author_position	first
authorships[0].raw_author_name	Zehui Shao
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5101557904
authorships[1].author.orcid	https://orcid.org/0000-0003-1700-1133
authorships[1].author.display_name	Yonghao Song
authorships[1].author_position	middle
authorships[1].raw_author_name	Yonghao Song
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5014476053
authorships[2].author.orcid	https://orcid.org/0009-0009-9545-7962
authorships[2].author.display_name	Qiyun Liu
authorships[2].author_position	middle
authorships[2].raw_author_name	Qiyun Liu
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5009874737
authorships[3].author.orcid	https://orcid.org/0000-0001-9011-6653
authorships[3].author.display_name	Zhixing Duan
authorships[3].author_position	middle
authorships[3].raw_author_name	Zhixing Duan
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5032769891
authorships[4].author.orcid	https://orcid.org/0000-0002-3316-877X
authorships[4].author.display_name	Huiqin Jiang
authorships[4].author_position	last
authorships[4].raw_author_name	Huiqin Jiang
authorships[4].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://doi.org/10.1051/ro/2024038
open_access.oa_status	diamond
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	On maximal Roman domination in graphs: complexity and algorithms
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10374
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9990000128746033
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Advanced Graph Theory Research
related_works	https://openalex.org/W2748952813, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W4245490552, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W1587224694, https://openalex.org/W2042127053, https://openalex.org/W2142036596
cited_by_count	0
locations_count	1
best_oa_location.id	doi:10.1051/ro/2024038
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4393919633
best_oa_location.source.issn	2804-7303
best_oa_location.source.type	journal
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l	2804-7303
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	RAIRO. Operations research
best_oa_location.source.host_organization
best_oa_location.source.host_organization_name
best_oa_location.license	cc-by
best_oa_location.pdf_url
best_oa_location.version	publishedVersion
best_oa_location.raw_type	journal-article
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	RAIRO - Operations Research
best_oa_location.landing_page_url	https://doi.org/10.1051/ro/2024038
primary_location.id	doi:10.1051/ro/2024038
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4393919633
primary_location.source.issn	2804-7303
primary_location.source.type	journal
primary_location.source.is_oa	True
primary_location.source.issn_l	2804-7303
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	RAIRO. Operations research
primary_location.source.host_organization
primary_location.source.host_organization_name
primary_location.license	cc-by
primary_location.pdf_url
primary_location.version	publishedVersion
primary_location.raw_type	journal-article
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	RAIRO - Operations Research
primary_location.landing_page_url	https://doi.org/10.1051/ro/2024038
publication_date	2024-02-13
publication_year	2024
referenced_works	https://openalex.org/W1484040084, https://openalex.org/W2058946695, https://openalex.org/W2026300475, https://openalex.org/W1984228559, https://openalex.org/W2595550610, https://openalex.org/W2967821251, https://openalex.org/W1108868487, https://openalex.org/W3043697555, https://openalex.org/W4214937823, https://openalex.org/W2337802335, https://openalex.org/W2474076680, https://openalex.org/W2898860148, https://openalex.org/W2058460385, https://openalex.org/W3016425788, https://openalex.org/W2320924352, https://openalex.org/W2767964623
referenced_works_count	16
abstract_inverted_index.(	8, 26, 37, 51, 63, 69, 74, 83, 111, 119, 129, 156, 164, 168, 184
abstract_inverted_index.)	28, 39, 53, 65, 71, 76, 85, 113, 121, 131, 158, 166
abstract_inverted_index.,	179
abstract_inverted_index..	135, 196
abstract_inverted_index.:	24
abstract_inverted_index.;	95
abstract_inverted_index.=	7, 54, 72, 86, 132, 159
abstract_inverted_index.E	10
abstract_inverted_index.G	6, 19, 27, 94, 142, 157, 165, 178, 185, 195
abstract_inverted_index.N	62, 118
abstract_inverted_index.V	25, 48, 108, 126, 163
abstract_inverted_index.a	1, 12, 21, 58, 90, 101
abstract_inverted_index.f	23, 50, 68, 110, 128, 155, 167
abstract_inverted_index.i	38
abstract_inverted_index.u	60, 70, 124, 130
abstract_inverted_index.v	43, 46, 52, 64, 80, 84, 103, 106, 112, 120, 161, 169
abstract_inverted_index.{	45, 79, 105, 123
abstract_inverted_index.\|	49, 109, 127
abstract_inverted_index.),	11, 170, 186
abstract_inverted_index.0}	87, 115, 133
abstract_inverted_index.1,	31
abstract_inverted_index.2.	73
abstract_inverted_index.2}	32
abstract_inverted_index.In	96, 197
abstract_inverted_index.V,	9
abstract_inverted_index.an	139, 192, 215
abstract_inverted_index.as	154
abstract_inverted_index.be	268
abstract_inverted_index.by	181
abstract_inverted_index.ii	75
abstract_inverted_index.in	270
abstract_inverted_index.is	20, 88, 143, 187, 239
abstract_inverted_index.mR	183
abstract_inverted_index.of	18, 93, 138, 141, 146, 177, 191, 194, 204, 210, 227, 260
abstract_inverted_index.to	220, 243
abstract_inverted_index.we	200, 213, 231, 253
abstract_inverted_index.γ	182
abstract_inverted_index.0},	55
abstract_inverted_index.For	0, 40
abstract_inverted_index.The	77, 136
abstract_inverted_index.V\|f	82
abstract_inverted_index.all	151
abstract_inverted_index.and	171, 248, 264
abstract_inverted_index.any	228
abstract_inverted_index.can	267
abstract_inverted_index.its	147
abstract_inverted_index.not	89
abstract_inverted_index.set	78, 92
abstract_inverted_index.sum	145
abstract_inverted_index.the	34, 144, 172, 188, 205, 222, 255
abstract_inverted_index.{0,	30
abstract_inverted_index.→	29
abstract_inverted_index.∅	134
abstract_inverted_index.∈	44, 47, 61, 81, 104, 107, 125, 162
abstract_inverted_index.∑	160
abstract_inverted_index.∩	122
abstract_inverted_index.≠	114
abstract_inverted_index.MRDF	140, 193
abstract_inverted_index.even	241
abstract_inverted_index.over	150
abstract_inverted_index.show	254
abstract_inverted_index.some	202
abstract_inverted_index.star	244
abstract_inverted_index.such	66, 116
abstract_inverted_index.that	67, 117, 233
abstract_inverted_index.this	198
abstract_inverted_index.with	33
abstract_inverted_index.(MRD)	238
abstract_inverted_index.Roman	14, 174, 207, 224, 235, 257
abstract_inverted_index.block	265
abstract_inverted_index.every	41
abstract_inverted_index.graph	5
abstract_inverted_index.other	97
abstract_inverted_index.prove	232
abstract_inverted_index.there	56, 99
abstract_inverted_index.time.	272
abstract_inverted_index.(MRDF)	17
abstract_inverted_index.bounds	203
abstract_inverted_index.convex	245
abstract_inverted_index.exists	57, 100
abstract_inverted_index.graph.	229
abstract_inverted_index.graphs	247, 266
abstract_inverted_index.linear	217, 271
abstract_inverted_index.number	176, 209, 226, 259
abstract_inverted_index.paper,	199
abstract_inverted_index.simple	2
abstract_inverted_index.trees,	263
abstract_inverted_index.values	149
abstract_inverted_index.vertex	42, 59, 102
abstract_inverted_index.weight	137, 190
abstract_inverted_index.words,	98
abstract_inverted_index.Lastly,	252
abstract_inverted_index.chordal	249
abstract_inverted_index.compute	221
abstract_inverted_index.denoted	153, 180
abstract_inverted_index.develop	214
abstract_inverted_index.graphs,	262
abstract_inverted_index.graphs.	211, 251
abstract_inverted_index.integer	216
abstract_inverted_index.maximal	13, 173, 206, 223, 234, 256
abstract_inverted_index.minimum	189
abstract_inverted_index.problem	237
abstract_inverted_index.computed	269
abstract_inverted_index.function	16, 22, 148
abstract_inverted_index.bipartite	246, 250
abstract_inverted_index.connected	4
abstract_inverted_index.establish	201
abstract_inverted_index.following	35
abstract_inverted_index.threshold	261
abstract_inverted_index.vertices,	152
abstract_inverted_index.dominating	15, 91
abstract_inverted_index.domination	175, 208, 225, 236, 258
abstract_inverted_index.restricted	242
abstract_inverted_index.undirected	3
abstract_inverted_index.NP-complete	240
abstract_inverted_index.formulation	219
abstract_inverted_index.programming	218
abstract_inverted_index.properties:	36
abstract_inverted_index.Furthermore,	230
abstract_inverted_index.Additionally,	212
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	5
citation_normalized_percentile.value	0.03220046
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False