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.

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.

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

Giampiero Chiaselotti
;
Tommaso Gentile;Federico G. Infusino;Paolo A. Oliverio
2017

Abstract

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.
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.
Simple Graphs; Lattices; Set Partitions
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11770/147708
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 27
  • ???jsp.display-item.citation.isi??? 23
social impact