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

Ars Combinatoria, Vol. 101, pp. 161-185, 2011.

Irène CHARON, Olivier HUDRY & Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
{irene.charon, olivier.hudry, antoine.lobstein}@telecom-paristech.fr

Abstract. Consider a connected undirected graph G=(V,E) and an integer r greater than or equal to 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.

Revenir à la page d'accueil