The degree-diameter problem for sparse graph classes

MaRDI QIDQ491538zbMATH OpenFDO

Authors Guillermo Pineda-Villavicencio, David R. Wood

Publication date 26 August 2015

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

Full work available at URL https://arxiv.org/abs/1307.4456, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p46

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

apex-minor-free grapharboricitydegree-diameter problemsparse graphsurface graphtreewidth

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: The degree-diameter problem asks for the maximum number of vertices in a graph with maximum degree $Delta$ and diameter $k$. For fixed $k$, the answer is $Theta(Delt{a}^k)$. We consider the degree-diameter problem for particular classes of sparse graphs, and establish the following results. For graphs of bounded average degree the answer is $Theta(Delt{a}^{k-1})$, and for graphs of bounded arboricity the answer is $Theta(Delt{a}^{floork/2})$, in both cases for fixed $k$. For graphs of given treewidth, we determine the the maximum number of vertices up to a constant factor. More precise bounds are given for graphs of given treewidth, graphs embeddable on a given surface, and apex-minor-free graphs.

Review text

Summary: The degree-diameter problem asks for the maximum number of vertices in a graph with maximum degree \(\Delta\) and diameter \(k\). For fixed \(k\), the answer is \(\Theta(\Delta^k)\). We consider the degree-diameter problem for particular classes of sparse graphs, and establish the following results. For graphs of bounded average degree the answer is \(\Theta(\Delta^{k-1})\), and for graphs of bounded arboricity the answer is \(\Theta(\Delta^{\lfloor k/2\rfloor})\), in both cases for fixed \(k\). For graphs of given treewidth, we determine the maximum number of vertices up to a constant factor. Other precise bounds are given for graphs embeddable on a given surface and apex-minor-free graphs.

Recommendations

• Moore graphs and beyond: a survey of the degree/diameter problem
• The degree-diameter problem for outerplanar graphs
• Large graphs with given degree and diameter. II
• Degree/diameter problem for trees and pseudotrees
• Some large graphs with given degree and diameter

Cites work

• \(N\)-separators in planar graphs
• A partial k-arboretum of graphs with bounded treewidth
• An extremal function for contractions of graphs
• Arc colorings of digraphs
• Asymptotically large (\(\Delta,D\))-graphs
• Constructions of large planar networks with given degree and diameter
• Decomposition of Finite Graphs Into Forests
• Diameter and treewidth in minor-closed graph families
• Diameter and treewidth in minor-closed graph families, revisited
• Equivalence of local treewidth and linear local treewidth and its algorithmic applications
• Graphs on surfaces
• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• scientific article; zbMATH DE number 4021187 (Why is no real title available?)
• scientific article; zbMATH DE number 3540357 (Why is no real title available?)
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 2044937 (Why is no real title available?)
• scientific article; zbMATH DE number 2172769 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Large planar graphs with given diameter and maximum degree
• Largest planar graphs of diameter two and fixed maximum degree
• LATIN 2004: Theoretical Informatics
• Layered separators in minor-closed graph classes with applications
• Line Digraph Iterations and the (d, k) Digraph Problem
• Local tree-width, excluded minors, and approximation algorithms
• Maximum size of a planar graph with given degree and even diameter
• Moore graphs and beyond: a survey of the degree/diameter problem
• Normal Recurring Decimals
• On a problem of a. kotzig concerning factorizations of 4‐regular graphs
• On the maximum order of graphs embedded in surfaces
• The extremal function for complete minors

Cited in

(8)

• Degree/diameter problem for trees and pseudotrees
• On the maximum order of graphs embedded in surfaces
• scientific article; zbMATH DE number 5309966 (Why is no real title available?)
• Maximizing line subgraphs of diameter at most \(t\)
• Algebraic and computer-based methods in the undirected degree/diameter problem - A brief survey
• scientific article; zbMATH DE number 6784973 (Why is no real title available?)
• The degree/diameter problem in maximal planar bipartite graphs
• Constructions of large graphs on surfaces

This page was built for publication: The degree-diameter problem for sparse graph classes

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