Rough sets on graphs: New dependency and accuracy measures

Attribute dependency and approximation accuracy measures are two fundamental notions in rough set and database theory. In this paper, we provide combinatorial closed formulas and asymptotic estimates for the attribute dependency and the approximation accuracy of some basic graph families. Actually, a finite simple undirected graph can be seen as a particular case of information table. This perspective can be assumed in a not unique way: in fact, in terms of information table, we can investigate a connected graph by means of its adjacency matrix or through its minimum vertex distance matrix. Having assumed both these two perspectives, we study the behavior of the attribute dependency and the approximation accuracy for some basic graph families and, above all, we provide an asymptotic estimate for two global averages obtained by means of the previous quantities.