6
$\begingroup$

I am looking for an (if possible constructive) classification of those finite, simple graphs (no loops, no multi-edges), where the open neighbourhood of each vertex (excluding that vertex aka open neighbourhood) is isomorphic to $C_7$; equivalently, where the closed neighbourhood of each vertex including that 'central' vertex is isomorphic to the wheel graph $W_8$ with 7 spokes

W8 graph

Alternatively, theses graphs are called 'locally $C_7$ (open)'.

Is there a classification of the finite, simple graphs that are locally $C_7$ (open neighbourhood definition)?

I understand that there is some relationship to triangulations or 'polyhedral realizations' of Hurwitz surfaces (https://en.wikipedia.org/wiki/Hurwitz_surface) that exist only for certain values of the genus (https://oeis.org/A179982); which would suggest a respective infinite set of locally $C_7$ graphs.

References

Examples

  1. The 7-regular Klein graph has 24 vertices and 84 edges - also see https://houseofgraphs.org/graphs/1198. The graph automorphism group has order 336 and can be embedded in the genus-3 orientable surface. One of the 'best ways looking' at the graph is embedded in an order-7 triangular tiling identifying certain vertices on the border of the disk Klein graph
  2. The self-intersection-free, polyhedral realization of the Hurwitz surface of genus 7 aka Macbeath surface or Fricke-Macbeath surface with 72 vertices, 252, edges, 168 triangles and automorphism group of order 1008 (including orientation-reversing automorphisms) - see https://houseofgraphs.org/graphs/52273 Fricke-Macbeath graph

Additional example

  1. The paper in the reference provides a $C_7$ graph with 36 vertices, 126 edges, 84 triangles and graph automorphism group of order 7. The genus is unknown.

Here the 'high dimensional embedding'

Graph[ImportString[">>graph6<<cvjCSLgUI@G`GG?Ie?@?DCC?O?gO_??_SI?A@OP?GGO?_Cb?BCO?AO_?@@HW?EH_?_c???AA`WA@aC?E@?GS?CKgO?OOsO_CG`CP???@lg\n", "Graph6"], GraphLayout->"HighDimensionalEmbedding"]

C7 graph w 36 vertices

This example suggests that there are many more locally $C_7$ graphs - just not maximizing the automorphism group order for a given genus (the ones maximizing are the Hurwitz surfaces - examples 1 and 2 above).

References

One more example

  1. I found this one actually in a listing of symmetric graphs by Marston Conder at https://www.math.auckland.ac.nz/~conder/. It has also 36 vertices, 126 edges, 84 triangles, graph automorphism group of order 504 and can be found in house of graphs at https://houseofgraphs.org/graphs/52182. The genus is unknown.

another 36 vertex one

It looks 'different' in this 'higher dimensional embedding'...

Graph[CanonicalGraph[EdgeList[Graph[ImportString["c}a[TC??G??@?A?H?AQ@_OGSGIOCSOGW?_O`AB@@@_@a?g??Og@@@OO?OSO?`A?H?SG?pOASE?W_gAR?OV??I_?WoGP?F_?g@B@_?WHOH?", "Graph6"]]]], GraphLayout->"HighDimensionalEmbedding"]

another 36 vertex graph in other embedding

$\endgroup$
8
  • 2
    $\begingroup$ Do you mean that for each $v\in V(G)$, the subgraph induced by $N(v)$ is $C_7$? Not just that $N(v)$ contains a $C_7$, I presume. $\endgroup$ Commented May 22 at 0:47
  • 2
    $\begingroup$ Hi Shou, yes, the subgraph induced by $N(v)$; not 'more' than $C_7$ in the open neighbourhood of each vertex $v$. $\endgroup$ Commented May 22 at 9:29
  • $\begingroup$ Observe that the fact there's only countably many graphs like that is trivial, as there are only countably many (simple finite) graphs $\endgroup$ Commented May 23 at 14:05
  • 1
    $\begingroup$ I don't really have a pen and paper right now to check if it's completely correct, but it seems like there is a bijection between the set of the isomorphism classes of connected finite simple graphs that are locally $C_7$ and the set of all conjugacy classes of torsion-free, finite-index subgroups of the $(2,3,7)$-triangle group. $\endgroup$ Commented May 23 at 15:08
  • 1
    $\begingroup$ @MichaelT Ah! That's a nice catch. I think we need to drop the torsion-free condition. Your example 3 in fact comes from a torsion subgroup. $\endgroup$ Commented May 25 at 8:09

3 Answers 3

Reset to default
1
+100
$\begingroup$

Not an answer, but I posted an embedding of the Fricke-Macbeath graph.

enter image description here

$\endgroup$
0
1
$\begingroup$

Also not an answer. Connecting a set of extraordinary lines in the Braced Heptagon and adding three new points to the main 7-cycles gives a new embedding of the Klein graph.

Braced Klein Graph

$\endgroup$
2
  • $\begingroup$ Nice one, any specific observation? $\endgroup$ Commented May 27 at 11:06
  • 1
    $\begingroup$ It's crazy that the Klein graph is forced. I asked "Why?" at math.stackexchange.com/questions/5070511/… $\endgroup$ Commented May 27 at 12:17
1
$\begingroup$

It seems I got the 'space of $C_7$ graphs' totally wrong.

I now understand

  • There is a neat 'pair of pants' construction for $C_7$ graphs
  • Even for 24 vertices, this results in 'quite a few' $C_7$ graphs (17 oriented ones (?))
  • The 'well-known' $C_7$ graphs are 'just' the 'tips of the icebergs' (for given number of vertices) maximizing the graph automorphism group in terms of group order

The construction is a rather neat 'pair of pants' 'gluing' exercise.

Step 1: Take a 3-regular simple graph (e.g., the tetrahedron).

Step 2: Place a 'pair of pants' graph (aka a 3-prism) at every vertex of the 3-regular graph

3-prism

The 2 triangles 1-2-3 and 4-5-6 are the 'pants' and the 4-cycles 1-2-5-4, 2-3-6-5 as well as 3-1-4-6 are the 'holes' of the pants.

Step 3a: Connect the holes of two pants with short cylinders (aka 4-antiprism) with 2 holes, here for the hole 1-2-5-4 and a hole 12-25-45-14

short cyl

Similar,

  • for the hole 2-3-6-5 connect with a short cylinder to the hole 23-36-56-25
  • for the hoe 3-1-4-6 connect with a short cylinder to the hole 13-14-46-36

With this construction, the local neighbourhood of vertex 1 in open neighbourhood definition is the 7-cycle 2-12-14-4-14-13-3(-2).

For illustration, here a pair of pants with short cylinders/ 'legs' connected to each hole - missing the pair of pants connected to the open holes of the legs

pair of pants w legs

Step 3b: When connecting the open holes at the ends of the cylinders to other pairs of pants, consider to twist the hole of the pants vs the hole of cylinder; also, change/ control orientation as seen fit.

Step 4: Check that you actually end up with a graph that is locally $C_7$ (a triangle in the original 3-regular simple graph combined with unfortunate twisting may results in unwanted triangles destroying the $C_7$ neighbourhood structure) and delete duplicates resulting from the construction.

Is this construction of $C_7$ graphs complete?
Put differently: Can all $C_7$ graphs be constructed in this way?
And: Do all $C_7$ graphs have $12*k=6*(2k)$ vertices for some integer $k>1$ (with $2k$ pairs of pants as all 3-regular graphs have an even number of vertices)?

The case

  • with 4 pairs of paints
  • starting from the tetrahedron as 3-regular graph
  • with $4\cdot 6=24$ vertices
  • where the unique graph with maximal automorphism group (group order 336) is the 7-regular Klein graph

Below a first list generated in a way where I tried to control orientation (list 'should' provide triangulations of oriented 2-surfaces): All 17 graphs have 24 vertices and are locally $C_7$, the order of the graph automorphism group varies from 2 to 336

C7 graphs w 24 vertices, 4 pairs of pants

... and the one with 336 symmetries is the 7-regular Klein graph with 24 vertices.

BTW: It seems that allowing non-oriented graphs provides 40 more, non-isomorphic graph constructions; highest order of graph automorphism group at 4, quite a few asymmetric ones (no non-trivial graph automorphism).

References

jfyi: Listing of first few 3-regular graphs

3 reg graphs

$\endgroup$
1
  • $\begingroup$ I have not really thought about this, BUT I wonder if and how this 'pair of pants' construction can be refined to cover locally $C_8$ or $C_k, k>7$ cases...? $\endgroup$ Commented Sep 20 at 15:56

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.