# Structures for random graphs with structure

Background
[You may skip this and go immediately to the Definitions.]

Crucial features of a (random) graph or network are:

• the degree distribution $$p(d)$$ (exponential, Poisson, or power law)

• the mean degree $$\bar{d}$$

• the mean clustering coefficient $$\bar{C}$$

• the mean distance $$L$$ and diameter $$D$$

Randomly generated graphs often are required to exhibit the small-world property, i.e. $$L\propto \log N$$ and $$\bar{C}$$ is “not small”. There are several random graph models that address at least one of these conditions:

While the Watts-Strogatz and the Barabasi-Albert model are modifications of the Erdős–Rényi model, and the Newman model is a specific generalization of the configuration model, I wonder if there is already a "meta-model" that tries to incorporate the best of all of these models. (Reference request.)

Generalizing both Watts-Strogatz's and Newman's model, I'd like to investigate random graphs that "interpolate between a randomized structure close to ER graphs and [some arbitrary regular graph]" (quote from Wikipedia).

For this, I'd like to have at hand a multitude of regular graphs which can

• be systematically symbolized and enumerated,

• be easily generated from their symbol (i.e. their adjacency matrices), and

• possibly have closed form expressions for the small-world characteristics $$L$$ and $$\bar{C}$$

Which regular graphs I have in mind can most easily be explained by an example.

Definitions

Let a vertex configuration be a graph that represents a vertex $$\nu$$ with a number of immediate neighbours $$\nu_0,\nu_2,\dots,\nu_{d-1}$$ and a shortest path (of arbitrary length) between each pair of consecutive neighbours $$\nu_i, \nu_{i+1}$$. A vertex configuration can be codified by the symbol $$(n_1.n_2.\dots.n_k)^m$$ which tells, that $$\nu$$ has degree $$d = m \cdot k$$ and is surrounded by an $$m$$-periodic sequence of $$n_i$$-faces resp. shortest cycles. (This is nothing but the standard definition of vertex configurations in geometry in the language of graph theory.)

Example:

$$(4)^4$$

A vertex is said to have a given vertex configuration $$\Gamma$$ when its neighbourhood together with one shortest path between neighbours is isomorphic to $$\Gamma$$. A graph is said to have a given vertex configuration $$\Gamma$$ when all of its vertices have vertex configuration $$\Gamma$$. A vertex configuration is said to be realizable when there is a graph that has it.

Now consider finite graphs in which all vertices have the same vertex configuration.

Questions

1. Are all vertex configurations $$\Gamma$$ realizable by graphs of more or less arbitrary size? How to prove or disprove this?
This has to do with the question if all vertex configurations (in the sense of geometry) which don't define a periodic tiling of the sphere (i.e. a regular polyhedron) define a periodic tiling of the Euclidean or hyperbolic plane.

2. If there are non-realizable vertex configurations: How do I check if a given vertex configuration is realizable?

3. Does a graph with a given vertex configuration $$\Gamma$$ have to be vertex-transitive?

4. Since the (equal) number of vertices of two vertex-transitive graphs with the same vertex configuration doesn't guarantee that they are isomorphic: By which general means can their "shape" be defined, so that two equally defined graphs must be isomorphic? (For an example: see below.)

5. Is there a systematic way to generate an adjacency matrix for a given realizable vertex configuration and "shape"?

With "shape" I mean what Dolbilin and Schulte call "neighborhood complexes (coronas)" in their paper The Local Theorem for Monotypic Tilings.

Examples

Consider the vertex configuration $$(4)^4$$ and a "shape" defined by numbers $$(4, 6)$$

When linking vertices on opposite sides of the shape all vertices have the same vertex configuration $$(4)^4$$, moreover the resulting graph is vertex-transitive:

We find diameter $$D = 5$$, clustering coefficient $$\bar{C} = 0$$, and mean distance $$L =\frac{1}{23}(4\times 1 + 7 \times 2 + 7 \times 3 + 4 \times 4 + 1 \times 5) \approx 2.61$$ for which to find a closed or recursive explicit expression (depending on $$(n,m)$$) seems to be feasible.

For the "shape"

with the same vertex configuration and number of vertices we find $$D = 5$$ and mean distance $$L =\frac{1}{23}(4\times 1 + 6 \times 2 + 6 \times 3 + 5 \times 4 + 2 \times 5) \approx 2.78$$

For the "shape"

with roughly the same number of vertices we find $$D = 4$$ and mean distance $$L =\frac{1}{24}(4\times 1 + 8 \times 2 + 8 \times 3 + 4 \times 4 ) \approx 2.5$$.

If you want a cluster coefficient $$\bar{C} = 1/2$$ you can start with a vertex configuration $$(3.n)^m$$, e.g. $$(3.4)^2$$:

