Isolation of regular graphs and $k$-chromatic graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916362175119360 |
|---|---|
| author | Borg, Peter |
| author_facet | Borg, Peter |
| contents | Given a set $\mathcal{F}$ of graphs, we call a copy of a graph in $\mathcal{F}$ an $\mathcal{F}$-graph. The $\mathcal{F}$-isolation number of a graph $G$, denoted by $ι(G,\mathcal{F})$, is the size of a smallest set $D$ of vertices of $G$ such that the closed neighbourhood of $D$ intersects the vertex sets of the $\mathcal{F}$-graphs contained by $G$ (equivalently, $G - N[D]$ contains no $\mathcal{F}$-graph). Thus, $ι(G,\{K_1\})$ is the domination number of $G$. For any integer $k \geq 1$, let $\mathcal{F}_{1,k}$ be the set of regular graphs of degree at least $k-1$, let $\mathcal{F}_{2,k}$ be the set of graphs whose chromatic number is at least $k$, and let $\mathcal{F}_{3,k}$ be the union of $\mathcal{F}_{1,k}$ and $\mathcal{F}_{2,k}$. Thus, $k$-cliques are members of both $\mathcal{F}_{1,k}$ and $\mathcal{F}_{2,k}$. We prove that for each $i \in \{1, 2, 3\}$, $\frac{m+1}{{k \choose 2} + 2}$ is a best possible upper bound on $ι(G, \mathcal{F}_{i,k})$ for connected $m$-edge graphs $G$ that are not $k$-cliques. The bound is attained by infinitely many (non-isomorphic) graphs. The proof of the bound depends on determining the graphs attaining the bound. This appears to be a new feature in the literature on isolation. Among the result's consequences are a sharp bound of Fenech, Kaemawichanurat and the present author on the $k$-clique isolation number and a sharp bound on the cycle isolation number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_10659 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Isolation of regular graphs and $k$-chromatic graphs Borg, Peter Combinatorics Discrete Mathematics 05C35, 05C69, 05C15, 05C38 Given a set $\mathcal{F}$ of graphs, we call a copy of a graph in $\mathcal{F}$ an $\mathcal{F}$-graph. The $\mathcal{F}$-isolation number of a graph $G$, denoted by $ι(G,\mathcal{F})$, is the size of a smallest set $D$ of vertices of $G$ such that the closed neighbourhood of $D$ intersects the vertex sets of the $\mathcal{F}$-graphs contained by $G$ (equivalently, $G - N[D]$ contains no $\mathcal{F}$-graph). Thus, $ι(G,\{K_1\})$ is the domination number of $G$. For any integer $k \geq 1$, let $\mathcal{F}_{1,k}$ be the set of regular graphs of degree at least $k-1$, let $\mathcal{F}_{2,k}$ be the set of graphs whose chromatic number is at least $k$, and let $\mathcal{F}_{3,k}$ be the union of $\mathcal{F}_{1,k}$ and $\mathcal{F}_{2,k}$. Thus, $k$-cliques are members of both $\mathcal{F}_{1,k}$ and $\mathcal{F}_{2,k}$. We prove that for each $i \in \{1, 2, 3\}$, $\frac{m+1}{{k \choose 2} + 2}$ is a best possible upper bound on $ι(G, \mathcal{F}_{i,k})$ for connected $m$-edge graphs $G$ that are not $k$-cliques. The bound is attained by infinitely many (non-isomorphic) graphs. The proof of the bound depends on determining the graphs attaining the bound. This appears to be a new feature in the literature on isolation. Among the result's consequences are a sharp bound of Fenech, Kaemawichanurat and the present author on the $k$-clique isolation number and a sharp bound on the cycle isolation number. |
| title | Isolation of regular graphs and $k$-chromatic graphs |
| topic | Combinatorics Discrete Mathematics 05C35, 05C69, 05C15, 05C38 |
| url | https://arxiv.org/abs/2304.10659 |