Accession Number : AD0767694
Title : Computer Generation of Vertex-Graphs.
Descriptive Note : Technical rept.,
Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Personal Author(s) : Sridharan,N. S.
Report Date : JUL 1973
Pagination or Media Count : 21
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)
Descriptors : (*COMPUTER PROGRAMMING, GRAPHICS), (*MOLECULAR STRUCTURE, COMPUTER PROGRAMMING), TOPOLOGY, ARTIFICIAL INTELLIGENCE, MAPPING(TRANSFORMATIONS)
Subject Categories : Computer Programming and Software
Atomic and Molecular Physics and Spectroscopy
Distribution Statement : APPROVED FOR PUBLIC RELEASE