- Tytuł:
- Double dominating sequences in bipartite and co-bipartite graphs
- Autorzy:
-
Sharma, Gopika
Pandey, Arti - Tematy:
-
double dominating sequences
bipartite graphs
chain graphs
NP-completeness
graph algorithms - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Powiązania:
- https://bibliotekanauki.pl/articles/60274301.pdf Link otwiera się w nowym oknie
- Opis:
- 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.
- Dostawca treści:
- Biblioteka Nauki
Artykuł