RADIUS OF 3-CONNECTED GRAPHS

Katsumi InoueSUT 1996 · DOI

This paper, published in the SUT Journal of Mathematics in 1996, provides a refined structural bound for a fundamental property in graph theory: the relationship between a graph's size and its "compactness," as measured by its radius.

TL;DR

The paper proves a new upper bound for the radius $r$ of a 3-connected graph with $n$ vertices, establishing that $r \leq \frac{n+15}{4}$. This result tightens previous asymptotic bounds, providing a concrete linear relationship that highlights how high connectivity forces a graph to expand its vertex count significantly to increase its radius.

What Problem Does This Paper Address?

In graph theory, the radius ($r$) of a graph is the minimum possible "maximum distance" from any single vertex to all others. Essentially, it measures how "central" the most central point is. A major question in structural graph theory is: How many vertices ($n$) do you need to achieve a certain radius, given specific connectivity constraints?

For a simple connected graph, the bound is trivial ($r \leq n/2$, like a path). However, as you increase connectivity—the minimum number of vertices that must be removed to disconnect the graph—the graph becomes more "tangled," making it harder to push vertices far away from each other without creating shortcuts.

Prior to this paper, researchers Harant and Walther had shown that for 3-connected graphs, the radius grows roughly as $n/4$, but their formula included an $O(\log n)$ error term. Katsumi Inoue aims to eliminate that ambiguity and provide a precise, non-asymptotic linear bound.

Methods

The author employs a layering technique (often called a BFS-layering or distance-partitioning).

  1. Distance Layers: Starting from a central vertex $z$, the vertices are partitioned into sets $X_i$ based on their distance $i$ from $z$.
  2. Connectivity Constraints: Because the graph is 3-connected, the author proves that every intermediate layer $X_i$ must contain at least 3 vertices (Lemma 2.1). If a layer had fewer, removing them would disconnect the graph, violating the 3-connectivity assumption.
  3. Averaging Argument: The core of the proof (Lemma 3.1) is a sophisticated counting argument. The author demonstrates that while some layers might only have 3 vertices, they cannot stay that small for long. By analyzing the local distances between vertices across multiple layers, the author proves that the "average" size of these layers must be at least 4.
  4. Proof by Contradiction: The author assumes the average layer size is less than 4 and then shows this would inevitably create a "shortcut" in the graph, which would contradict the original definition of the graph's radius.

Datasets

Not discussed in the paper. This is a theoretical work in pure mathematics; the results are proven through logical deduction and apply to all possible 3-connected graphs, rather than being tested on specific empirical datasets.

Key Insights and Ideas

  • The "Density" of 3-Connectivity: The most important insight is that 3-connectivity imposes a "minimum width" on the graph's structure. You cannot build a very "long and skinny" 3-connected graph without eventually adding enough vertices to make the average layer size $\geq 4$.
  • Local vs. Global Structure: The paper bridges the gap between local connectivity (how vertices are joined to their neighbors) and global metrics (the radius). It shows that the requirement to have three independent paths between any two points eventually forces the graph to consume vertices at a rate of at least 4 per unit of radius.
  • Refining the Constant: While previous work focused on the $n/4$ slope, this paper focuses on the "intercept" (the $+15$), providing a much clearer picture of the behavior of smaller or moderately sized graphs.

Key Results

  • The Main Theorem: For any 3-connected graph with $n$ vertices and radius $r$: $$r \leq \frac{n + 15}{4}$$
  • Improvement over Asymptotics: This result is a significant step over the previous $r < \frac{n}{4} + O(\log n)$ bound because it provides a specific constant (15) instead of a growing logarithmic term.
  • Lower Bound Comparison: The author notes that there exist constructions of 3-connected graphs where $r \approx \frac{n+4}{4}$. This means the new bound is very close to being "tight" (the best possible bound).

Limitations and Future Work

  • The Constant Gap: There is still a small gap between the proven upper bound ($+15$) and the known lower bound constructions ($+4$). The author explicitly mentions in the remarks that the proof could likely be extended to improve the bound to $r \leq \frac{n+12}{4}$.
  • Higher Connectivity: The paper specifically deals with 3-connected graphs. A natural extension would be to generalize this to $k$-connected graphs, where one might expect the denominator to increase as connectivity increases (i.e., the graph must become even "denser").

Summary updated

Abstract

We show that if G is a 3-connected graph with radius r, then r |V (G)|+15 4 .
BibTeX
@inproceedings{inoue1996radius,
  author = {Katsumi Inoue},
  title = {{RADIUS OF 3-CONNECTED GRAPHS}},
  booktitle = {SUT},
  year = {1996},
  doi = {10.55937/sut/1262208509},
}
Figure