Structural properties of twin-free graphs (Q870075)

Summary: Consider a connected undirected graph \(G=(V,E)\), a set \(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.