Edge growth in graph powers

zbMATH Open1296.05108arXiv1202.6085MaRDI QIDQ2876017FDOQ2876017

Authors: Alexey Pokrovskiy 

Publication date: 15 August 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1202.6085

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

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)

Cited In (6)

• On the sizes of graphs and their powers: the undirected case
• Growth of graph powers
• On growth triangular graphs
• Edge growth in graph squares
• Title not available (Why is that?)
• On the sizes of the graphs \(G\), \(G^r\), \(G^r\setminus G\): the directed case

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)