𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimum graphs of specified diameter, connectivity and valence. II

✍ Scribed by E. Engelhardt; V. Klee; K. Li; H. Quaife


Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
769 KB
Volume
78
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis


In order to avoid trivialities, it is assumed throughout that d 22, vacal, and ~23. A (d, c, v)-graph is a c-connected graph of diameter d in which each node is of valence v. The minimum order (number of nodes) of such graphs is denoted by p(d, c, v), and a minimum (d, c, v)-graph is one of minimum order. The minimum (d, 1,3)-graphs and minimum (d, 2,3)-graphs were classified and enumerated by Klee and Quaife [6], and for odd d the minimum (d, 3,3)-graphs were classified and enumerated by Klee [4]. Related results were published by Myers (7-91. For large values of c and v, it seems hopeless to attempt to classify all minimum (d, c, v)-graphs, and precise enumeration seems also to be very difficult. However, it is possible to determine p(d, c, v) for all (d, c, v), and that is the purpose of the present note. Obviously &!, c, v) 2 p (d, c, v), the minimum order of a c-connected graph of diameter at least d in which each node is of valence at least v. It turns out that in many cases ,p(d,c,v) = p( d,c,v), where this means that the two function values differ by as little as possible, taking into account the fact that all odd-valent graphs are of the L . ._ -J-I order (in other words, either p(d, c, v) = ~(d, c, v), or v and p( d, c, v) are both odd andp(d, c, v) = p( d, c, v) + 1). However, there are cases in which the excess of p(d, c, v) over F( d, c, v) is not accounted for by this


πŸ“œ SIMILAR VOLUMES


On the edge-reconstruction of 3-connecte
✍ Yue Zhao πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 550 KB

It is shown that a 3-connected planar graph with minimum valency 4 is edge-reconstructible if no 4-vertex is adjacent to a 5-vertex. ## 1. Introduction In this paper, all graphs G=(V(G),E(G)) considered will be finite and simple. A connected graph G is said to have connectivity k o = ko(G) if the

On the connectivity and the conditional
✍ Balbuena, C.; Carmona, A.; FοΏ½brega, J.; Fiol, M. A. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 771 KB

Recently, it was proved that if the diameter D of a graph G is small enough in comparison with its girth, then G is maximally connected and that a similar result also holds for digraphs. More precisely, if the diameter D of a digraph G satisfies D 5 21 -1, then G has maximum connectivity ( K = 6 ) .

An algorithm for construction of a k-con
✍ Ulrich Schumacher πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 470 KB

Two fundamental considerations in the design of a communication network are reliability and maximum transmission delay. In this paper we give an algorithm for construction of an undirected graph with n vertices in which there are k node-disjoint paths between any two nodes. The generated graphs will