It is proved that the minimum-density LDS problem in infinite $\mathbb{Z}$-periodic graphs with a finite period is NP-hard, which bridges the gap between cardinality minimization on finite graphs and density minimization on infinite graphs via a rigorous periodic reduction.
Abstract
A dominating set $S$ of a graph $G$ is a locating-dominating set (LDS) if, for each pair of distinct vertices not in~$S$, their neighbourhoods in $S$ are distinct. Finding a minimum-cardinality LDS in finite graphs is a well-known NP-hard problem. On infinite graphs, this problem naturally generalises to finding an LDS of minimum density. While density bounds have been widely studied for specific infinite regular grids, no computational complexity results exist for infinite graphs. We prove that the minimum-density LDS problem in infinite $\mathbb{Z}$-periodic graphs with a finite period is NP-hard. This result bridges the gap between cardinality minimization on finite graphs and density minimization on infinite graphs via a rigorous periodic reduction. Furthermore, our approach can be adapted to establish NP-hardness for related structural problems on infinite periodic graphs.
For a graph $G$, let $h(G)$ be the minimum cardinality of a vertex set meeting every maximum independent set of $G$. We establish two complementary reduction principles for the Bollob\'as--Erd\H{o}s--Tuza conjecture: the conjecture for arbitrary graphs is equivalent to its restriction to regular graphs of any fixed pos...
It is proved that the problem of computing a minimum dominating set on bipartite circle graphs admitting a chord representation in which the chords can be partitioned into two color classes such that no two chords of the same color intersect remains NP-hard.
A. K. Abu-Affash, Paz Carmi, Joseph S. B. Mitchell· arXiv.org· 0 citations
A set of vertices $S$ of a graph $G$ is locating-dominating if $S$ is dominating and, for each pair of distinct vertices not in $S$, their neighborhoods in $S$ are distinct. We present results on the minimum density of such sets in the infinite hexagonal grid with a finite number of rows $k$, also known as the hexagona...
In 1962, Erd\H{o}s characterized the maximum size of nonhamiltonian graphs of order $n$ with minimum degree at least $k$. Later, Ning and Peng [Combin. Probab. Comput. 29 (2020) 128-136] extended Erd\H{o}s's results to the clique condition and provided the maximum clique number for nonhamiltonian graphs of order $n$ wi...
The spectral Tur\'an type problem, initiated by Nikiforov in 2007, aims to determine the graphs among $n$-vertex $H$-free graphs having maximum spectral radius. In this paper, we study this problem for $1$-planar graphs, i.e., graphs that admit a drawing in the plane such that each edge is crossed at most once. Recentl...
This work focuses on graphs of bounded treewidth and pathwidth, and provides constructions that reach these bounds, and has the tight bound $nc(G,k))\leq \frac{7}{3}k$, for graphs $G$ with pathwidth 1 or treewidth 1.
Gaétan Berthe, F. Foucaud, Tuomo Lehtilä et al.· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
