✦ LIBER ✦

Fast generation of regular graphs and construction of cages

✍ Scribed by Meringer, Markus

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 162 KB
Volume: 30
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199902)30:2<137::aid-jgt7>3.0.co;2-g

No coin nor oath required. For personal study only.

✦ Synopsis

The construction of complete lists of regular graphs up to isomorphism is one of the oldest problems in constructive combinatorics. In this article an efficient algorithm to generate regular graphs with a given number of vertices and vertex degree is introduced. The method is based on orderly generation refined by criteria to avoid isomorphism checking and combined with a fast test for canonicity. The implementation allows computing even large classes of graphs, like construction of the 4-regular graphs on 18 vertices and, for the first time, the 5regular graphs on 16 vertices. Also in cases with given girth, some remarkable results are obtained. For instance, the 5-regular graphs with girth 5 and minimal number of vertices were generated in less than 1 h. There exist exactly four (5, 5)-cages.

📜 SIMILAR VOLUMES

Deza graphs: A generalization of strongl

Deza graphs: A generalization of strongly regular graph

✍ M. Erickson; S. Fernando; W. H. Haemers; D. Hardy; J. Hemmeter 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 1 views

P4-decompositions of regular graphs

✍ Heinrich, Katherine; Liu, Jiping; Yu, Minli 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB 👁 1 views

In this article, we show that every simple r-regular graph G admits a balanced P 4 -decomposition if r ≡ 0(mod 3) and G has no cut-edge when r is odd. We also show that a connected 4-regular graph G admits a P 4 -decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degr

Rat cages of simplified construction

✍ Long, J. A. 📂 Article 📅 1924 🏛 John Wiley and Sons 🌐 English ⚖ 411 KB

Generation of isospectral graphs

✍ Halbeisen, Lorenz; Hungerb�hler, Norbert 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 357 KB 👁 1 views

We discuss a discrete version of Sunada's Theorem on isospectral manifolds, which allows the generation of isospectral simple graphs, i.e., nonisomorphic simple graphs that have the same Laplace spectrum. We also consider additional boundary conditions and Buser's transplantation technique applied t

1-Factorizations of random regular graph

1-Factorizations of random regular graphs

✍ M. S. O. Molloy; H. Robalewska; R. W. Robinson; N. C. Wormald 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB 👁 2 views

It is shown that for each r G 3, a random r-regular graph on 2 n vertices is equivalent in a certain sense to a set of r randomly chosen disjoint perfect matchings of the 2 n vertices, as n ª ϱ. This equivalence of two sequences of probabilistic spaces, called contiguity, occurs when all events almo

Construction of uniquelyH-colorable grap

Construction of uniquelyH-colorable graphs

✍ Zhu, Xuding 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB 👁 2 views

We shall prove that for any graph H that is a core, if χ(G) is large enough, then H × G is uniquely H-colorable. We also give a new construction of triangle free graphs, which are uniquely n-colorable.