Transmission-Minimal Regular Graph

A transmission-minimal regular graph is a connected -regular graph on vertices whose graph transmission is minimum among all connected -regular graphs on vertices. Equivalently, for fixed and , such a graph minimizes the Wiener index and the mean distance.

The term is introduced here for this extremal class of graphs. Such graphs might also be described as extremal average-distance regular graphs or optimal average-distance regular graphs. A transmission-minimal regular graph should not be confused with a transmission-regular graph, which is a graph whose vertices all have the same vertex transmission. The word "regular" in transmission-minimal regular graph refers to vertex degree, not vertex transmission.

The same problem is posed for -regular graphs by Knor et al. (2019). Knor et al. (2016) conjecture that, among all -regular graphs on vertices, the minimum Wiener index is attained by a graph with the minimum possible diameter. Closely related computational problems arise in the order/degree problem and the Graph Golf competition, where fixed-degree graphs with small diameter and average shortest path length are sought (Kitasuka et al. 2018, Graph Golf 2021). Transmission-minimal regular graphs often have other extremal properties (Rokicki, pers. comm., May 11, 2026). In fact, many such graphs are among the smallest cubic crossing number graphs and smallest quartic crossing number graphs.

Counts of small transmission-minimal cubic graphs are summarized in the following table (Knor et al. 2019). The examples column lists named representatives where available and elides additional unnamed graphs. The minimum transmissions and counts in the cubic table are indexed by half the number of vertices.

vertices	count (OEIS A395987)	minimum transmission (OEIS A395986)	examples
4	1	6	tetrahedral graph
6	2	21	utility graph , 3-prism graph
8	2	44	Wagner graph and one other
10	1	75	Petersen graph
12	2	126	twinplex graph, triplex graph
14	7	189	Heawood graph, generalized Petersen graph , box graph, and 4 others
16	6	264	6 graphs
18	1	351	1 graph
20	1	450	1 graph
22	1	573	1 graph
24	1	708	McGee graph
26	2	871	CNG 9A, generalized Petersen graph

For the displayed cubic rows with vertices, the minimum transmissions are given by

(1)

Indeed, in a cubic graph on vertices, each vertex has three vertices at distance 1 and at most six at distance 2, so for every vertex and hence

(2)

Equality holds exactly when, for every vertex , there are six vertices at distance 2 from and all remaining vertices are at distance exactly 3. Equivalently, every vertex has distance distribution

(3)

The displayed , , and rows are exceptional, with minimum transmissions , , and , respectively (Knor et al. 2019; E. Weisstein, May 12-13 and 20, 2026).

Corresponding counts of small transmission-minimal quartic graphs are given below. The rows for are the table of Knor et al. (2019). The minimum transmissions and counts in the quartic table are indexed by the number of vertices.

vertices	count (OEIS A395989)	minimum transmission (OEIS A395988)	examples
5	1	10	pentatope graph
6	1	18	octahedral graph
7	2	28	circulant graph and one other
8	6	40	complete bipartite graph , rook graph , antiprism graph , and 3 others
9	16	54	circulant graphs and , generalized quadrangle , and 13 others
10	24	70	circulant graph and 23 others
11	37	88	Andrásfai graph and 36 others
12	26	108	circulant graph , Chvátal graph, quartic vertex-transitive graph Qt17, and 23 others
13	10	130	13-cyclotomic graph and 9 others
14	1	154	1 graph
15	1	180	1 graph
16	1	210	1 graph
17	2	247	2 graphs
18	1	283	1 graph

For a quartic graph on vertices, the analogous radius-two bound gives for every vertex , and so

(4)

Equality holds exactly when every vertex has all remaining non-neighbors at distance 2, i.e., when has diameter at most 2. This gives the quartic table values for . The rows , , and are exceptional; exhaustive enumeration gives the minimum transmissions , , and , respectively (Knor et al. 2019; E. Weisstein, May 12-13, 2026).