Edge growth in graph squares

MaRDI QIDQ2855624zbMATH OpenFDO

Authors Michael Goff

Publication date 25 October 2013

Published in Integers (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.5157, http://www.emis.de/journals/INTEGERS/papers/n42/n42.Abstract.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graph squarenarrow familyregular graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: We resolve a conjecture of Hegarty regarding the number of edges in the square of a regular graph. If $G$ is a connected $d$-regular graph with $n$ vertices, the graph square of $G$ is not complete, and $G$ is not a member of two narrow families of graphs, then the square of $G$ has at least $(2-o_d(1))n$ more edges than $G$.

Recommendations

• Edge growth in graph powers
• scientific article; zbMATH DE number 1248190
• On the Edge-Expansion of Graphs
• On the square of a Hamiltonian cycle in dense graphs
• The square of paths and cycles

Cited in

(5)

• Edge growth in graph powers
• scientific article; zbMATH DE number 1248190 (Why is no real title available?)
• scientific article; zbMATH DE number 1545700 (Why is no real title available?)
• Growth of Edge-Homogeneous Tessellations
• Growth of graph powers

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

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