Structural Properties of Twin-Free Graphs
Structural Properties of Twin-Free Graphs
复制标题
无孪生图的结构性质
DOI：
10.37236/934
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
A. Lobstein
中科院分区：
文献类型：
--
作者：
I. Charon;I. Honkala;O. Hudry;A. Lobstein
考虑一个连通无向图$G=(V，E)$，一个顶点子集$C\subseteq V$和一个整数$r\geq 1$；对于V$中的任何顶点$v\，设$B_r(V)$表示以$v$为中心的半径为$r$的球，即所有顶点通过至多$r$条边的路径连接到$v$的集合。如果对于V$中的所有顶点$v\，集合$B_r(V)\capC$都是非空的且不同，则我们称$C$为$r$-识别码。一个图允许至少一个$r$-识别码当且仅当它是$r$-无孪生的，即V$中的集合$B_r(V)$，$v\都是不同的。我们研究了$r$-无孪生图的一些结构问题，如以$2r+1$个顶点为子图的路的存在性，或删除一个顶点的后果。
Consider a connected undirected graph $G=(V,E)$, a subset of vertices $C \subseteq V$, and an integer $r \geq 1$; for any vertex $v\in V$, let $B_r(v)$ denote the ball of radius $r$ centered at $v$, i.e., the set of all vertices linked to $v$ by a path of at most $r$ edges. If for all vertices $v \in V$, the sets $B_r(v) \cap C$ are all nonempty and different, then we call $C$ an $r$-identifying code. A graph admits at least one $r$-identifying code if and only if it is $r$-twin-free, that is, the sets $B_r(v)$, $v \in V$, are all different. We study some structural problems in $r$-twin-free graphs, such as the existence of the path with $2r+1$ vertices as a subgraph, or the consequences of deleting one vertex.