On the sizes of the graphs G, G r , G r \ G: the directed case.
David Auger, Irène Charon, Olivier Hudry, Antoine C. Lobstein · 2010
Let G be a directed graph and G r be its r-th power. We study different issues dealing with the number of arcs, or size, of G and G r: 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 G r = Kn, what is the minimum number of arcs that are added when going from G to G r, and which are the graphs achieving this bound? 1