CHARACTERIZATION AND APPLICABILITY OF SOME SPECIAL TYPES OF MOORE GRAPHS

Bilall SHAINI, Shpëtim REXHEPI, Eip RUFATI

Abstract

Various types of complex networks, such as telecommunication networks, are modeled using graphs whose vertices are telecommunication stations and whose edges are cables. During the construction of such networks, there are various restrictions on the vertices or edges. The condition is usually set on the highest degree of the vertex of that graph (that network) and the diameter of the graph (in that network). When studying such graphs, two typical problems arise: (i) degree/diameter problem: for given natural numbers and , it is necessary to find the largest possible number of vertices of a connected graph whose largest degree is equal to , and whose diameter is less than or equal to ; (ii) degree/girth problem: with the given natural numbers and , the smallest possible number of vertices of a connected regular graph whose degree of regularity is equal to and girth is should be determined. The study of these two problems takes place in finding evidence for the non-existence of graphs whose number of vertices is very close to the upper limit for the number , called Moore's limit, numerous studies give results about the existence of graphs that improve the lower limit of this number. The main goal of this paper is to study the problem of the existence of Moore graphs, that is, those graphs which, under the given conditions, have the number of vertices equal to Moore's limit. In the introductory section of the paper, the fundamental concepts and basic properties of the Moore graph are precisely defined. Furthermore, all Moore graphs of diameter 2 are described, and special emphasis is placed on the very important Moore graph known as the Petersen graph. Numerous figures are also offered for a better insight into its structure. The last part of the paper is covered by the problem characterizations of Moore graphs of diameter 3.

Pages: 334 - 346