Large planar graphs with given diameter and maximum degree

DOI10.1016/0166-218X(94)00011-2MaRDI QIDQ1897359zbMATH OpenDBLPWikidataFDO

Authors Michael R. Fellows, Pavol Hell, K. Seyffarth

Publication date 27 August 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(94)00011-2

zbMATH Keywords

diametermaximum degreeplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Extremal problems in graph theory (05C35)

Review text

Let \(G\) be a planar graph on \(n\) vertices with maximum degree \(\Delta\) and diameter \(k\). The problem of determining the maximum number of vertices that \(G\) can have is studied in this paper. When \(k= 2\), it has been shown that \(n\leq \lfloor{3\over 2}\Delta\rfloor+ 1\) (for \(\Delta\geq 8\)). In this paper, the authors show that when \(k= 3\), we have \(\lfloor {9\over 2} \Delta\rfloor- 3\leq n\leq 8\Delta+ 12\). They also show that in general \(n\) is \(\Theta(\Delta^{\lfloor k/2\rfloor})\) for any fixed value of \(k\).

Recommendations

• Largest planar graphs of diameter two and fixed maximum degree
• Largest planar graphs and largest maximal planar graphs of diameter two
• Maximum size of a planar graph with given degree and even diameter
• scientific article; zbMATH DE number 1932947
• New constructions of large scale planar networks with given diameter and maximum degree

Cites work

• A Separator Theorem for Planar Graphs
• Constructions of large planar networks with given degree and diameter
• Largest planar graphs of diameter two and fixed maximum degree
• On a problem of a. kotzig concerning factorizations of 4‐regular graphs

Cited in

(30)

• The maximum sum of degrees above a threshold in planar graphs
• Largest planar graphs and largest maximal planar graphs of diameter two
• Structure and pancyclicity of maximal planar graphs with diameter two
• New Moore-like bounds and some optimal families of abelian Cayley mixed graphs
• The degree-diameter problem for outerplanar graphs
• The degree/diameter problem for mixed abelian Cayley graphs
• On the maximum order of graphs embedded in surfaces
• New constructions of large scale planar networks with given diameter and maximum degree
• Some large graphs with given degree and diameter
• Domination in planar graphs with small diameter*
• Constructions of large planar networks with given degree and diameter
• Large circulant graphs of fixed diameter and arbitrary degree
• scientific article; zbMATH DE number 1932947 (Why is no real title available?)
• scientific article; zbMATH DE number 1892890 (Why is no real title available?)
• The degree-diameter problem for sparse graph classes
• Plane graphs with large faces and small diameter
• Maximum size of a planar graph with given degree and diameter
• Combinatorial Geometry and Graph Theory
• The degree/diameter problem in maximal planar bipartite graphs
• On a problem of a. kotzig concerning factorizations of 4‐regular graphs
• The degree/diameter problem in maximal planar bipartite graphs
• Existential closure in line graphs
• Maximum size of a planar graph with given degree and even diameter
• \(N\)-separators in planar graphs
• Largest planar graphs of diameter two and fixed maximum degree
• The degree-diameter problem for plane graphs with pentagonal faces
• An improved Moore bound and some new optimal families of mixed abelian Cayley graphs
• Large graphs with given degree and diameter. II
• Domination and dominator colorings in planar graphs with small diameter
• Classification of regular planar graphs with diameter two

This page was built for publication: Large planar graphs with given diameter and maximum degree

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