# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Find the number of vertices at each distance in a symmetric graph

Contributed by:
Ed Pegg Jr

ResourceFunction["GraphCoordinationSequence"][ finds the number of vertices at distance |

In a square lattice, the coordination sequence starts 1, 4, 8, 12, 16, 20, 24, ..., with multiples of 4 following. By the taxicab metric, there is one lattice point at distance 0, 4 at distance 1, and so on.

Usually, the coordination sequence is only of interest when it is the same for all vertices.

For a disconnected graph, the number of unreachable points is placed after ∞.

Finding the coordination sequence for a specific graph is compuationally easy. Finding the graph for a specific coordination sequence is extremely difficult. Whether a graph with coordination sequence {1, 57, 3192} exists has been an unsolved question since 1960.

Find the coordination sequence of the Petersen graph:

In[1]:= |

Out[1]= |

Show the GraphDistanceMatrix in unsorted and sorted form:

In[2]:= |

Out[4]= |

Construct the order-7 middle levels graph (here, the middle levels are 3 and 4):

In[5]:= |

Out[5]= |

Find the coordination sequence:

In[6]:= |

Out[6]= |

The coordination sequence for any odd order middle levels graph can be found with a formula:

In[7]:= |

Out[7]= |

Find the coordination sequence for a disconnected graph:

In[8]:= |

Out[8]= |

Directed graphs may be used, such as seen in CayleyGraph.

The following graph is Fibonacci to ten steps in the coordination sequence:

In[9]:= |

Out[9]= |

The following graph is tribonacci to ten steps in the coordination sequence:

In[10]:= |

Out[10]= |

The following graph is Padovan to ten steps in the coordination sequence:

In[11]:= |

Out[11]= |

In[12]:= |

Out[12]= |

The coordination sequences of hypercube graphs are binomial:

In[13]:= |

Out[13]= |

The coordination sequences of the Bruhat graphs are the Mahonian numbers, A008302:

In[14]:= |

Out[14]= |

Multiple graphs can have the same coordination sequence:

In[15]:= |

Out[16]= |

Some graphs show different distant behaviors for every vertex:

In[17]:= |

Out[18]= |

The coordination sequence for this graph has maximal dis-coordination:

In[19]:= |

Out[19]= |

Up to 9 vertices, all regular connected graphs have the same coordination sequence for all vertices, with two exceptions:

In[20]:= |

Out[21]= |

Graphs with a specific coordination sequence are hard to find. Here are several of the form {1,3,6,x,x,4}:

In[22]:= |

Out[23]= |

Determining the existence of all {1,3,6,10,10,4} graphs currently requires a search of the 453090162062723 cubic graphs on 34 nodes.

Here are 947 Cayley graphs with precomputed {order, coordination sequence, generator}:

In[24]:= |

Out[25]= |

Coordination sequences have a rise followed (usually) by a fall:

In[26]:= |

Out[26]= |

- 1.0.0 – 11 October 2022

This work is licensed under a Creative Commons Attribution 4.0 International License