Structural Properties of Twin-Free Graphs

Abstract

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.