×

The adjacency matrix of a graph as a data table: a geometric perspective. (English) Zbl 1366.05029

Summary: 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 toward 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.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C65 Hypergraphs
05A18 Partitions of sets
05C75 Structural characterization of families of graphs
06A15 Galois correspondences, closure operators (in relation to ordered sets)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N., Huang, H., Sudakov, B.: Nonnegative \[k\] k-sums, fractional covers, and probability of small deviations. J Comb. Theory Ser. B 102(3), 784-796 (2012) · Zbl 1241.05100
[2] Andrews, G.E.: Euler’s “De Partitio numerorum”. Bull. Am. Math. Soc. 44(4), 561-573 (2007) · Zbl 1172.11031
[3] Bargiela, A., Pedrycz, W.: Granular Computing. An Introduction. The Springer International Series in Engineering and Computer Science, New York (2003) · Zbl 1046.68052
[4] Barret, C.L., Reidys, C.M.: Elements of a theory of computer simulation. I. Sequential CA over random graphs. Appl. Math. Comput. 98(2-3), 241-259 (1999)
[5] Barret, C.L., Mortveit, H.S., Reidys, C.M.: Elements of a theory of computer simulation. II. Sequential dynamical systems. Appl. Math. Comput. 107(2-3), 121-136 (2000) · Zbl 1049.68149
[6] Barret, C.L., Mortveit, H.S., Reidys, C.M.: Elements of a theory of computer simulation. III. Equivalence of SDS. Appl. Math. Comput. 122(3), 325-340 (2001) · Zbl 1050.68161
[7] Barret, C.L., Mortveit, H.S., Reidys, C.M.: Elements of a theory of computer simulation. IV. Sequential dynamical systems: fixed points, invertibility and equivalence. Appl. Math. Comput. 134(1), 153-171 (2003) · Zbl 1028.37010
[8] Berge, C.: Hypergraphs: Combinatorics of Finite Sets. Elsevier, Amsterdam (1984)
[9] Bhattacharya, A.: On a conjecture of Manickam and Singhi. Discrete Math. 272, 259-261 (2003) · Zbl 1030.05116
[10] Bianucci, D., Cattaneo, G., Ciucci, D.: Entropies and co-entropies of coverings with application to incomplete information systems. Fundam Inform 75(1), 77-105 (2007) · Zbl 1108.68112
[11] Bianucci, D.; Cattaneo, G.; Peter, JF (ed.); Skowron, A. (ed.), Information entropy and granulation co-entropy of partitions and coverings: a summary, No. 5656, 15-66 (2009), New York · Zbl 1248.94038
[12] Bisi, C., Chiaselotti, G.: A class of lattices and boolean functions related to the Manickam-Miklös-Singhi conjecture. Adv. Geom. 13(1), 1-27 (2013) · Zbl 1259.05178
[13] Bisi, C., Chiaselotti, G., Oliverio, P.A.: Sand piles models of signed partitions with \[d\] d piles. ISRN Comb (2013). doi:10.1155/2013/615703 · Zbl 1264.05007
[14] Bisi, C., Chiaselotti, G., Marino, G., Oliverio, P.A.: A natural extension of the Young partition lattice. Adv. Geom. 15(3), 263-280 (2015) · Zbl 1317.05018
[15] Bisi, C., Chiaselotti, G., Gentile, T., Oliverio, P. A.: Dominance order on signed integer partitions. Adv. Geom. (to appear) · Zbl 1264.05007
[16] Blyth, T.S.: Lattices and Ordered Algebraic Structures. Springer, London (2005) · Zbl 1073.06001
[17] Cattaneo, G.: Generalized rough sets (preclusivity fuzzy-intuitionistic (BZ) lattices). Stud. Log. 01, 47-77 (1997) · Zbl 0864.03040
[18] Cattaneo, G., Ciucci, D., Bianucci, D.: Entropy and co-entropy of partitions and coverings with applications to roughness theory. In: Bello, R., Falcon, R., Pedrycz, W., Kacprzyk, J. (eds.) Granular Computing: At the Junction of Rough Sets and Fuzzy Sets. Series: Studies on Fuzziness and Soft Computing, vol. 224, pp. 55-77. Springer, Berlin (2008)
[19] Cattaneo, G.: An investigation about rough set theory: some foudational and mathematical aspects. Fundam. Inform. 108, 197-221 (2011) · Zbl 1241.03060
[20] Cattaneo, G., Comito, M., Bianucci, D.: Sand piles: from physics to cellular automata models. Theor. Comput. Sci. 436, 35-53 (2012) · Zbl 1251.37017
[21] Cattaneo, G., Chiaselotti, G., Dennunzio, A., Formenti, E., Manzoni, L.: Non uniform cellular automata description of signed partition versions of ice and sand pile models. Cell. Autom. Lect. Notes Comput. Sci. 8751, 115-124 (2014)
[22] Cattaneo, G., Chiaselotti, G., Ciucci, D., Gentile, T.: On the connection of hypergraph theory with formal concept analysis and rough set theory. Inf Sci 330, 342-357 (2016) · Zbl 1390.68618
[23] Cattaneo, G., Chiaselotti, G., Oliverio, P.A., Stumbo, F.: A new discrete dynamical system of signed integer partitions. Eur. J. Comb. 55, 119-143 (2016) · Zbl 1333.05026
[24] Cattaneo, G., Chiaselotti, G., Gentile, T., Oliverio, P.A.: The lattice structure of equally extended signed partitions. A generalization of the Brylawski approach to integer partitions with two possible models: ice piles and semiconductors. Fundam. Inform. 141, 1-36 (2015) · Zbl 1344.37015
[25] Chen, J., Li, J.: An application of rough sets to graph theory. Inf. Sci. 201, 114-127 (2012) · Zbl 1251.05165
[26] Chiaselotti, G.: On a problem concerning the weight functions. Eur. J. Comb. 23, 15-22 (2002) · Zbl 0998.05064
[27] Chiaselotti, G., Infante, G., Marino, G.: New results related to a conjecture of Manickam and Singhi. Eur. J. Comb. 29(2), 361-368 (2008) · Zbl 1131.05093
[28] Chiaselotti, G., Marino, G., Oliverio, P.A., Petrassi, D.: A discrete dynamical model of signed partitions. J. Appl. Math. 2013, 973501 (2013) · Zbl 1266.06001
[29] Chiaselotti, G., Gentile, T., Marino, G., Oliverio, P.A.: Parallel rank of two sandpile models of signed integer partitions. J. Appl. Math. 2013, 292143 (2013) · Zbl 1268.06001
[30] Chiaselotti, G., Gentile, T., Oliverio, P.A.: Parallel and sequential dynamics of two discrete models of signed integer partitions. Appl. Math. Comput. 232, 1249-1261 (2014) · Zbl 1410.37015
[31] Chiaselotti, G., Gentile, T., Oliverio, P.A.: Lattices of partial sums. Algebra Discrete Math. 18(2), 171-185 (2014) · Zbl 1325.06001
[32] Chiaselotti, G., Keith, W., Oliverio, P.A.: Two self-dual lattices of signed integer partitions. Appl. Math. Inf. Sci. 8, 3191-3199 (2014)
[33] Chiaselotti, G., Ciucci, D., Gentile, T.: Simple undirected graphs as formal contexts. In: Proceedings of ICFCA, Lecture Notes in Computer Science, vol. 9113, pp. 287-302. Springer (2015) · Zbl 1312.68184
[34] Chiaselotti, G., Ciucci, D., Gentile, T., Infusino, F.: Rough set theory applied to simple undirected graphs. In: Proceedings of RSKT 2015, Lecture Notes in Computer Science, vol. 9436, pp. 423-434. Springer (2015) · Zbl 1444.68219
[35] Chiaselotti, G., Ciucci, D., Gentile, T., Infusino, F.: Preclusivity and simple graphs. In: Proceedings of RSFDGrC 2015, Lecture Notes in Computer Science, vol. 9437, pp. 127-137. Springer (2015) · Zbl 1444.68199
[36] Chiaselotti, G., Ciucci, D., Gentile, T., Infusino, F.: Preclusivity and simple graphs: the \[n-\] n-cycle and \[n\] n-path cases. In: Proceedings of RSFDGrC 2015, Lecture Notes in Computer Science, vol. 9437, pp. 138-148. Springer (2015) · Zbl 1444.68200
[37] Chiaselotti, G., Gentile, T., Infusino, F., Oliverio, P.A.: Rough sets for \[n\] n-cycles and \[n\] n-paths. Appl. Math. Inf. Sci. 10(1), 117-124 (2016)
[38] Ciucci, D.E.: Classification of Dynamics in Rough Sets. In: RSCTC 2010, Lecture Notes in Computer Science, vol. 6086, pp. 257-266. Springer (2010) · Zbl 1344.37015
[39] Ciucci, D.E.: Temporal dynamics in information tables. Fundam. Inform. 115(1), 57-74 (2012) · Zbl 1237.68212
[40] Comellas, F., Sampels, M.: Deterministic small-world networks. Phys. A 309, 231-235 (2002) · Zbl 0995.60103
[41] Diestel, R.: Graph Theory. Graduate Text in Mathematics, 4th edn. Springer, Berlin (2010) · Zbl 1204.05001
[42] Dorbec, P., Montassier, M., Ochem, P.: Vertex partitions of graphs into cographs and stars. J. Graph Theory 75(1), 75-90 (2014) · Zbl 1280.05104
[43] Doreian, P., Batagelj, V., Ferligoj, A.: Generalized Blockmodeling. Cambridge University Press, Cambridge (2005) · Zbl 1181.68106
[44] Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput. 24, 1278-1304 (1995) · Zbl 0842.05070
[45] Eiter, T., Gottlob, G.: Hypergraph transversal computation and related problems in logic and AI. In: Proceedings of JELIA 2002, Lecture Notes in Computer Science, vol. 2424, pp. 549-564 (2002) · Zbl 1013.68143
[46] Elbassioni, K.: On the complexity of monotone dualization and generating minimal hypergraph transversals. Discrete Appl. Math. 32(2), 171-187 (2008) · Zbl 1160.68017
[47] Erdös, P., Rényi, A.: Asymmetric graphs. Acta Math. Hung. 14(3-4), 295-315 (1963) · Zbl 0118.18901
[48] Gravier, S., Hoang, C.T., Maraya, F.: Coloring the hypergraph of maximal cliques of a graph with no long path. Discrete Math. 272(2-3), 285-290 (2003) · Zbl 1028.05033
[49] Greco, S., et al.: Rough sets methodology for sorting problems in presence of multiple attributes and criteria. Eur. J. Oper. Res. 138, 247-259 (2002) · Zbl 1008.90509
[50] Groshaus, M., Szwarcfiter, J.L.: Biclique graphs and biclique matrices. J. Graph Theory 63(1), 1-16 (2010) · Zbl 1216.05104
[51] Groshaus, M., Montero, L.P.: On the iterated biclique operator. J. Graph Theory 73(2), 181-190 (2013) · Zbl 1262.05117
[52] Gyárfás, A., Lehel, J.: Hypergraph families with bounded edge cover or transversal number. Combinatorica 3(3-4), 351-358 (1983) · Zbl 0534.05052
[53] Hagen, M.: Lower bounds for three algorithms for transversal hypergraph generation. Discrete Appl. Math. 157, 1460-1469 (2009) · Zbl 1177.05116
[54] Hartke, S.G., Stolee, D.: A linear programming approach to the Manickam-Miklös-Singhi conjecture. Eur. J. Comb. 36, 53-70 (2014) · Zbl 1284.05325
[55] Hahn, G., Sabidussi, G. (eds.): Graph Symmetry. Algebraic Methods and Applications; NATO ASI Series, vol. 497, Springer, Berlin (1997) · Zbl 0868.00039
[56] Hońko, P.: Relational pattern updating. Inf. Sci. 189, 208-218 (2012)
[57] Hońko, P.: Association discovery from relational data via granular computing. Inf. Sci. 10, 136-149 (2013) · Zbl 1284.68497
[58] Huang, B., Zhang, Y., Li, H., Wei, D.: A dominance intuitionistic fuzzy-rough set approach and its applications. Appl. Math. Model. 37, 7128-7141 (2013) · Zbl 1426.68262
[59] Ivanov, A.A., Shpectorov, S.V.: Geometries for sporadic groups related to the petersen graph. I. Commun. Algebra 16(5), 925-953 (1988) · Zbl 0639.20011
[60] Ivanov, A.A., Shpectorov, S.V.: Geometries for sporadic groups related to the petersen graph. II. Eur. J. Comb. 10(4), 347-361 (1989) · Zbl 0709.20014
[61] Kang, X., Li, D., Wang, S., Qu, K.: Formal concept analysis based on fuzzy granularity base for different granulations. Fuzzy Sets Syst. 203, 33-48 (2012) · Zbl 1254.68249
[62] Keith, W.J.: A bijective toolkit for signed partitions. Ann. Comb. 15, 95-117 (2011) · Zbl 1233.05031
[63] Khachiyan, L., Boros, E., Elbassioni, K., Gurvich, V.: A global parallel algorithm for the hypergraph transversal problem. Inf. Process. Lett. 101(4), 148-155 (2007) · Zbl 1185.68838
[64] Kreinovich, V.; Pedrycz, W. (ed.); Skowron, A. (ed.); Kreinovich, V. (ed.), Interval computation as an important part of granular computing: an introduction, 3-32 (2008), New York
[65] Lin, T.Y.: Data mining: granular computing approach, in methodologies for knowledge discovery and data mining. Lecture Notes in Computer Science 1574, 24-33 (1999) · Zbl 1284.68497
[66] Lin, T.Y.: Data mining and machine oriented modeling: a granular approach. Appl. Intell. 13, 113-124 (2000)
[67] Magner, A., Janson, S., Kollias, G., Szpankowski, W.: On symmetry of uniform and preferential attachment graphs. Electron. J. Comb. 21 (3), 25 (2014) · Zbl 1331.05197
[68] Manickam, N., Singhi, N.M.: First distribution invariants and EKR theorems. J. Comb. Theory Ser. A 48, 91-103 (1988) · Zbl 0645.05023
[69] Marino, G., Chiaselotti, G.: A method to count the positive 3-subsets in a set of real numbers with non negative sum. Eur. J. Comb. 23, 619-629 (2002) · Zbl 1021.05003
[70] McKee, T.A., McMorris, F. R.: Topics in Intersection Graph Theory. S.I.A.M. (Discrete Mathematics and Applications Series) (1999) · Zbl 0945.05003
[71] Pagliani, P., Chakraborty, M.K.: A Geometry of Approximation. Rough Set Theory: Logic, Algebra and Topology of Conceptual Patterns. Springer, Berlin (2008) · Zbl 1213.03002
[72] Pawlak, Z.: Rough Sets—Theoretical Aspects of Reasoning About Data. Kluwer, Dordrecht (1991) · Zbl 0758.68054
[73] Pawlak, Z., Skowron, A.: Rudiments of rough sets. Inf. Sci. 177, 3-27 (2007) · Zbl 1142.68549
[74] Pawlak, Z., Skowron, A.: Rough sets: some extensions. Inf. Sci. 177, 28-40 (2007) · Zbl 1142.68550
[75] Pawlak, Z., Skowron, A.: Rough sets and Boolean reasoning. Inf. Sci. 177, 41-73 (2007) · Zbl 1142.68551
[76] Pedersen, A.S.: Hadwiger’s Conjecture and inflations of the Petersen graph. Discrete Math. 312(24), 3537-3543 (2012) · Zbl 1296.05078
[77] Pedrycz, W., Skowron, A., Kreinovich, V.: Handbook of Granular Computing. Wiley, New York (2008) · Zbl 1142.68551
[78] Pedrycz, W., Hirota, K., Pedrycz, W., Dong, F.: Granular representation and granular computing with fuzzy sets. Fuzzy Sets Syst. 203, 17-32 (2012)
[79] Pedrycz, W.: Granular Computing: Analysis and Design of Intelligent Systems. CRC Press, Boca Raton (2013)
[80] Pisner, E.: Graph Dynamics. Pitman Research Notes in Mathematics Series. Longman, Harlow (1995) · Zbl 1251.37017
[81] Qiu, T., Chen, X., Liu, Q., Huang, H.: Granular computing approach to finding association rules in relational database. Int. J. Intell. Syst. 25, 165-179 (2010) · Zbl 1213.68238
[82] Reidys, C.M.: Sequential dynamical systems over words. Ann. Comb. 10(4), 481-498 (2006) · Zbl 1130.37334
[83] Reidys, C.M.: Combinatorics of sequential dynamical systems. Discrete Math. 308(4), 514-528 (2008) · Zbl 1128.37006
[84] Sampels, M.: Vertex-symmetric generalized Moore graphs. Discrete Appl. Math. 138, 195-202 (2004) · Zbl 1034.05019
[85] Simovici, D.A., Djeraba, C.: Mathematical Tools for Data Mining. Springer, London (2014) · Zbl 1303.68006
[86] Skowron, A., Rauszer, C.: The Discernibility Matrices and Functions in Information Systems, Intelligent Decision Support, Theory and Decision Library series, vol. 11, pp. 331-362. Springer, Netherlands (1992)
[87] Skowron, A., Wasilewski, P.: Information systems in modeling interactive computations on granules. Theor. Comput. Sci. 412, 5939-5959 (2011) · Zbl 1223.68118
[88] Skowron, A., Wasilewski, P.: Interactive information systems: toward perception based computing. Theor. Comput. Sci. 454, 240-260 (2012) · Zbl 1286.68480
[89] Stepaniuk, J.: Rough—Granular Computing in Knowledge Discovery and Data Mining. Springer, Berlin (2008) · Zbl 1173.68646
[90] Tanga, J., Shea, K., Min, F., Zhu, W.: A matroidal approach to rough set theory. Theor. Comput. Sci 471(3), 1-11 (2013) · Zbl 1258.05022
[91] Tyomkyn, M.: An improved bound for the Manickam-Miklós-Singhi conjecture. Eur. J. Comb. 33(1), 27-32 (2012) · Zbl 1308.11030
[92] Wang, C., Chen, D.: A short note on some properties of rough groups. Comput. Math. Appl. 59, 431-436 (2010) · Zbl 1189.20073
[93] Weyl, H.: Symmetry. Princeton University Press, Princeton (1952) · Zbl 0046.00406
[94] Wu, W.Z., Leung, Y., Mi, J.S.: Granular computing and knowledge reduction in formal contexts. IEEE Trans. Knowl. Data Eng. 21, 1461-1474 (2009)
[95] Xiao, W., Parhami, B.: Cayley graphs as models of deterministic small-world networks. Inf. Process. Lett. 97, 115-117 (2006) · Zbl 1184.68060
[96] Yao, Y.Y.: On modeling data mining with granular computing. COMPSAC IEEE 2001, 638-643 (2001)
[97] Yao. J.T., Yao, Y.Y.: A Granular computing approach to machine learning. In: Proceedings of the 1st International Conference on Fuzzy Systems and Knowledge Discovery, pp. 732-736 (2002) · Zbl 0118.18901
[98] Yao, Y.: A Partition model of granular computing. In: Peters, J. F., Skowron, A. (eds.) Transactions on Rough Sets I, Lecture Notes in Computer Science, vol. 3100, Springer, pp. 232-253 (2004) · Zbl 1104.68776
[99] Yao, Y., Zhao, Y.: Discernibility matrix simplification for constructing attribute reducts. Inf. Sci. 179, 867-882 (2009) · Zbl 1162.68704
[100] Yao, Y., Yao, B.X.: Covering based rough set approximations. Inf. Sci. 200, 91-107 (2012) · Zbl 1248.68496
[101] Zadeh, LA; Gupta, N. (ed.); Ragade, R. (ed.); Yager, R. (ed.), Fuzzy sets and information granularity, 3-18 (1979), Amsterdam
[102] Zadeh, L.A.: Towards a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic. Fuzzy Sets Syst. 19, 111-127 (1997) · Zbl 0988.03040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.