Transmission-Minimal Regular Graph

A transmission-minimal regular graph is a connected r-regular graph G on n vertices whose graph transmission T(G) is minimum among all connected r-regular graphs on n vertices. Equivalently, for fixed n and r, 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 r-regular graphs by Knor et al. (2019). Knor et al. (2016) conjecture that, among all r-regular graphs on n 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.

For the displayed cubic rows with 10<=n<=20 vertices, the minimum transmissions are given by

Indeed, in a cubic graph on n>=10 vertices, each vertex has three vertices at distance 1 and at most six at distance 2, so T(u)>=3n-15 for every vertex u and hence

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

The displayed n=22, n=24, and n=26 rows are exceptional, with minimum transmissions 573=(3n(n-5))/2+12, 708=(3n(n-5))/2+24, and 871=(3n(n-5))/2+52, 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 n>=6 are the r=4 table of Knor et al. (2019). The minimum transmissions and counts in the quartic table are indexed by the number of vertices.

For a quartic graph G on n<=17 vertices, the analogous radius-two bound gives T(u)>=2n-6 for every vertex u, and so

Equality holds exactly when every vertex has all remaining n-5 non-neighbors at distance 2, i.e., when G has diameter at most 2. This gives the quartic table values for 5<=n<=15. The rows n=16, n=17, and n=18 are exceptional; exhaustive enumeration gives the minimum transmissions 210=16(16-3)+2, 247=17(17-3)+9, and 283=18(18-3)+13, respectively (Knor et al. 2019; E. Weisstein, May 12-13, 2026).

See also

Explore with Wolfram|Alpha

References

Cite this as:

Weisstein, Eric W. "Transmission-Minimal Regular Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Transmission-MinimalRegularGraph.html

Subject classifications