The adjacency matrix of a graph as a data table: a geometric perspective

In this paper we continue a research project concerning the study of a graph from the perspective of granular computation. To be more specific, we interpret the adjacency matrix of any simple undirected graph $G$ in terms of data information table, which is one of the most studied structures in database theory. Granular computing (abbreviated GrC) is a well developed research field in applied and theoretical information sciences; nevertheless, in this paper we address our efforts towards a purely mathematical development of the link between GrC and graph theory. From this perspective, the well studied notion of indiscernibility relation in GrC becomes a symmetry relation with respect to a given vertex subset in graph theory, therefore the investigation of this symmetry relation turns out to be the main object of study in this paper.In detail, we study a simple undirected graph $G$ by assuming a generic vertex subset $W$ as reference system with respect to which examine the symmetry of all vertex subsets of $G$. The change of perspective from $G$ without reference system to the pair $(G,W)$ is similar to what occurs in the transition from an affine space to a vector space. We interpret the symmetry blocks in the reference system $(G,W)$ as particular equivalence classes of vertices in $G$ and we study the geometric properties of all reference systems $(G,W)$, when $W$ runs over all vertex subsets of $G$. We also introduce three hypergraph models and a vertex set partition lattice associated to $G$, by taking as general models of reference several classical notions of GrC. For all these constructions we provide a geometric characterization and we determine their structure for basic graph families. Finally, we apply a wide part of our work to study the important case of the Petersen graph.