# Graph Circumference

The circumference of a graph is the length of any longest cycle in a graph. Hamiltonian graphs on vertices therefore have circumference of .

For a cyclic graph, the maximum element of the detour matrix over all adjacent vertices is one smaller than the circumference.

The graph circumference of a self-complementary graph is either (i.e., the graph is Hamiltonian), , or (Furrigia 1999, p. 51).

Circumferences of graphs for various classes of nonhamiltonian graphs are summarized in the table below.

class | circumference |

erefbarbell graph | |

-bishop graph | |

book graph | 6 |

complete bipartite graph for | |

-cone graph | |

gear graph | |

grid graph | |

grid graph | |

helm graph | |

-knight graph | |

pan graph | |

sunlet graph | |

web graph | |

wheel graph | |

-windmill graph |