
Accession Number : AD0767694
Title : Computer Generation of VertexGraphs.
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 vertexdegree list, Lederberg has presented a treegeneration algorithm which, exploiting a canonicallexical 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 vertexgraphs 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 vertexgraphs 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 vertexgraphs 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
Computer Hardware
Atomic and Molecular Physics and Spectroscopy
Distribution Statement : APPROVED FOR PUBLIC RELEASE