| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419846 | Discrete Applied Mathematics | 2011 | 10 Pages |
Abstract
Let GG be an undirected graph and GrGr be its rr-th power. We study different issues dealing with the number of edges in GG and GrGr. In particular, we answer the following question: given an integer r≥2r≥2 and all connected graphs GG of order nn such that Gr≠KnGr≠Kn, what is the minimum number of edges that are added when going from GG to GrGr, and which are the graphs achieving this bound?
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
David Auger, Irène Charon, Olivier Hudry, Antoine Lobstein,