Extremal Values for Identification, Domination and Maximum Cliques in Twin-Free Graphs

Abstract

Consider a connected undirected graph \(G = (V, E)\) 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)\) are different, then we say that \(G\) is \(r\)-twin-free.

Studies have been made, e.g., on the number of edges or the minimum degree in one-twin-free graphs. We extend these investigations and in particular we determine the exact size of the largest clique in a connected \(r\)-twin-free graph.