On the diameter of Kronecker graphs

DOI10.1016/J.DISC.2018.07.026MaRDI QIDQ1783634zbMATH OpenOpenAlexFDO

Authors Justyna Banaszak, Tomasz Łuczak

Publication date 21 September 2018

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

diameterconnectivityrandom graphsKronecker graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Connectivity (05C40)

Abstract: It is shown that a.a.s. as soon as a Kronecker graph becomes connected its diameter is bounded by a constant.

Recommendations

• On the diameter of Kneser graphs
• On the diameter of generalized Kneser graphs
• On \(k\)-diameter of \(k\)-connected graphs
• Tight bound on the diameter of the Knödel graph
• scientific article; zbMATH DE number 1696530
• On the \(k\)-diameter of \(k\)-regular \(k\)-connected graphs
• scientific article; zbMATH DE number 5054160
• The diameter of domination k‐critical graphs
• On the diameter of dot-critical graphs
• The diameter of cyclic Kautz digraphs

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• An in-depth analysis of stochastic Kronecker graphs
• Connectivity and giant component of stochastic Kronecker graphs
• Giant components in Kronecker graphs
• Kronecker graphs: an approach to modeling networks
• Stochastic Kronecker graphs

Cited in

(5)

• scientific article; zbMATH DE number 5054160 (Why is no real title available?)
• Krein parameters and antipodal tight graphs with diameter 3 and 4
• The diameter of cyclic Kautz digraphs
• The diameter of Hanoi graphs
• Diameters of graphs on reduced words of \(12\) and \(21\)-inflations

Describes a project that uses

Uses Software

• KronFit

This page was built for publication: On the diameter of Kronecker graphs

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