
arXiv: 1005.2542
For a graph $G$, its $r$th 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 $r$th power. In particular we obtain that, for $r\geq 3$, either the $r$th power is complete or "many" new edges are added. In this direction, Hegarty showed that there is a constant $\epsilon > 0$ such $e(G^3)\geq (1+\epsilon)e(G)$. We extend this result in two directions. We give an alternative proof of Hegarty's result with an improved constant of $\epsilon = \frac{1}{6}$. We also show that for general $r$, $e(G^{r}) \geq \left( \left\lceil \frac{r}{3} \right\rceil -1 \right)e(G).$
Distance in graphs, ems, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 05C12
Distance in graphs, ems, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 05C12
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
