Large planar graphs with given diameter and maximum degree

DOI10.1016/0166-218X(94)00011-2zbMath0832.05060WikidataQ57360113 ScholiaQ57360113MaRDI QIDQ1897359

Michael R. Fellows, Pavol Hell, Karen Seyffarth

Publication date: 27 August 1995

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

zbMATH Keywords

diameterplanar graphmaximum degree

Mathematics Subject Classification ID

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

Related Items

On the maximum order of graphs embedded in surfaces ⋮ The degree-diameter problem for outerplanar graphs ⋮ Domination and dominator colorings in planar graphs with small diameter ⋮ Domination in planar graphs with small diameter* ⋮ Maximum size of a planar graph with given degree and diameter ⋮ The degree/diameter problem for mixed abelian Cayley graphs ⋮ New Moore-like bounds and some optimal families of abelian Cayley mixed graphs ⋮ The degree/diameter problem in maximal planar bipartite graphs ⋮ Maximum size of a planar graph with given degree and even diameter ⋮ \(N\)-separators in planar graphs ⋮ The degree-diameter problem for sparse graph classes ⋮ Largest planar graphs of diameter two and fixed maximum degree ⋮ The degree/diameter problem in maximal planar bipartite graphs ⋮ An improved Moore bound and some new optimal families of mixed abelian Cayley graphs ⋮ Largest planar graphs and largest maximal planar graphs of diameter two

Cites Work

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