Pokrovskiy, A;
(2011)
Growth of Graph Powers.
The Electronic Journal of Combinatorics
, 18
(1)
, Article P88. 10.37236/575.
Preview |
Text
Pokrovskiy_575-PDF file-635-1-10-20120107.pdf - Published Version Download (109kB) | Preview |
Abstract
For a graph G, its rth power is constructed by placing an edge between two vertices if they are within distance r of each other. In this note we study the amount of edges added to a graph by taking its rth power. In particular we obtain that, for r ≥ 3, either the rth power is complete or "many" new edges are added. In this direction, Hegarty showed that there is a constant ε > 0 such e(G3) ≥ (1 + ε)e(G). We extend this result in two directions. We give an alternative proof of Hegarty's result with an improved constant of ε = 1/6. We also show that for general.
| Type: | Article |
|---|---|
| Title: | Growth of Graph Powers |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.37236/575 |
| Publisher version: | https://doi.org/10.37236/575 |
| 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/10112670 |
Archive Staff Only
 |
View Item |
