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 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})$为这样一个最小的点集 $D$ 的大小,使得从 $G$ 中删去 $D$ 的闭邻域所得到的图中不包含一个 $ \mathcal{F}$ 中的图的副本。因此,$\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$-环。这推广了Caro和Hansberg对 $\{K_{1,k}\}$-独立数的界限,作者对环割去数的界限和Fenech、Kaemawichanurat以及作者对 $k$-团隔离数的界限。由于Brooks定理的存在,若 $\mathcal{F} = \mathcal{F}_{3,k}$,那么相同的情况仍然成立。这些界限是尖锐的。

0
下载
关闭预览

相关内容

【PKDD 2021】PaGNN:基于交互结构学习的链路预测
专知会员服务
17+阅读 · 2021年11月26日
专知会员服务
40+阅读 · 2021年6月10日
专知会员服务
56+阅读 · 2021年1月26日
因果图,Causal Graphs,52页ppt
专知会员服务
241+阅读 · 2020年4月19日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
代码推荐 | 轻松实现各种图匹配 Graph matching.
图与推荐
2+阅读 · 2022年10月22日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
einsum is all you needed!
极市平台
1+阅读 · 2022年7月27日
图表示学习Graph Embedding综述
AINLP
32+阅读 · 2020年5月17日
【NeurIPS2019】图变换网络:Graph Transformer Network
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
图嵌入(Graph embedding)综述
人工智能前沿讲习班
449+阅读 · 2019年4月30日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年5月15日
Arxiv
0+阅读 · 2023年5月14日
Arxiv
0+阅读 · 2023年5月11日
VIP会员
相关资讯
代码推荐 | 轻松实现各种图匹配 Graph matching.
图与推荐
2+阅读 · 2022年10月22日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
einsum is all you needed!
极市平台
1+阅读 · 2022年7月27日
图表示学习Graph Embedding综述
AINLP
32+阅读 · 2020年5月17日
【NeurIPS2019】图变换网络:Graph Transformer Network
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
图嵌入(Graph embedding)综述
人工智能前沿讲习班
449+阅读 · 2019年4月30日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员