Graphical Partitions and Graphical Relations

Article type: Research Article

Authors: Shaheen, Tanzeela^a | Stell, John G.^{b; *}

Correspondence: [*] Address for correspondence: School of Computing, University of Leeds, Leeds LS2 9JT, Leeds, U.K.

Abstract: We generalize the well-known correspondence between partitions and equivalence relations on a set to the case of graphs and hypergraphs. This is motivated by the role that partitions and equivalence relations play in Rough Set Theory and the results provide some of the foundations needed to develop a theory of rough graphs. We use one notion of a partition of a hypergraph, which we call a graphical partition, and we show how these structures correspond to relations on a hypergraph having additional properties. In the case of a hypergraph with only nodes and no edges these properties are exactly the usual reflexivity, symmetry and transitivity properties required for equivalence relations on a set. We present definitions for upper and lower approximations of a subgraph with respect to a graphical partition. These generalize the well-known approximations in Rough Set Theory. We establish fundamental properties of our generalized approximations and provide examples of these constructions on some graphs.

DOI: 10.3233/FI-2019-1777

Journal: Fundamenta Informaticae, vol. 165, no. 1, pp. 75-98, 2019