← 研踪 PaperTrailarXiv:2611.19361 · v1
Distance-$2$ isolation of connected graphs
首次提交 2026-11-14 20:02
版本更新 2026-11-14 20:02
雷达观测 2026-11-17 12:06
摘要
If is a set of graphs and is a copy of a graph in , then we call an -graph. Let be a connected -vertex graph. For a subset of the vertex set , let denote the second closed neighbourhood of . Let denote the size of a smallest subset of such that intersects the -graphs contained by (equivalently, contains no -graph). For , let denote the set of connected graphs that have at least edges (and at least one vertex if ). By a well-known result of Meir and Moon, if . We show that if , and is not a -cycle. Hua and Liu recently showed that if is not a -vertex path or a -cycle or a -cycle, then there exists a subset of such that and each component of has a universal vertex. We strengthen this result by showing that if , and is not an -cycle or one of five -vertex graphs. It follows that if is not a -cycle or a -vertex graph or a -cycle. This also implies the result of Hua and Liu, and that if is the set of cycles, then unless is a -cycle or a -vertex graph containing a cycle. All these bounds are sharp.
作者备注:15 pages
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-14 20:02 · 最新观测版本
Distance-$2$ isolation of connected graphs
If is a set of graphs and is a copy of a graph in , then we call an -graph. Let be a connected -vertex graph. For a subset of the vertex set , let denote the second closed neighbourhood of . Let denote the size of a smallest subset of such that intersects the -graphs contained by (equivalently, contains no -graph). For , let denote the set of connected graphs that have at least edges (and at least one vertex if ). By a well-known result of Meir and Moon, if . We show that if , and is not a -cycle. Hua and Liu recently showed that if is not a -vertex path or a -cycle or a -cycle, then there exists a subset of such that and each component of has a universal vertex. We strengthen this result by showing that if , and is not an -cycle or one of five -vertex graphs. It follows that if is not a -cycle or a -vertex graph or a -cycle. This also implies the result of Hua and Liu, and that if is the set of cycles, then unless is a -cycle or a -vertex graph containing a cycle. All these bounds are sharp.
查看此版本解读 →查看此版本原文 ↗