For any graph $G$ and any set $\mathcal{F}$ of graphs, let $\iota(G,\mathcal{F})$ denote the size of a smallest set $D$ of vertices of $G$ such that the graph obtained from $G$ by deleting the closed neighbourhood of $D$ does not contain a copy of a graph in $\mathcal{F}$. Thus, $\iota(G,\{K_1\})$ is the domination number of $G$. For any integer $k \geq 1$, let $\mathcal{F}_{0,k} = \{K_{1,k}\}$, 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}_{0,k}$, $\mathcal{F}_{1,k}$ and $\mathcal{F}_{2,k}$. We prove that if $G$ is a connected $n$-vertex graph and $\mathcal{F} = \mathcal{F}_{0,k} \cup \mathcal{F}_{1,k}$, then $\iota(G, \mathcal{F}) \leq \frac{n}{k+1}$ unless $G$ is a $k$-clique or $k = 2$ and $G$ is a $5$-cycle. This generalizes a classical bound of Ore on the domination number, a bound of Caro and Hansberg on the $\{K_{1,k}\}$-isolation number, a bound of the author on the cycle isolation number, and a bound of Fenech, Kaemawichanurat and the author on the $k$-clique isolation number. By Brooks' Theorem, the same holds if $\mathcal{F} = \mathcal{F}_{3,k}$. The bounds are sharp.


翻译:对于任意图$G$和任意图集$\mathcal{F}$,令$\iota(G,\mathcal{F})$表示在$G$中删除$\mathcal{F}$中某些图的所有子图所需的最小顶点集合$D$的大小。因此,$\iota(G,\{K_1\})$是$G$的支配数。对于任意整数$k\geq 1$,令$\mathcal{F}_{0,k}=\{K_{1,k}\}$,$\mathcal{F}_{1,k}$为度不低于$k-1$的正则图集合,$\mathcal{F}_{2,k}$为色数不低于$k$的图集合,$\mathcal{F}_{3,k}$为$\mathcal{F}_{0,k}$、$\mathcal{F}_{1,k}$和$\mathcal{F}_{2,k}$的并集。我们证明,如果$G$是$ n $个顶点的连通图,$\mathcal{F}= \mathcal{F}_{0,k} \cup \mathcal{F}_{1,k}$,则$\iota(G, \mathcal{F})\leq \frac{n}{k+1}$,除非$G$是$k$-团或$k=2$且$G$是$5$-环。这推广了Ore关于支配数的经典界限,Caro和Hansberg关于$\{K_{1,k}\}$-孤立数的界限,作者关于环孤立数的界限,以及Fenech、Kaemawichanurat和作者关于$k$-团孤立数的界限。根据Brooks定理,如果$\mathcal{F}= \mathcal{F}_{3,k}$,则同样成立。这些界限是最优的。

0
下载
关闭预览

相关内容

MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
NeurIPS 2022 | 利用子图和结点的对称性提升子图GNN
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
图神经网络库PyTorch geometric
图与推荐
17+阅读 · 2020年3月22日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年6月4日
Arxiv
0+阅读 · 2023年6月3日
Arxiv
0+阅读 · 2023年6月3日
Arxiv
0+阅读 · 2023年6月2日
Arxiv
0+阅读 · 2023年5月31日
VIP会员
相关VIP内容
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
相关资讯
NeurIPS 2022 | 利用子图和结点的对称性提升子图GNN
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
图神经网络库PyTorch geometric
图与推荐
17+阅读 · 2020年3月22日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
相关论文
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员