Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Algorithmsarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Algorithms
Article . 2022 . Peer-reviewed
License: CC BY
Data sources: Crossref
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Algorithms
Article . 2022
Data sources: DOAJ
DBLP
Article . 2022
Data sources: DBLP
versions View all 4 versions
addClaim

Domination and Independent Domination in Extended Supergrid Graphs

Authors: Jong-Shin Chen; Ruo-Wei Hung; Fatemeh Keshavarz-Kohjerdi; Yung-Fa Huang;

Domination and Independent Domination in Extended Supergrid Graphs

Abstract

Supergrid graphs are derived by computing stitch paths for computerized embroidery machines. In the past, we have studied the Hamiltonian-related properties of supergrid graphs and their subclasses of graphs. In this paper, we propose a generalized graph class for supergrid graphs called extended supergrid graphs. Extended supergrid graphs include grid graphs, supergrid graphs, diagonal supergrid graphs, and triangular supergrid graphs as subclasses of graphs. In this paper, we study the problems of domination and independent domination on extended supergrid graphs. A dominating set of a graph is the subset of vertices on it, such that every vertex of the graph is in this set or adjacent to at least a vertex of this set. If any two vertices in a dominating set are not adjacent, this is called an independent dominating set. Domination and independent domination problems find a dominating set and an independent dominating set with the least number of vertices on a graph, respectively. The domination and independent domination set problems on grid graphs are known to be NP-complete, meaning that these two problems on extended supergrid graphs are also NP-complete. However, the complexities of these two problems in other subclasses of graphs remain unknown. In this paper, we first prove that these two problems on diagonal supergrid graphs are NP-complete, then, by a simple extension, we prove that these two problems on supergrid graphs and triangular supergrid graphs are also NP-complete. In addition, these two problems on rectangular supergrid graphs are known to be linearly solvable; however, the complexities of these two problems on rectangular triangular-supergrid graphs remain unknown. This paper provides tight upper bounds on the sizes of the minimum dominating and independent dominating sets for rectangular triangular-supergrid graphs.

Related Organizations
Keywords

Industrial engineering. Management engineering, triangular supergrid graph, QA75.5-76.95, rectangular triangular-supergrid graph, T55.4-60.8, supergrid graph, Electronic computers. Computer science, grid graph, diagonal supergrid graph, extended supergrid graph, independent domination, domination

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    4
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
4
Top 10%
Average
Average
gold