It is proved that, for every fixed \(k\geq 3\), the exact value $\delta_2=1/9$ follows directly.
Abstract
Let $G_n$ be the $n\times n$ square grid, and let $k\geq 2$. A set $D\subseteq V(G_n)$ is an \emph{exact-distance $k$-dominating set} if every vertex $v\in V(G_n)\setminus D$ has a vertex $u\in D$ with $d(u,v)=k$. We write $D_{\mathrm{opt}}^{(k)}(G_n)$ for the minimum cardinality of such a set. For every fixed $k$, consider the limit $ \delta_k= \lim_{n\to\infty} \frac{D_{\mathrm{opt}}^{(k)}(G_n)}{n^2}. $ We prove that, for every fixed \(k\geq 3\), $ \frac{1}{4k} \leq \delta_k \leq \frac{k-1}{3k^2-k-1}. $ For $k=2$, the exact value $\delta_2=1/9$ follows directly.
Let $\mathbf{G}=\{G_1,\dots,G_{n}\}$ be a collection of not necessarily distinct $n$-vertex graphs with a common vertex set $V$. A cycle $C$ with $V(C)\subseteq V$ and $|E(C)|\leq n$ is called \emph{rainbow} in $\mathbf{G}$, if there exists an injection $\phi\colon E(C)\to [n]$ such that $e\in E(G_{\phi(e)})$ for each...
For an $n$-vertex graph $G$ and a permutation $\sigma$ of its vertex set, let $\sigma(G)$ denote the corresponding relabelling of $G$, and put \[ I_G(\sigma)=|E(G)\cap E(\sigma(G))|. \] Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph for which $I_G(\sigma)\geq k$ for every $\sigma$. In 1977 Erd\H{o}s...
Let $G$ be a simple graph on $n$ vertices and $e(G)$ edges. Let $\mu_1\geq \cdots \geq \mu_{n-1}\geq \mu_n=0$ be the Laplacian eigenvalues of $G$. For $k=1, \ldots, n$, let $S_k(G)=\sum_{i=1}^{k}\mu_i$. Brouwers conjecture asserts that for any $k\in\{1,\ldots, n\}$, $S_k(G)\leq e(G)+\binom{k+1}{2}$. In [Bounding the su...
For a graph $G$ and a set $B\subseteq V(G)$, the spread $\mathrm{sp}(B)$ of $B$ is the difference between the largest and the smallest degree in $G$ of a vertex of $B$, and for an integer $k\geq0$ the parameter $\mathrm{sp}(G,k)$ is the largest cardinality of a set $B$ with $\mathrm{sp}(B)\leq k$. Caro, Lauri and Zarb...
Y. Caro, R. S̆krekovski, Christina Zarb· 0 citations
For a graph $G$, let $\tau_{\mathrm{iso}}(G)$ denote the number of isomorphism classes of its spanning trees. For every fixed $d\ge3$ and all sufficiently large $n$, we prove that every connected $n$-vertex graph $G$ with $\delta(G)\ge d$ satisfies \[\tau_{\mathrm{iso}}(G)\ge \tau_{\mathrm{iso}}(K_{d,n-d})=A_dn^{d-1}+O...
Let $k\ge 3$ and let $n=km$. A $K_k$-factor in an $n$-vertex graph is a collection of $m$ vertex-disjoint copies of $K_k$ that covers the entire vertex set. We determine the maximum adjacency spectral radius of an $n$-vertex graph containing no $K_k$-factor when $m\ge 2k-1$. More precisely, we prove that every such gra...