Discrete Applied Mathematics, Vol. 159, pp. 1666-1675, 2011.

David AUGER, 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
{david.auger, irene.charon, olivier.hudry, antoine.lobstein}@telecom-paristech.fr

Résumé. Let G be an undirected graph and G^r be its r-th power. We study different issues dealing with the number of edges in G and G^r. In particular, we answer the following question: given an integer r>1 and all connected graphs G of order n such that G^r is not equal to K_n, what is the minimum number of edges that are added when going from G to G^r, and which are the graphs achieving this bound?

Revenir à la page d'accueil