Unfortunately, this configuration does not qualify because it doesn't tile a plane but the sphere (giving rise to the cuboctahedron). So you have to choose $$(3.4)^3$$ at least. To draw a nice "shape" of some size that can be made into a finite graph with vertex configuration $$(3.4)^m$$, $$m > 2$$, requires hyperbolic geometry. To find an adjacency matrix is even harder, as I guess (see question 5). Also the diameter $$D$$ and mean distance $$L$$ (as closed expressions).

Alternatively, one can add an edge to half of the $$n\cdot m$$ $$4$$-cycles (randomly chosen) of the $$(4)^4$$ graph - thus reducing diameter $$D$$ and mean distance $$L$$.

The following vertex configuration has notation $$(3.4.4.4)^1$$ and should provide counterexamples to question 1 (existence of graphs of arbitrary size) and question 3 (vertex-transitivity).

There are only finitely many graphs that realize this configuration, and all of them are finite with at most 24 vertices. Exactly two of them are planar, the edge-graph of rhombicuboctahedron (left), and the edge-graph of the closely related pseudo-rhombicuboctahedron (right). Only the first one is vertex-transitive.

All other graphs can be obtained from these by identifying vertices. For example, identifying antipodal vertices in the left graph gives a "projective polyhedron":

I highlighted the vertex configuration in the right image because it is not obvious in this drawing.

I think these are all the graphs with this configuration. I might be wrong, but there are certainly no such graphs with more than 24 vertices.

More generally, you might be interested in the Local Theorem from

which is concerned with the question when certain local restrictions imply global symmetry. Usually, it gives uniqueness and vertex-transitivity, but it only applies if the topology is "simply connected" (so, for tilings of the sphere, Euclidean/hyperbolic plane, but not for the torus, as you have seen in your question that the graph is not unique for $$(4)^4$$).

In the start of Section 3 (below Theorem 3.1) they state that the configuration $$(3.5.5.5)^1$$ can be realized as an infinite graph, but not as a vertex-transitive one. I have tried to track down this claim, but they only refer to the book "Tilings and Patterns" which contains literally thousands of tilings, and I was not able to find the desired one.

Finally, the following configuration $$(3.4.5)^1$$ should not be realizable at all:

To see this, note that the graph must contain a "triangular face" (since the configuration does). Each of the three edges of that triangle is shared either with a quadrangle, or a pentagon. W.l.o.g. assume that two edges are shared with a quadrange. But these two edges share a vertex, and so this vertex cannot be of type $$(3.4.5)^1$$.

In general it seems quite tricky to distinguish the realizable from the non-realizable configurations. As a rule of thumb, it seems that odd-faces pose a problem, similarly as they did in the previous example. So, e.g. a configuration $$(\mathbf 5.8.10)^1$$ cannot exist either for the same reason, as there is a pentagonal face that bounds two different kinds of faces, and there is no face-type repeated at a vertex.

Since you mention (in the comments) that you are mostly interested in $$(3.n)^m$$ (assuming $$n\ge 3$$, $$m\ge 2$$):

This configuration always exists, is unique and vertex-transitive (assuming a "simply connected topology", which we can translate as "the graph is planar").

It is finite only for $$(3.3)^2$$ (octahedron), $$(3.4)^2$$ (cuboctahedron) and $$(3.5)^2$$ (icosidodecahedron). You can consider it "planar" for $$\smash{(3.3)^3}$$ (triangular tiling) and $$\smash{(3.6)^2}$$ (trihexagonal tiling), and hyperbolic in all other cases.

The uniqueness and symmetry is essentially a consequence of the Local Theorem (and the related Extension Theorem) mentioned before. But in easy terms: if you try to build a graph with such a vertex configuration, and you start from any vertex, and then you try to complete the vertex configuration around any of the other vertices, you can do this only in a unique way (really, try it on paper). Since you make no choice in any (of the possibly infinitely many) steps, the result is unique.

• Thanks, your answer is relevant in two respects: First, it shows that a graph that realizes a configuration doesn't have to be vertex-transitive. (That's important for me to know, and it answers question 3) Second it shows that there are (of course) configurations that tile only the sphere (defining a polyhedron) but not a plane. This case was excluded in the remark to question 1. Aug 18 '20 at 13:15
• Do you have a tool at hand that draws graphs for given configurations? Aug 18 '20 at 13:20
• @Hans-PeterStricker Sadly no, I always do it by hand. Aug 18 '20 at 13:25
• @Hans-PeterStricker The graph with configuration $(3.n)^m$ exists, is unique and vertex-transitive. I edited my answer. Aug 18 '20 at 15:36
• @Hans-PeterStricker Okay, uniqueness is a lie. Imagine that you can build finite graphs of type $(3.3)^3$ by wrapping around the tiling to a torus as you did with $(4)^4$. The Local Theorm assumes that the "topology is simply connected" (e.g. sphere, Euclidean/hyperbolic plane). Similar wrapping might be possible in the spherical and hyperbolic case. I am not sure what this does to vertex-transitivity, but I am optimistic that it is preserved. I might edit the answer later. Aug 18 '20 at 15:46