Problem of the Month (February 2006)

This month we consider four graph theory problems, two that concern straight line planar graphs, and two that concern the farthest vertices from a given vertex.

Problem #1: A straight line planar graph is a graph with non-intersecting straight lines as edges. The diameter of a graph is the longest distance between a pair of vertices in the graph. What is the smallest diameter of a straight line planar graph with vertices in an m×n rectangle? Can you find a 13×13 graph with diameter 4? What are the minimal diameters for other rectangular graphs? What about triangular graphs?

Problem #2: Given a set of lengths (possibly repeated), what is the smallest straight line planar graph where every vertex is incident to edges of exactly those lengths?

Problem #3: A degree-distance graph is a graph where the degree of every vertex is equal to the number of vertices in the graph that are maximally distant from it. What are the small degree-distance graphs? For what sets do distance-degree graphs exist?

Problem #4: A vertex v2 is called the antipode of vertex v1 if v2 is the unique farthest vertex from v1. An antipode chain {v1, v2, . . . vn} is a list of vertices where vi+1 is the antipode of vi. What is the smallest graph with an antipode chain of length n? Do such graphs exist for every n?

Problem #1:

This problem ended up being too easy. Jeremy Galvagni showed that any rectangular or triangular graph can have diameter no larger than 4.

Joseph DeVincentis found the size 4 triangular graph with diameter 2, and a size 13 triangular graph with diameter 3.

Joseph Cooper found a 13×13 graph with diameter 4.

Largest Known Straight Line Planar
Rectangular Graphs of a Given Diameter
DiameterSizeGraph
11×2 23×3 35×n 4m×n (Jeremy Galvagni)

Largest Known Straight Line Planar
Triangular Graphs of a Given Diameter
DiameterSizeGraphs
12 24 314 4n (Jeremy Galvagni)

Problem #2:

Joseph DeVincentis found the minimal {a,a,b} graphs for b<2a.

Joseph DeVincentis also noted that the solutions for {1}, {1,1}, {1,1,1}, and {1,1,1,1} can be found in the Math Magic two months ago.

Smallest Known Straight Line Planar
Graphs With Given Incidences
Incidence SetGraph
{a} {a,a} {a,b} {a,a,a} {a,a,b}
b < 2a {a,a,b}
b ≥ 2a (Gavin Theobald)
{a,b,c}
a+b > c {a,b,c}
a+b ≤ c
a << b {a,b,c}
2ac < a2+b2 < 2bc (Gavin Theobald)
{a,a,a,b}
b = √3 a (Gavin Theobald)
{a,a,b,b}
b = 1.985 a {a,a,b,b}
b = 1.358 a (Gavin Theobald)

Problem #3:

Joseph DeVincentis noted that the complete graph Kn+1 is a {n} degree-distance graph, and that by joining two copies of Kn+1 at a vertex, we get a {n, 2n} degree-distance graph.

Joseph DeVincentis also proved that {1} and {1,2} are the only sets possible that contain 1, and that {n,n+1} degree-distance graphs always exist.

Known Degree-Distance Graphs
Degree SetGraphs
{1} {2}  . . .
{3}   {4}   . . . {1,2} {2,3} {2,4}  . . . {2,5} {3,4}  {3,6}  {3,7}?
{4,5} (Joe DeVincentis)
{4,6} {4,7}?
{4,8}   . . .

Problem #4:

Corey Plover found antipode chains for n≥5, using 2n – 5 + (n+1)/2  (n+5)/2 vertices.

Smallest Known Graphs With
Length n Antipode Chain
LengthGraph
2 3 4 5 (Gavin Theobald)
6 (Gavin Theobald)
7 (Gavin Theobald)
8 (Gavin Theobald)

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 2/14/06.