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