𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Orderly algorithms for generating restricted classes of graphs

✍ Scribed by Charles J. Colbourn; Ronald C. Read

Publisher
John Wiley and Sons
Year
1979
Tongue
English
Weight
463 KB
Volume
3
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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.

πŸ“œ SIMILAR VOLUMES

Class of graphs with restricted neighbor
Class of graphs with restricted neighborhoods
✍ Kim T. Rawlinson; R. C. Entringer πŸ“‚ Article πŸ“… 1979 πŸ› John Wiley and Sons 🌐 English βš– 286 KB

## Abstract A description is obtained for connected graphs in which a point __u__ is adjacent of __v__ only if __u__ is adjacent to all points whose degree is greater than that of __v__. The minimum number of lines in such a grpah with all points having degree at least __d__ is also determined. Fin

Simple Markov-chain algorithms for gener
Simple Markov-chain algorithms for generating bipartite graphs and tournaments
✍ Ravi Kannan; Prasad Tetali; Santosh Vempala πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 174 KB πŸ‘ 2 views

We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score sequence. We analyze simple Markov chains for both problems. For the first problem, we cannot prove that our chain is rapidly mixing in g

A Distributed Algorithm for GSPN Reachab
A Distributed Algorithm for GSPN Reachability Graph Generation
✍ S Caselli; G Conte; P Marenzoni πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 318 KB

The applicability of generalized stochastic Petri nets (GSPNs) and other high-level modeling formalisms to real systems is often constrained by the explosion in the size of the underlying state-space representation. This paper describes a distributed program taking advantage of the large amount of m

An Efficient Parallel Algorithm for Maxi
An Efficient Parallel Algorithm for Maximum Matching for Some Classes of Graphs
✍ I. Parfenoff πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 403 KB

The P 4 -tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with few induced P 4 (cographs, P 4 -sparse graphs, P 4 -lite graphs). Here, we propose an extension of R. Lin and S. Olariu's work (1994. J. Parallel Distributed Computing 22, 26 36.) on cographs, usi

Cyclic gossiping times for some classes
Cyclic gossiping times for some classes of graphs
✍ Knisely, James A.; Laskar, Renu πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 574 KB

Gossiping and broadcasting are two problems of information dissemination described for a group of individuals connected by a communication network. In gossiping, every person in the network knows a unique item of information and needs to communicate it to everyone else. In broadcasting, one individu