Graph of graphsThe pictures1 in this page represent the space of trivalent graphs with various number of vertices. This space has a natural geometry, namely, two graphs are close if they differ by a few local mutations.
More precisely, we can give the space of graphs the structure of a graph itself. Let GG(n) be the graph whose vertices are trivalent graph with n=2k vertices and two vertices are connected by an edge if the associated graphs differ by a single Whitehead move.
There are two Whitehead moves possible for every edge.
The graph GG(6).
Simple graphsA graph is called simple if it has girth at least 3 (no loops or double edges). It was shown by Coco Zhang2 that the subgraphs GG_simple(n) and GG_not_simple(n) are both connected. Hence to simplify our discussion, we concentrate on simple graphs only. We refer to GG_simple(n) = G(n) and to the subgraph of G(n) consisting of graphs of girth at least g by G(n,g).
Here are a few pictures of the graph of simple graphs. The vertices are colored by the girth of the associated graph as follows:
girth 3: blue; girth 4: green; girth 5: cyan; girth 6: magenta; girth 7: yellow; girth 8: red;
We define G(n,k) to be the subgraph of G(n) induced by the vertices(graphs) with girth ≥ k.
It seems like the "end" of G(n) is somewhat tree like. It is a question of McMullen whether this family of graphs is an expander family.
c-covered graphs and connectivity of G(n,k) 3To study the general rules of connectivity in G(n), we define the folowing term:
A graph is c-covered by short cycles (or "c-covered" for short) if every path of length c is contained in a cycle of length k, where k is the girth of graph.
The Desargues graph (n=20, girth=6) is 3-covered by short cycles.
The following pictures are two representations of Desargues graphs.
Therefore, if we pick a path P of length 3 in the Desargues graph, there exists an automorphism that maps the path to a-b-c-d depicted below. We see that there is a cycle of length 6 (a-b-c-d-e-f-a) containing the path a-b-c-d. Now, the inverse automorphism send the cycle a-b-c-d-e-f-a to a cycle that contain P. By a systole we mean a cycle that has a length equal to the girth of the graph. Thus any path of length 3 is contained in a systole and hence the Desargues graph is 3-covered.
|Graph name||Number of Vertices||Girth|
These special graphs are indicated in the plots of G(n) and G(n,k).
Generalized Petersen graph GP(3m+3, m) is 3-covered by short cycles, m ∈ N, m ≥5.
Consider the case when m=5, i.e. GP(18, 5). The length of the shortest cycle is 8, thus girth = 8. And there are two types of systoles in it.
a-a-a, a-a-b (b-a-a), a-b-c (c-b-a), b-c-c (c-c-b), b-c-b.
a-a-a, a-a-b(b-a-a), b-c-c is contained in Type I systole;
b-c-b is contained in Type II systole;
a-b-c(c-b-a) is contained in Type I or Type II systole, depending on orientation of c.
From the argument above, any path of length 3 in GP(18, 5) is contained in a cycle of length 8. Therefore, GP(18,5) is
3-covered by short cycles. This is also true for other values of m, m ∈ N, m ≥5.
In G(n), every 3-covered graph with girth k only connects to graphs with girth < k.
In other words, any Whithead move on 3-covered graph will decrease the girth.
Let g be a 3-covered graph with girth k in G(n). Then every path of length 3 is contained in a cycle of length k.
Now recall that G(n,k) is a subgraph of G(n) induced by the vertices (graphs) with girth ≥ k. If G(n,k) contains only vertices (graphs) of girth k and one of these graphs is 3-covered by short cycles, then the graph is contained in a disconnected component of G(n,k).
For convenience, if the subgraph G(n,k) is disconnected and the vertices (graphs) have j different levels of girths, we call this property of G(n,k) by j-level disconnectivity. G(18,6), G(20,6) and G(22,6) above are 1-level disconnected.
Here are two examples of 2-level disconnectivity.
G(24,6) contains vertices of girth 6 (cyan) and 7 (yellow)
G(30,7) contains vertices of girth 7 (yellow) and 8 (red)
It is a question of Ci whether the property of c-covered of the vertices (graphs) in G(n,k) is related to the level of disconnectivity of G(n,k). Does a greater value of c imply more disconnectivity levels?
Here is a table of the number of trivalent graphs of a given girth. 5
|Vertices||girth = 3||girth = 4||girth = 5||girth = 6||girth = 7||girth=8|
- 1- These pictures have been produce in collaboration with Roi Docampo, Jing Tao and Ci Zhang using Sage. ↩
- 2- In 2013, Coco Zhang was a high school junior at Branksome Hall. This work was done as part of the Math Mentorship Program at the University of Toronto during the winter of 2013.↩
- 3- This section is written by Ci Zhang as part of her Work Study during the Summer and Fall 2018. ↩
- 4- Biggs, N. L.; Smith, D. H. (1971), "On trivalent graphs", Bulletin of the London Mathematical Society, 3 (2): 155–158, see here. MR 0286693. ↩
- 5- Source: http://oeis.org/A198303. See also here ↩