Research

Associate Professor, Mathematics / Dept. Chair
Mathematics, School of Science & Technology
902.563.1181

http://faculty.cbu.ca/jpreen/
Office: A129A

My research is into Graph Theory, my recent publications have been on the subject of the domination polynomial of graphs. I have previously researched on planar and toroidal regular graphs, in particular distance and 5-regular graphs.


The (Degree, Diameter) Problem for Planar Graphs

We consider only the special case when the graph is planar. If the graph
is also regular, Euler’s formula implies that the maximum degree
(degree) Δ can be at most 5. Each entry in the first table is either a single number
or a closed interval [lower bound, upper bound] containing the order (number
of vertices) of the largest planar Δ-regular graph with diameter D. In all cases, the lower bound arises from the construction of a graph. If an entry consists of a single number, the lower and upper bounds are known to be the same.


LOWER AND UPPER BOUNDS FOR LARGEST PLANAR REGULAR (Δ,D)-GRAPHS (30th October, 2005)

Δ
\ D
1 2 3 4 5 6 7 8
1 2 none none none none none none none
2 3 5 7 9 11 13 15 17
3 4 6 12 [18, 30] [28, 62] [36, 122] [52, 244] [76, 488]
4 none 9 [16, 33] [27,
96]
[44, 291] [81, 867] [134, 2595] [243, 7779]
5 none none 16 [28,
248]
[62, 984] [124,
3928]
[254, 11294] [500, 62808]

 

To confirm the first two rows and extend them infinitely to the right, note that K2 is the only connected (equivalently, finite diameter) 1-regular graph and that cycles are the only connected 2-regular graphs.

To check that the first column is correct, note that the diameter-1 graphs are exactly the complete graphs (by definition) and that both K5 and K6 are nonplanar.

The proof that the 16 vertex 5-regular graph is indeed the largest one of diameter 3 was completed by James Preen
in June 2005 and is published.

The upper bound for (5,7) comes from the following paper:

M. Fellows, P. Hell, and K. Seyffarth. Large planar graphs with given
diameter and maximum degree. Disc. Appl. Math. 61 (1995),
133-153. MR 96e:05081.

The
lower bound

for (5,4) comes from a set of 54 graphs (the one illustrated has radius 3)
constructed by James Preen, who also constructed the (4,4) graph which has now been proven to be one of six 4-regular planar graphs with diameter 4 and 27 vertices.

Additionally, using plantri it has been established that there exist no 4-regular planar graphs with 28 vertices and similarly
there are no 3-regular planar graphs with diameter 4 with between 20 and 30
vertices.

Most of the previously best-known lower bounds and a proof of the non-existence
of (5,2) can be found in the following paper:

F. Göbel and W. Kern. Planar regular graphs with prescribed diameter.
Univ. of Twente (The Netherlands) Applied Math. Memorandum No. 1183, December
1993.

The lower bounds for (3,D), D ≥ 6; (4,D), D ≥ 5; and (5,D),
D ≥ 5 arose from Pratt and Friedman
improving the constructions of Göbel and Kern.

The lower bound for (4,D), D even and ≥ 4, given without proof
in Proposition
3.2(c) in the Göbel/Kern paper, should be
8*3D/2-1-2. Also, the
lower bound for (4,D), D odd and ≥ 5, should be
4*3(D-1)/2-2.
These
corrections have been verified by Frits Göbel, but
Erich
Friedman
and Rob Pratt
have improved the bounds, as reflected in this table:

Please send any updates or corrections to james_preen at capebretonu.ca

Page originally compiled by Rob Pratt and
rescued from the internet archive in 2005.