Pokrovskiy, A;
(2014)
Edge growth in graph powers.
Australasian Journal of Combinatorics
, 58
(2)
pp. 347-357.
Preview |
Text
EdgeGrowthFinal.pdf - Accepted Version Download (115kB) | Preview |
Abstract
For a graph G, its rth power G is defined as the graph with the same vertex set as G, and an edge between any two vertices whenever they are within distance r of each other in G. Motivated by a result from additive number theory, Hegarty raised the question of how many new edges G has when G is a regular, connected graph with diameter at least r. We address this question for r ≠ 3, 6. We give a lower bound for the number of edges in the rth power of G in terms of the order of G and the minimal degree of G. As a corollary, for r ≠3, 6, we determine how small the ratio e(G )/e(G) can be for regular, connected graphs of diameter at least r. r r r
| Type: | Article |
|---|---|
| Title: | Edge growth in graph powers |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://ajc.maths.uq.edu.au/pdf/58/ajc_v58_p347.pd... |
| Language: | English |
| Additional information: | This version is the version of record. For information on re-use, please refer to the publisher's terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10112671 |
Archive Staff Only
 |
View Item |
