𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Nonexistence of certain cubic graphs with small diameters

✍ Scribed by Leif K. Jørgensen

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
560 KB
Volume
114
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the maximum number of vertices in a cubic graph with small diameter. We show that a cubic graph of diameter 4 has at most 40 vertices. (The Moore bound is 46 and graphs with 38 vertices are known.) We also consider bipartite cubic graphs of diameter 5, for which the Moore bound is 62. We prove that in this case a graph with 56 vertices found by Bond and Delorme (1988) is optimal.

A survey paper of Bermond et al. [3] gives constructions of large (d,D)-graphs. Their paper also contains a table of the largest known (d,D)-graphs. Only in five cases is a (d, D)-graph (d 3 3 and D 3 2) known to have as many vertices as possible, and these optimal graphs are either Moore graphs or have M(d, D)-2 vertices. For d = 3, the first case, where the maximal number of vertices in a (d, D)-graph is not known, is D =4. There exist at least two non-isomorphic cubic graphs of diameter

📜 SIMILAR VOLUMES

Domination in planar graphs with small d
Domination in planar graphs with small diameter
✍ Wayne Goddard; Michael A. Henning 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB

## Abstract MacGillivray and Seyffarth (J Graph Theory 22 (1996), 213–229) proved that planar graphs of diameter two have domination number at most three and planar graphs of diameter three have domination number at most ten. They also give examples of planar graphs of diameter four having arbitrar

Nonexistence of some Antipodal Distance-
Nonexistence of some Antipodal Distance-regular Graphs of Diameter Four
✍ Aleksandar Jurišić; Jack Koolen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 160 KB

We find an inequality involving the eigenvalues of a regular graph; equality holds if and only if the graph is strongly regular. We apply this inequality to the first subconstituents of a distance-regular graph and obtain a simple proof of the fundamental bound for distance-regular graphs, discovere

Three small cubic graphs with interestin
Three small cubic graphs with interesting hamiltonian properties
✍ Tudor Zamfirescu 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 211 KB

## Abstract We present here three graphs, which are the smallest known ones of their kind: a cubic three‐connected planar nontraceable graph, a cubic three‐connected planar graph which is not homogeneously traceable, and a cubic one‐Hamiltonian graph which is not Hamiltonian connected.

Region distributions of some small diame
Region distributions of some small diameter graphs
✍ Saul Stahl 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 954 KB

Stahl, S., Region distributions of some small diameter graphs, Discrete Mathematics 89 (1991) 281-299. Let G be a graph with a vertex u such that V(G) -{u} induces either a forest or a cycle. It is shown that the region distribution of G is approximately proportional to the Stirling numbers of the f

Small maximal matchings of random cubic
Small maximal matchings of random cubic graphs
✍ H. Assiyatun; W. Duckworth 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 330 KB

## Abstract We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random __n__‐vertex cubic graphs using diffe