Premium
Cataloging graphs by generating them uniformly at random
Author(s) -
Kerber A.,
Laue R.,
Hager R.,
Weber W.
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140507
Subject(s) - combinatorics , mathematics , cataloging , random graph , discrete mathematics , indifference graph , graph , computer science , world wide web
We describe an algorithm for cataloging graphs by generating them uniformly at random. The method used is based on a recent algorithm by Dixon and Wilf that generates orbit representatives uniformly at random. The approach is refined to graphs with prescribed numbers of edges and vertices, and then applied to obtain the complete list of graphs on 10 vertices.