Article in volume
Authors:
Title:
Double dominating sequences in bipartite and co-bipartite graphs
PDFSource:
Discussiones Mathematicae Graph Theory 45(2) (2025) 545-564
Received: 2023-04-18 , Revised: 2024-04-05 , Accepted: 2024-04-12 , Available online: 2024-06-17 , https://doi.org/10.7151/dmgt.2548
Abstract:
In a graph $G=(V,E)$, a vertex $u \in V$ dominates a vertex $v \in V$ if
$v \in N_G[u]$. A sequence $S=(v_1,v_2, \ldots, v_k)$ of vertices of $G$ is
called a double dominating sequence of $G$ if (i) for each $i$, the vertex
$v_i$ dominates at least one vertex $u \in V$ which is dominated at most once
by the previous vertices of $S$ and, (ii) all vertices of $G$ have been
dominated at least twice by the vertices of $S$.
Grundy Double Domination problem asks to find a double dominating
sequence of maximum length for a given graph $G$. In this paper, we prove that
the decision version of the problem is NP-complete for bipartite and
co-bipartite graphs. We look for the complexity status of the problem in the
class of chain graphs which is a subclass of bipartite graphs. We use dynamic
programming approach to solve this problem in chain graphs and propose an
algorithm which outputs a Grundy double dominating sequence of a chain graph
$G$ in linear-time.
Keywords:
double dominating sequences, bipartite graphs, chain graphs, NP-completeness, graph algorithms
References:
- B. Brešar, T. Gologranc, M. Milanič, D.F. Rall and R. Rizzi, Dominating sequences in graphs, Discrete Math. 336 (2014) 22–36.
https://doi.org/10.1016/j.disc.2014.07.016 - B. Brešar, S. Klavžar and D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979–991.
https://doi.org/10.1137/100786800 - B. Brešar, A. Pandey and G. Sharma, Computational aspects of some vertex sequences of Grundy domination-type, Indian J. Discrete Math. 8 (2022) 21–38.
- J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer Science, (John Wiley and Sons, New York 1985) 282–300.
- J.F. Fink and M.S. Jacobson, On n-domination, n-dependence and forbidden subgraphs, in: Graph Theory with Applications to Algorithms and Computer Science, (John Wiley and Sons, New York 1985) 301–311.
- T.W. Haynes and S.T. Hedetniemi, Vertex sequences in graphs, Discrete Math. Lett. 6 (2021) 19–31.
https://doi.org/10.47443/dml.2021.s103 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Topics in Domination in Graphs, Dev. Math. 64 (Springer, Cham, 2020).
https://doi.org/10.1007/978-3-030-51117-3 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Structures of Domination in Graphs, Dev. Math. 66 (Springer, Cham, 2021).
https://doi.org/10.1007/978-3-030-58892-2 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs, Advanced Topics (Marcell Dekker, New York, 1998).
https://doi.org/10.1201/9781315141428 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
https://doi.org/10.1201/9781482246582 - P. Heggernes and D. Kratsch, Linear-time certifying recognition algorithms and forbidden induced subgraphs, Nordic J. Comput. 14 (2007) 87–108.
- G. Sharma and A. Pandey, Computational aspects of double dominating sequences in graphs, in: Algorithms and Discrete Applied Mathematics: 9th International Conference, CALDAM 2023, A.Bagchi and R. Muthu (Ed(s)), Lecture Notes in Computer Science 13947, (Springer-Verlag, Berlin, Heidelberg, 2023) 284–296.
https://doi.org/10.1007/978-3-031-25211-2_22
Close