Local Properties of Triangular Graphs

Issue title: Special Issue on Concurrency Specification and Programming (CS&P)

Article type: Research Article

Authors: Mazurkiewicz, Antoni

Affiliations: Institute of Computer Science of PAS Ordona 21, 01-237 Warsaw, Poland. E-mail: Antoni.Mazurkiewicz@ipipan.waw.pl

Abstract: In the paper triangular graphs are discussed. The class of triangular graphs is of special interest as unifying basic features of complete graphs and trees. The main issue addressed in the paper is to characterize class of triangular graphs (defined globally) by local means. Namely, it is proved that any triangular graph can be constructed from a singleton by successive extensions with nodes having complete neighborhoods. Next, the proved theoretical properties are applied for designing some local algorithms for triangular graphs: for elections a leader and for constructing their spanning trees. The fairness of these algorithms is proved, which means that any node can be elected and any spanning tree can be constructed by execution of these algorithms.

Keywords: triangular graphs, local computations, leader elections, spanning trees

Journal: Fundamenta Informaticae, vol. 79, no. 3-4, pp. 487-495, 2007