𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximal planar graphs of diameter two

✍ Scribed by Karen Seyffarth

Publisher
John Wiley and Sons
Year
1989
Tongue
English
Weight
1020 KB
Volume
13
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A maximal planar graph is a simple planar graph in which every face is a triangle. We show here that such graphs with maximum degree A and diameter two have no more than :A + 1 vertices. We also show that there exist maximal planar graphs with diameter two and exactly LiA + 1 J vertices.

πŸ“œ SIMILAR VOLUMES

Two trees in maximal planar bipartite gr
Two trees in maximal planar bipartite graphs
✍ Gerhard Ringel πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 127 KB

## Abstract It is proven that each maximal planar bipartite graph is decomposable into two trees. Β© 1993 John Wiley & Sons, Inc.

Maximal and Minimal Vertex-Critical Grap
Maximal and Minimal Vertex-Critical Graphs of Diameter Two
✍ Jing Huang; Anders Yeo πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 446 KB

A graph is vertex-critical if deleting any vertex increases its diameter. We construct, for each & 5 except &=6, a vertex-critical graph of diameter two on & vertices with at least , where c 2 is some constant. We also construct, for each & 5 except &=6, a vertex-critical graph of diameter two on &

Maximal chromatic polynomials of connect
Maximal chromatic polynomials of connected planar graphs
✍ Ioan Tomescu πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 429 KB πŸ‘ 1 views

## Abstract In this paper we obtain chromatic polynomials of connected 3‐ and 4‐chromatic planar graphs that are maximal for positive integer‐valued arguments. We also characterize the class of connected 3‐chromatic graphs having the maximum number of __p__‐colorings for __p__ β‰₯ 3, thus extending a

On the connectivity of maximal planar gr
On the connectivity of maximal planar graphs
✍ S. L. Hakimi; E. F. Schmeichel πŸ“‚ Article πŸ“… 1978 πŸ› John Wiley and Sons 🌐 English βš– 254 KB πŸ‘ 1 views
Reduced graphs of diameter two
Reduced graphs of diameter two
✍ Hong-Jian Lai πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 444 KB

## Abstract A graph __H__ is __collapsible__ if for every subset X βŠ† __V(H), H__ has a spanning connected subgraph whose set of odd‐degree vertices is X. In any graph __G__ there is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction