Computer Generation of Vertex-Graphs.
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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
- Computer Programming and Software
- Computer Hardware
- Atomic and Molecular Physics and Spectroscopy