Large planar graphs with given diameter and maximum degree
type: Item
instance of: scholarly article
title: Large planar graphs with given diameter and maximum degree
zbMATH Open document ID: 0832.05060
DOI: 10.1016/0166-218X(94)00011-2
author: Michael R. Fellows
author: Pavol Hell
author: K. Seyffarth
published in: Discrete Applied Mathematics
publication date: 1995-08-27T00:00:00Z
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\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 790496
zbMATH Keywords: planar graph
zbMATH Keywords: maximum degree
zbMATH Keywords: diameter
Wikidata QID: Q57360113
MaRDI profile type: Publication
cites work: On a problem of a. kotzig concerning factorizations of 4‐regular graphs
cites work: Constructions of large planar networks with given degree and diameter
cites work: Largest planar graphs of diameter two and fixed maximum degree
cites work: A Separator Theorem for Planar Graphs
DBLP publication ID: journals/dam/FellowsHS95
description: scientific article; zbMATH DE number 790496