Edge growth in graph powers

MaRDI QIDQ2876017zbMATH OpenFDO

Authors Alexey Pokrovskiy

Publication date 15 August 2014

Published in The Australasian Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.6085, http://ajc.maths.uq.edu.au/pdf/58/ajc_v58_p347.pdf

zbMATH Keywords

Cayley graphCauchy-Davenport theorem

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Connectivity (05C40)

Abstract: For a graph G, its rth power G^r has the same vertex set as G, and has an edge between any two vertices within distance r of each other in G. 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 we determine how small the ratio e(G^r)/e(G) can be for regular graphs of diameter at least r.

Recommendations

• Growth of graph powers
• On the sizes of graphs and their powers: the undirected case
• Edge growth in graph squares
• On the sizes of the graphs \(G\), \(G^r\), \(G^r\setminus G\): the directed case
• Average degree in graph powers

Cited in

(6)

• Edge growth in graph squares
• On the sizes of graphs and their powers: the undirected case
• On the sizes of the graphs \(G\), \(G^r\), \(G^r\setminus G\): the directed case
• On growth triangular graphs
• scientific article; zbMATH DE number 1990713 (Why is no real title available?)
• Growth of graph powers

This page was built for publication: Edge growth in graph powers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2876017)