Roman Domination on Circular-Convex, Triad-Convex Bipartite Graphs and P4-Tidy Graphs
Abstract
The Roman Domination Problem (RDP) on a graph G=(V,E) asks for a labeling function f:V→{0,1,2} such that every vertex assigned value 0 is adjacent to a vertex assigned value 2. The objective is to minimize the total weight ∑v∈ V f(v); this minimum value is the Roman domination number of G, denoted by γR(G). In this paper, we study RDP on graph classes motivated by convexity and induced-P4 structure. First, we consider circular-convex bipartite graphs, a natural superclass of convex bipartite graphs, where RDP is already known to be polynomial-time solvable. Assuming that a circular-convex representation is given, we compute γR(G) in O(n6) time by cutting the circular order, separating interval and wrap-around vertices, and branching over at most two wrap-around vertices assigned value 2. Second, we study triad-convex bipartite graphs, a restricted subclass of tree-convex bipartite graphs whose convexity tree is a subdivision of K1,3. Although RDP is hard on broader tree-convex subclasses such as star-convex and comb-convex bipartite graphs, we show that γR(G) can be computed in O(n7) time on triad-convex bipartite graphs. Finally, we study P4-tidy graphs, which properly extend cographs. Using the Giakoumakis et al. structural decomposition of P4-tidy graphs, we give a direct, exact algorithm that computes γR(G) in O(n+m) time. These results extend the algorithmic boundary of Roman domination on convexity-based bipartite graphs and P4-structured graph classes.
Related
- Graphs with Large Vertex–Edge Roman {2}-Domination Number
- Paired Domination in Cubic Bipartite Graphs
- Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs
- The domination number of the 2-token graph of the complete bipartite graph
- The domination number of the k-token graph of the complete bipartite graph Km,n
BibTeX
@misc{das2026roman,
title = {{Roman Domination on Circular-Convex, Triad-Convex Bipartite Graphs and $P_4$-Tidy Graphs}},
author = {Gautam K. Das and Kamal Santra},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19240},
eprint = {2609.19240},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19240},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Roman Domination on Circular-Convex, Triad-Convex Bipartite Graphs and P_4-Tidy Graphs
AU - Gautam K. Das
AU - Kamal Santra
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.19240
UR - https://arxiv.org/abs/2609.19240
AB - The Roman Domination Problem (RDP) on a graph G=(V,E) asks for a labeling function f:V→{0,1,2} such that every vertex assigned value 0 is adjacent to a vertex assigned value 2. The objective is to minimize the total weight ∑_v∈ V f(v); this minimum value is the Roman domination number of G, denoted by γ_R(G). In this paper, we study RDP on graph classes motivated by convexity and induced-P_4 structure. First, we consider circular-convex bipartite graphs, a natural superclass of convex bipartite graphs, where RDP is already known to be polynomial-time solvable. Assuming that a circular-convex representation is given, we compute γ_R(G) in O(n^6) time by cutting the circular order, separating interval and wrap-around vertices, and branching over at most two wrap-around vertices assigned value 2. Second, we study triad-convex bipartite graphs, a restricted subclass of tree-convex bipartite graphs whose convexity tree is a subdivision of K_1,3. Although RDP is hard on broader tree-convex subclasses such as star-convex and comb-convex bipartite graphs, we show that γ_R(G) can be computed in O(n^7) time on triad-convex bipartite graphs. Finally, we study P_4-tidy graphs, which properly extend cographs. Using the Giakoumakis et al. structural decomposition of P_4-tidy graphs, we give a direct, exact algorithm that computes γ_R(G) in O(n+m) time. These results extend the algorithmic boundary of Roman domination on convexity-based bipartite graphs and P_4-structured graph classes.
ER -