Total domination and open packing in some subclasses of bipartite graphs

M. A. Shalu () and V. K. Kirubakaran ()
Additional contact information
M. A. Shalu: Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram
V. K. Kirubakaran: Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram

Journal of Combinatorial Optimization, 2025, vol. 50, issue 5, No 2, 60 pages

Abstract: Abstract A total dominating set in a graph G(V, E) is a vertex subset D such that every vertex in V is adjacent to some vertex in D. The cardinality of a minimum total dominating set in G is called the total domination number of G. Given a graph G and a positive integer $$k\le |V(G)|,$$ the decision problem Total Dominating Set is to decide whether G has a total dominating set of size at most k. We prove that Total Dominating Set is NP-complete on (i) 2-degenerate planar perfect elimination bipartite graphs of maximum degree three (Class $$\mathcal {G}$$ ), which improves a result by Garnero and Sau (Discr Math Theor Comput Sci 20:20, 2018. https://doi.org/10.23638/DMTCS-20-1-14 ), and (ii) the intersection class of star-convex, comb-convex, and perfect elimination bipartite graphs (Class $$\mathcal {H}$$ ). Chlebík and Chlebíková (Inf Comput 206(11):1264–1275, 2008) proved that the total domination number cannot be approximated within a factor of $$(1-\epsilon )\ln n$$ for any $$\epsilon >0$$ on bipartite graphs unless $$NP\subseteq Dtime(n^{O(\log \log n)})$$ . We strengthen this result by showing that the approximation hardness bound holds for the class $$\mathcal {H}$$ , a subclass of bipartite graphs. Also, we proved that Total Dominating Set parameterized by solution size is W[2]-complete on the class $$\mathcal {H}$$ . On the positive side, we show that Total Dominating Set parameterized by maximum degree is fixed-parameter tractable in star-convex bipartite graphs. A vertex subset S is called an open packing in G if, for every distinct $$x',x''\in S$$ , $$N_G(x')\cap N_G(x'')=\emptyset $$ , where $$N_G(x)=\{y\in V(G):\, xy\in E(G)\}$$ for every $$x\in V(G)$$ . The cardinality of a maximum open packing in G is called the open packing number of G. Open packing and total domination is a pair of primal-dual graph problems and, for graphs without isolated vertices, the open packing number is a lower bound for the total domination number. The Open Packing problem takes a graph G and a positive integer k as inputs and checks whether G has an open packing of size at least k. It is known that Open Packing is NP-complete in bipartite graphs. Our work strengthens this result by showing that the problem remains NP-complete on (i) class $$\mathcal {G}$$ and (ii) class $$\mathcal {H}$$ . We further infer that on the graph class $$\mathcal {H}$$ , (i) open packing number is hard to approximate within a factor of $$n^{\frac{1}{2}-\epsilon }$$ for any $$\epsilon >0$$ unless P = NP and (ii) Open Packing parameterized by solution size is W[1]-complete. Also, we show that Open Packing parameterized by maximum degree is fixed-parameter tractable in star convex bipartite graphs. In addition, we design polynomial time algorithms to find a maximum open packing in circular-convex bipartite graphs and triad-convex bipartite graphs.

Keywords: Total dominating set; Open packing; Subclique; Triangle-free graphs; Bipartite graphs (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01360-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:50:y:2025:i:5:d:10.1007_s10878-025-01360-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01360-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().