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
(Jeremy Galvagni)

Largest Known Straight Line Planar
Triangular Graphs of a Given Diameter
(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
b < 2a
b ≥ 2a

(Gavin Theobald)
a+b > c
a+b ≤ c
a << b
2ac < a2+b2 < 2bc

(Gavin Theobald)
b = √3 a

(Gavin Theobald)
b = 1.985 a
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
{2} . . .
{4} . . .
{2,4} . . .
(Joe DeVincentis)
{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
(Gavin Theobald)
(Gavin Theobald)
(Gavin Theobald)
(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.