Structure and pancyclicity of maximal planar graphs with diameter two.

A graph G on n vertices is called non-universal if its maximum degree is at most n - 2 . In this paper, we give a structural characterization for non-universal maximal planar graphs with diameter two. In precise, we find 10 basic graphs, and then generate all 25 non-universal maximal planar graphs with diameter two by adding repeatedly and appropriately 3-vertices to some of these 10 basic graphs. As an application, we show that maximal planar graphs with diameter two are pancyclic except five special graphs. [ABSTRACT FROM AUTHOR]