Restrained domination and its variants in extended supergrid graphs
RW Hung - Theoretical Computer Science, 2023 - Elsevier
Domination problem is a well-known NP-complete problem for general graphs. In this paper,
we will study its three variants, including restrained, independent restrained, and restrained …
we will study its three variants, including restrained, independent restrained, and restrained …
The Hamiltonicity, Hamiltonian connectivity, and longest (s, t)-path of L-shaped supergrid graphs
F Keshavarz-Kohjerdi, RW Hung - arxiv preprint arxiv:1904.02581, 2019 - arxiv.org
Supergrid graphs contain grid graphs and triangular grid graphs as their subgraphs. The
Hamiltonian cycle and path problems for general supergrid graphs were known to be NP …
Hamiltonian cycle and path problems for general supergrid graphs were known to be NP …
Paired restraint domination in extended supergrid graphs
Consider a graph G with vertex set V (G) and edge set E (G). A subset D of V (G) is said to be
a dominating set of G if every vertex not in D is adjacent to at least one vertex in D. If, in …
a dominating set of G if every vertex not in D is adjacent to at least one vertex in D. If, in …
The Hamiltonicity and Hamiltonian-connectivity of Solid Supergrid Graphs
F Keshavarz-Kohjerdi, A Bagheri - Bulletin of the Malaysian Mathematical …, 2023 - Springer
The Hamiltonian path and cycle problems are well-known NP-complete problems. A given
graph is Hamiltonian-connected if there exists a Hamiltonian path between any two vertices …
graph is Hamiltonian-connected if there exists a Hamiltonian path between any two vertices …
Hamilton connectivity of convex polytopes with applications to their detour index
A connected graph is called Hamilton‐connected if there exists a Hamiltonian path between
any pair of its vertices. Determining whether a graph is Hamilton‐connected is an NP …
any pair of its vertices. Determining whether a graph is Hamilton‐connected is an NP …
Hamiltonian (s, t)-paths in solid supergrid graphs
F Keshavarz-Kohjerdi, A Bagheri - Computational and Applied …, 2024 - Springer
The Hamiltonian path is a well-known NP-complete problem. This problem has been studied
for solid supergrid graphs, in some special cases, and recently for 3-connected solid …
for solid supergrid graphs, in some special cases, and recently for 3-connected solid …
The restrained domination and independent restrained domination in extending supergrid graphs
RW Hung, MJ Chiu - … , COCOON 2021, Tainan, Taiwan, October 24–26 …, 2021 - Springer
Let G be a graph with vertex set V (G) and edge set E (G). A set D ⊆ V (G) D⊆ V (G) is a
dominating set of G if every vertex not in D is adjacent to at least one vertex of D. A …
dominating set of G if every vertex not in D is adjacent to at least one vertex of D. A …
Hamilton-connectivity of line graphs with application to their detour index
A graph is called Hamilton-connected if there exists a Hamiltonian path between every pair
of its vertices. Determining whether or not a graph is Hamilton-connected is an NP-complete …
of its vertices. Determining whether or not a graph is Hamilton-connected is an NP-complete …
Finding longest (s, t)-paths of O-shaped supergrid graphs in linear time
RW Hung, F Keshavarz-Kohjerdi… - 2019 IEEE 10th …, 2019 - ieeexplore.ieee.org
The longest path and Hamiltonian problems were known to be NP-complete. In spite of
many applications of these problems, their complexities are still unknown for many classes …
many applications of these problems, their complexities are still unknown for many classes …
The Longest -paths of -shaped Supergrid Graphs
RW Hung, F Keshavarz-Kohjerdi - arxiv preprint arxiv:1911.08558, 2019 - arxiv.org
In this paper, we continue the study of the Hamiltonian and longest $(s, t) $-paths of
supergrid graphs. The Hamiltonian $(s, t) $-path of a graph is a Hamiltonian path between …
supergrid graphs. The Hamiltonian $(s, t) $-path of a graph is a Hamiltonian path between …