Transmission-Minimal Regular Graph

A transmission-minimal regular graph is a connected -regular simple graph on vertices whose graph transmission is minimum among all connected -regular simple 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) conjectured 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, up to graph isomorphism, are summarized in the following table. The rows for 6 through 22 vertices are given by Knor et al. (2019, p. 128). The examples column lists named representatives where available and elides additional unnamed graphs. The counts (OEIS A395987) and minimum graph transmissions (OEIS A395986) are indexed by half the number of vertices.

vertices	count	minimum transmission	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 graph transmissions are given by

(1)

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

(2)

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

(3)

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

Corresponding counts of small transmission-minimal quartic graphs, up to graph isomorphism, are given below. The rows for 6 through 17 vertices are given by Knor et al. (2019, p. 129). The counts (OEIS A395989) and minimum graph transmissions (OEIS A395988) are indexed by the number of vertices.

vertices	count	minimum transmission	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 connected quartic graph on vertices, counting its four neighbors and non-neighbors gives for every graph vertex , and so

(4)

Equality holds exactly when every graph 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 graph transmissions , , and , respectively (Knor et al. 2019; E. Weisstein, May 12-13, 2026).