تقرير
On the $C_4$-isolation number of a graph
| العنوان: | On the $C_4$-isolation number of a graph |
|---|---|
| المؤلفون: | Wei, Xiaohua, Zhang, Gang, Zhao, Biao |
| سنة النشر: | 2023 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05C69 |
| الوصف: | Let $C_k$ be the cycle of length $k$. For any graph $G$, a subset $D \subseteq V(G)$ is a $C_k$-isolating set of $G$ if the graph obtained from $G$ by deleting the closed neighbourhood of $D$ contains no $C_k$ as a subgraph. The $C_k$-isolation number of $G$, denoted by $\iota(G,C_k)$, is the cardinality of a smallest $C_k$-isolating set of $G$. Borg (2020) and Borg et al. (2022) proved that if $G \ncong C_3$ is a connected graph of order $n$ and size $m$, then $\iota(G,C_3) \leq \frac{n}{4}$ and $\iota(G,C_3) \leq \frac{m+1}{5}$. Very recently, Bartolo, Borg and Scicluna showed that if $G$ is a connected graph of order $n$ that is not one of the determined nine graphs, then $\iota(G,C_4) \leq \frac{n}{5}$. In this paper, we prove that if $G \ncong C_4$ is a connected graph of size $m$, then $\iota(G,C_4) \leq \frac{m+1}{6}$, and we characterize the graphs that attain the bound. Moreover, we conjecture that if $G \ncong C_k$ is a connected graph of size $m$, then $\iota(G,C_k) \leq \frac{m+1}{k+2}$. Comment: 15 pages, 2 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2310.17337 |
| رقم الأكسشن: | edsarx.2310.17337 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |