Computer Generation of Vertex-Graphs.
Abstract
In connection with the problem of generating all multigraphs having a specified vertex-degree list, Lederberg has presented a tree-generation algorithm which, exploiting a canonical-lexical notational system, constructs the complete set of solutions in canonically increasing order, without redundancy. Brown, et al., have expanded the scope of generation to cyclic graphs. Their method relies upon the existence of a complete and irredundant set of vertex-graphs and the procedure consists of a series of graph labelling steps. Graph labelling allows one to assign labels from a given set to the vertices (edges) of a graph, in such a way that knowing the symmetry group of the graph, equivalent label assignments are avoided prospectively. Recent work has been directed towards supplying the vertex-graphs needed by the generator. A program has been written to generate all graphs with t trivalent and q quadrivalent vertices, from graphs having (t + 2q) trivalent vertices. This method, however, will generate redundant vertex-graphs and some issues in isomorph elimination are considered in this presentation. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1973
- Accession Number
- AD0767694
Entities
People
- N. S. Sridharan
Organizations
- Stanford University