Abstract
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 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 Gr = 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?.
| Original language | English |
|---|---|
| Pages (from-to) | 87-109 |
| Number of pages | 23 |
| Journal | Australasian Journal of Combinatorics |
| Volume | 48 |
| Publication status | Published - 1 Oct 2010 |
Fingerprint
Dive into the research topics of 'On the sizes of the graphs G, Gr, Gr\G: The directed case'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver