✦ LIBER ✦

Constructions of large planar networks with given degree and diameter

✍ Scribed by Fellows, M.; Hell, P.; Seyffarth, K.

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 157 KB
Volume: 32
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199812)32:4<275::aid-net4>3.0.co;2-g

No coin nor oath required. For personal study only.

✦ Synopsis

There is considerable interest in constructing large networks with given diameter and maximum degree. In certain applications, there is a natural restriction for the networks to be planar. Thus, consider the problem of determining the maximum number of nodes in a planar network with maximum degree D and diameter at most k. We have previously proved that this number is at most (roughly) 12kD  k /2 and there is a trivial lower bound of about ( D 0 1)  k /2 . We introduce a number of general constructions which substantially improve the lower bound and yield the largest known networks. We also provide a catalog of the best-known networks for small values of D and k, many obtained by specialized constructions.

📜 SIMILAR VOLUMES

New large graphs with given degree and d

New large graphs with given degree and diameter six

✍ G�mez, J.; Pelayo, I.; Balbuena, C. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB 👁 1 views

In this paper, a method for obtaining large diameter 6 graphs by replacing some vertices of a Moore bipartite diameter 6 graph with complete K h graphs is proposed. These complete graphs are joined to each other and to the remaining nonmodified graphs by means of new edges and by using a special dia

Total colorings of planar graphs with la

Total colorings of planar graphs with large maximum degree

✍ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 2 views

It is proved that a planar graph with maximum degree ∆ ≥ 11 has total (vertex-edge) chromatic number ∆ + 1.