TY - JOUR

T1 - Orderly algorithms for generating restricted classes of graphs

AU - Colbourn, Charles J.

AU - Read, Ronald C.

PY - 1979

Y1 - 1979

N2 - Orderly algorithms for the generation of exhaustive lists of nonisomorphic graphs are discussed. The existence of orderly methods to generate the graphs with a given subgraph and without a given subgraph is established. This method can be used to list all the nonisomorphic subgraphs of a given graph, as well as to produce catalogs of Hamiltonian graphs, pancyclic graphs, degree‐constrained graphs, and other classes. A generalization of this method is given that can be used to generate lists of graphs with given girth, planar graphs, k‐colorable graphs, and k‐connected graphs, for example. Finally, these observations are employed to generate restricted classes of digraphs, notably acyclic digraphs and poset digraphs. The generation of poset digraphs is shown to supply a practical orderly method for producing a catalog of lattices. Similar observations concerning vertex addition generation methods allow one to improve on existing methods for the generation of catalog of interval and circle graphs.

AB - Orderly algorithms for the generation of exhaustive lists of nonisomorphic graphs are discussed. The existence of orderly methods to generate the graphs with a given subgraph and without a given subgraph is established. This method can be used to list all the nonisomorphic subgraphs of a given graph, as well as to produce catalogs of Hamiltonian graphs, pancyclic graphs, degree‐constrained graphs, and other classes. A generalization of this method is given that can be used to generate lists of graphs with given girth, planar graphs, k‐colorable graphs, and k‐connected graphs, for example. Finally, these observations are employed to generate restricted classes of digraphs, notably acyclic digraphs and poset digraphs. The generation of poset digraphs is shown to supply a practical orderly method for producing a catalog of lattices. Similar observations concerning vertex addition generation methods allow one to improve on existing methods for the generation of catalog of interval and circle graphs.

UR - http://www.scopus.com/inward/record.url?scp=0011686172&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0011686172&partnerID=8YFLogxK

U2 - 10.1002/jgt.3190030210

DO - 10.1002/jgt.3190030210

M3 - Article

AN - SCOPUS:0011686172

SN - 0364-9024

VL - 3

SP - 187

EP - 195

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -