The 6th International Conference "Distributed Computing and Grid-technologies in Science and Education"

THE MAXIMUM DISTANCE IN THE GRAPH WITH FIXED DOMINATION NUMBER

30 Jun 2014, 17:00

15m

407 (LIT JINR)

sectional reports Algorithms and methods of application tasks solving in distributed computing environments

Speaker

Dr Alexander RAPPOPORT (A. A. Kharkevich Institute for Information Transmission Problems, RAS)

Description

The study considers the problem of analysis of metric characteristics and structural features of graphs with a fixed smallest dominating set. It, in particular, provides opportunities for realization of various ways of data transmission in communication networks. The results also include methods of such transmission using decentralization and local interaction of elements (for example, in peer-to-peer environments). The work shows an estimate of maximum distances, diameter and – for these values – the type of configurations of graphs with fixed domination number. A special place is given to situation when there are two dominating elements. The study formulates a number of conditions describing graphs of this type. [1] A. M. Rappoport. The problem of construction of the decentralized communication structures. Dynamic of non-homogeneous systems. Proceedings of ISA RAS, M.: URSS, 2004, Vol.7, P.176-179. [2] A. P.Afanas’ev, A. M Rappoport. Construction and estimation of dominating sets in communication structures. Doklady Mathematics, 2006, Vol.73, No.3, P. 465-468. [3] T. W. Haynes, S.T. Hedetniemi, P. J. Slater. Fundamentals of domination on graphs. Marcel Dekker, Inc. New York, 1998, P. 450. [4] V. A. Emelichev, etc. Lectures on the graphs theory. M.: Librokom, 2008, P. 383.