eprintid: 10112671
rev_number: 16
eprint_status: archive
userid: 608
dir: disk0/10/11/26/71
datestamp: 2021-05-28 12:47:54
lastmod: 2021-10-16 22:06:13
status_changed: 2021-05-28 12:47:54
type: article
metadata_visibility: show
creators_name: Pokrovskiy, A
title: Edge growth in graph powers
ispublished: pub
divisions: UCL
divisions: B04
divisions: C06
divisions: F59
note: This version is the version of record. For information on re-use, please refer to the publisher's terms and conditions.
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
date: 2014-01-14
date_type: published
official_url: https://ajc.maths.uq.edu.au/pdf/58/ajc_v58_p347.pdf
oa_status: green
full_text_type: other
language: eng
primo: open
primo_central: open_green
verified: verified_manual
elements_id: 1798239
lyricists_name: Pokrovskiy, Alexey
lyricists_id: APOKR39
actors_name: Pokrovskiy, Alexey
actors_id: APOKR39
actors_role: owner
full_text_status: public
publication: Australasian Journal of Combinatorics
volume: 58
number: 2
pagerange: 347-357
issn: 2202-3518
citation:        Pokrovskiy, A;      (2014)    Edge growth in graph powers.                   Australasian Journal of Combinatorics , 58  (2)   pp. 347-357.          Green open access   
 
document_url: https://discovery.ucl.ac.uk/id/eprint/10112671/1/EdgeGrowthFinal.pdf