On the Sizes of the Graphs G, Gr, Gr\ G: the Directed Case
Australasian Journal of Combinatorics, Vol. 48, pp. 87-109, 2010.
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
{auger, charon, hudry, lobstein}@enst.fr
Résumé. Let G be a directed graph and Gr be its r-th power. We study different issues dealing with the number of arcs, or size, of G and Gr: given the order and diameter of a strongly connected digraph, what is its maximum size, and which are the graphs achieving this bound? What is the minimum size of the r-th power of a strongly connected digraph, and which are the graphs achieving this bound? Given all strongly connected digraphs G of order n such that Gr is not equal to Kn, what is the minimum number of arcs that are added when going from G to Gr, and which are the graphs achieving this bound?