**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:

- The Watts-Strogatz model (with underlying regular ring lattice)
- The Barabasi-Albert model (with preferred attachment)
- The Configuration model (with given degree sequences, resp. distributions)
- The Newman model (incorporating community structure)

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:

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**

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.}If there are non-realizable vertex configurations: How do I check if a given vertex configuration is realizable?

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

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.)

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$.