Romanian Academy Calea Victoriei 125, Bucharest, Romania Locally Derivable Graphs

Issue title: New Frontiers in Scientific Discovery – Commemorating the Life and Work of Zdzislaw Pawlak

Article type: Research Article

Authors: Mazurkiewicz, Antoni

Affiliations: Institute of Computer Science of PAS, Ordona 21, 01-237, Warsaw, Poland. E-mail: [email protected]

Abstract: In the paper a class of locally derivable graphs is defined and discussed. Well known particular cases of derivable graphs are (among others) trees, complete, and triangular graphs; in the paper a broader class of locally derivable graphs, called closed graphs, is defined. Nodes and edges of closed graphs can be partitioned into external and internal ones; the main property of such graphs their local reducibility: successive removing its external nodes leads eventually to a singleton, and removing its external edges leads to an a spanning tree of the graph. The class of closed graphs is then a class enabling structural reducing. This property can be applied in processor networks to design some local procedures leading to global results.

Keywords: Graphs, graph transformations, local computations

Journal: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 335-355, 2007