Abstract

Knödel graphs W d,n of even order n and degree d , 1 X d X [Special characters omitted.] , have been introduced by W. Knödel as a result of their good properties in terms of broadcasting and gossiping information in interconnected networks. In particular, Knödel graphs of order 2 d and degree d have been widely studied because of their remarkable number of vertices to diameter ratio characteristic, which competes with hypercubes and circulant graphs of the same order. In this thesis, a general definition of the Knödel graphs is given, based on a theorem of isomorphism, and a new family of complete rotations is found. Based on the Cayley graph definition of the Knödel graph, a new hierarchical structure is defined and its rotational properties are studied. Although Knödel graphs have high symmetry properties, the diameter of the Knödel graphs is known only for W d,2 d , and the shortest path problem in logarithmic time, is an open problem. In this thesis, a logarithmic algorithm for the shortest path in W d,2 d is proposed, for a subset of the set of vertices, and a heuristic is given for the remaining vertices. The method described here opens the way of finding the shortest path in general and for solving the general problem of finding the diameter in every Knödel graph.