Edge Number, Minimum Degree, Maximum Independent Set, Radius and Diameter in Twin-Free Graphs
Advances in Mathematics of Communications, Vol. 3(1), pp. 97-114, 2009.
David AUGER (*), Irène CHARON (*), Iiro HONKALA (#), 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
{auger, charon, hudry, lobstein}@telecom-paristech.fr
(#) Department of Mathematics
University of Turku, 20014 Turku, Finland
honkala@utu.fi
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 Br(v) denote the ball of radius r centred 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 Br(v) are different, then we say that G is r-twin-free.
In r-twin-free graphs, we prolong the study of the extremal values that can be achieved by some of the main classical parameters in graph theory, and investigate here the number of edges, the minimum degree, the size of a maximum independent set, as well as the radius and diameter.