EUVIMEDEUVIMED entdecken
Crossref

Total Outer-Connected Domination on Convex Split Graphs — Classical, Parameterized and Approximation Complexity Results

A. Mohanapriya, P. Renjith, N. Sadagopan

International Journal of Foundations of Computer Science · 21.05.2026 · 1-20

DOI: 10.1142/s0129054126500127 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Journal of Foundations of Computer Science, online erschienen am 21.05.2026. Verfasst von A. Mohanapriya und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

For a connected graph [Formula: see text], the total outer-connected dominating set problem (TOCD) asks for a partition of [Formula: see text] into [Formula: see text] and [Formula: see text] such that [Formula: see text] is a total dominating set of [Formula: see text] and [Formula: see text] is connected. TOCD is NP-complete on general graphs, chordal graphs and split graphs [1]. In this paper, we introduce a subclass of split graphs called star-convex split graphs and strengthen the NP-completeness result of split graphs; TOCD is NP-complete on star-convex split graphs with convexity on clique (independent set). In the parameterized setting, it is interesting to note that the total outer-connected domination problem, with respect to the solution size, is W[2]-hard when the convexity of star-convex split graphs lies on the clique, whereas it is W[1]-hard when the convexity lies on the independent set. Further, we obtain an interesting dichotomy for TOCD on star-convex split graphs with convexity on clique; TOCD is polynomial-time solvable if no pendant vertices, and NP-complete, otherwise. If the convexity is on the independent set, then the dichotomy is; on [Formula: see text]-free star-convex split graphs, TOCD is NP-complete, and polynomial-time solvable on [Formula: see text]-free split graphs. It is natural to ask for the status of approximation algorithm for finding minimum total outer-connected domination on star-convex split graphs with convexity. We prove that star-convex split graphs with convexity on independent set does not admit [Formula: see text]-approximation algorithm unless NP [Formula: see text] DTIME([Formula: see text]). Furthermore, we prove that for path-convex split graphs finding a minimum total outer-connected domination is polynomial-time solvable.

Zitieren

APA

Mohanapriya, A., Renjith, P., & Sadagopan, N. (2026). Total Outer-Connected Domination on Convex Split Graphs — Classical, Parameterized and Approximation Complexity Results. International Journal of Foundations of Computer Science, 1-20. https://doi.org/10.1142/s0129054126500127

Vancouver

Mohanapriya A, Renjith P, Sadagopan N. Total Outer-Connected Domination on Convex Split Graphs — Classical, Parameterized and Approximation Complexity Results. International Journal of Foundations of Computer Science. 2026:1-20. doi:10.1142/s0129054126500127

BibTeX
@article{Mohanapriya2026,
  author = {Mohanapriya, A. and Renjith, P. and Sadagopan, N.},
  title = {Total Outer-Connected Domination on Convex Split Graphs — Classical, Parameterized and Approximation Complexity Results},
  journal = {International Journal of Foundations of Computer Science},
  year = {2026},
  pages = {1--20},
  doi = {10.1142/s0129054126500127}
}
Kostenlos starten →