摘要:

AbstractThis annotated bibliography contains 32 papers on graph isomorphism not included in the bibliography of Read and Corneil, most of which discuss algorithms or their theoretical foundations. We include articles by Miller, Weisfeiler, and Whitney as well as algorithms by Johnson and Leighton, Schmidt and Druffel, Tinhofer, and Erdös and Babai

ISSN:0364-9024    

DOI:10.1002/jgt.3190030202

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractWe briefly describe how we compiled a catalog of all the 720 self‐complementary graphs on 12 nodes. In our first attempt at this compilation one graph was inadvertently omitted. The missing graph was subsequently found by making use of a theoretical formula due to Parthasarathy and Sridharan for counting self‐complementary graphs with given partiti

ISSN:0364-9024    

DOI:10.1002/jgt.3190030203

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractLabel‐increasing trees are fully labeled rooted trees with the restriction that the labels are in increasing order on every path from the root; the best known example is the binary case—no tree with more than two branches at the root, or internal vertices of degree greater than three—extensively examined by Foata and Schutzenberger inA Survey of Combinatorial Theory.The forests without branching restrictions are enumerated by number of trees byFn(x) =x(x+ 1)…(x+n− 1),n>1 (F0(x) = 1), whose equivalent:Fn(x) =Yn(xT1,…,xTn),Fn(1)=Tn+ 1=n!, is readily adapted to branching

ISSN:0364-9024    

DOI:10.1002/jgt.3190030204

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractGiven a graph Γ an abelian groupG, and a labeling of the vertices of Γ with elements ofG, necessary and sufficient conditions are stated for the existence of a labeling of the edges in which the label of each vertex equals the product of the labels of its incident edges. Such an edge labeling is called compatible. For vertex labelings satisfying these conditions, the set of compatible edge labelings is enumerate

ISSN:0364-9024    

DOI:10.1002/jgt.3190030205

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractAn ingraphNis a subgraph of a digraphGwhose edge set consists of all the edges ofGthat are directed into a subsetXof the vertices. SetXis the generating set ofN.It is proved thatGcontains a unique even ingraph and this ingraph is generated by the setAof vertices that root an odd number of spanning out arborescences providedAis nonempty. IfAis empty, then there exist at least two even ingraphs.

ISSN:0364-9024    

DOI:10.1002/jgt.3190030206

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractIn this paper we introduce the notion of strongly connected polygons in the line graph of a bipartite graph. We use this notion to give a necessary and sufficient condition for a matrixYto be fully irreducible without the need to construct a transversal ofY.In addition, we show that the notion of strongly connected polygons forms the basis of a general theory that may be used for finding all the cycles in the directed graph of a fully irreducible matrix and for constructing all the nonzero transversals of a fully irreducible matrix.

ISSN:0364-9024    

DOI:10.1002/jgt.3190030207

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractExistence of some generalized edge colorings is proved by using the properties of hypergraphs as well as alternating chain methods. A general framework is given for edge colorings and some general properties of balancing are derived.

ISSN:0364-9024    

DOI:10.1002/jgt.3190030208

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractA graph is defined to be randomly matchable if every matching ofGcan be extended to a perfect matching. It is shown that the connected randomly matchable graphs are preciselyK2nandKn,n(n≥ 1

ISSN:0364-9024    

DOI:10.1002/jgt.3190030209

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractOrderly 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, andk‐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 g

ISSN:0364-9024    

DOI:10.1002/jgt.3190030210

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractA set of points in a graph is independent if no two points in the set are adjacent. A graph is well covered if every maximal independent set is a maximum independent set or, equivalently, if every independent set is contained in a maximum independent set. The well‐covered graphs are classified by theWnproperty: For a positive integern, a graphGbelongs to classWnif ≥nand anyndisjoint independent sets are contained inndisjoint maximum independent sets. Constructions are presented that show how to build infinite families ofWngraphs containing arbitrarily large independent sets. A characterization ofWngraphs in terms of well‐covered subgraphs is given, as well as bounds for the size of a maximum independent set and the minimum and maximum degrees of points inWng

ISSN:0364-9024    

DOI:10.1002/jgt.3190030211

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY