×

Compact generalized polygons and Moore graphs as stable graphs. (English) Zbl 1262.05034

In this paper the notion of a stable graph is introduced, and various results are proved about the class of stable graphs.
For a graph \(\mathcal{G} = (V,E)\) and an integer \(k \geq 2\), define \(D_k\) to be the set of all pairs of vertices which are distance \(k\) apart. The graph \(\mathcal{G}\) is called \(k\)-stable if the girth of \(\mathcal{G}\) is greater than \(2k\), all vertices are adjacent to at least three others, and if \(V\) carries a topology such that \(D_k\) is open in \(V^2\) and the map
\[ f : D_k \to V_{k+1},\;(v,w)\mapsto p, \]
where \(p\) is the unique path from \(v\) to \(w\), is continuous. A graph is called stable if it is \(k\)-stable for some \(k\).
The two most interesting classes of stable graphs are the compact Moore graphs (a Moore graph is a graph with finite diameter \(d \geq 2\) and girth \(2d+1\)), and a certain subclass of the compact generalized polygons (a generalized polygon is a bipartite graph with finite diameter \(d \geq 3\) and girth \(2d\)). These two classes of graph occur in many settings and have been much studied.
Let us illustrate the tenor of this interesting paper with two results. Suppose that \(\mathcal{G} = (V,E)\) is a stable graph.
The first result states that if the topology on \(V\) is discrete, then \(\mathcal{G}\) is \(k\)-stable for any \(k\), while if the topology on \(V\) is non-discrete, then \(\mathcal{G}\) is \(k\)-stable for a unique value of \(k\).
Suppose in addition that \(\mathcal{G}\) is graph-connected, locally connected and non-discrete. The second result states that the following statements are equivalent:
(1)
\(\mathcal{G}\) is a generalized polygon, and the vertex set is locally compact.
(2)
The vertex set is compact, and the adjacency relation is closed.
(3)
All panels are compact.
An interesting corollary to this result gives conditions under which an infinite stable Moore graph is homeomorphic to the Cantor set.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
51E12 Generalized quadrangles and generalized polygons in finite geometry
51H10 Topological linear incidence structures
PDFBibTeX XMLCite