Metraipolis › archive › dc_37b9fd4e1909

Roman Domination on Circular-Convex, Triad-Convex Bipartite Graphs and $P_4$-Tidy Graphs — arXiv:2609.19240

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.19240
License (as archived)
CC0-1.0
Archived
2026-10-10T04:47:31.748Z
SHA-256 of the archived text
bd971f79c807e17828987ee5d18deb06e9d249d924db9a92f05273bde048eae4
Stable URL of this page
https://metraipolis.com/documento/dc_37b9fd4e1909

How to cite

Roman Domination on Circular-Convex, Triad-Convex Bipartite Graphs and $P_4$-Tidy Graphs — arXiv:2609.19240 — arXiv (en), https://arxiv.org/abs/2609.19240 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_37b9fd4e1909 (Metraipolis archive dc_37b9fd4e1909, sha256 bd971f79c807e17828987ee5d18deb06e9d249d924db9a92f05273bde048eae4)
BibTeX
@misc{dc37b9fd4e1909,
  title = {Roman Domination on Circular-Convex, Triad-Convex Bipartite Graphs and $P_4$-Tidy Graphs — arXiv:2609.19240},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.19240},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_37b9fd4e1909; sha256 bd971f79c807e17828987ee5d18deb06e9d249d924db9a92f05273bde048eae4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19240. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Roman Domination Problem (RDP) on a graph \(G=(V,E)\) asks for a labeling function \(f:V\rightarrow\{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 \(\sum_{v\in V} f(v)\); this minimum value is the Roman domination number of \(G\), denoted by \(\gamma_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 \(\gamma_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 \(\gamma_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 \(\gamma_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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in math.CO).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.19240 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T04:15:33.167Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).