Structural properties of twin-free graphs
The electronic journal of combinatorics, Tome 14 (2007)
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.
@article{10_37236_934,
author = {Ir\`ene Charon and Iiro Honkala and Olivier Hudry and Antoine Lobstein},
title = {Structural properties of twin-free graphs},
journal = {The electronic journal of combinatorics},
year = {2007},
volume = {14},
doi = {10.37236/934},
zbl = {1113.05085},
url = {http://geodesic.mathdoc.fr/articles/10.37236/934/}
}
Irène Charon; Iiro Honkala; Olivier Hudry; Antoine Lobstein. Structural properties of twin-free graphs. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/934
Cité par Sources :