Abstract
The operations of structural similarity on the objects with a factual basis presented as ordinary graphs are considered. Conditions are given under which such objects are similar, and a characterization of the set of graphs with isomorphic results of the similarity operation is presented. The proofs use the apparatus of the Galois correspondence associated with the graph.
This is a preview of subscription content, log in via an institution to check access.
Notes
In studies of graph theory, any complete subgraph is often called a clique, but a clique is understood by us as a complete subgraph that is maximal with respect to inclusion.
REFERENCES
Harary, F., Graph Theory, Reading: Addison-Wesley, 1969.
Prisner, E., Hereditary clique-Helly graphs, J. Comb. Math. Comb. Comput., 1993, vol. 14, pp. 216–220.
Riguet, J., Relations binaires, fermetures, correspondances de Galois, Bull. Soc. Math. France, 1948, vol. 76, pp. 114–155. https://doi.org/10.24033/bsmf.1401
Ochan, Yu.S., Some questions of the equivalence of families of sets, Izv. Akad. Nauk SSSR, Ser. Mat., 1942, no. 6, pp. 171–188.
Shreider, Yu.A., Mathematical model of classification, Nauchn.-Tekhn. Inform., Ser. 2. Protsessy Sist., 1968, no. 10, pp. 7–14.
Badekha, I.A., Edge clique coverings of graphs, Prikl. Diskretnaya Mat., 2013, no. 1, pp. 69–83. https://doi.org/10.17223/20710410/19/6
Bonomo, F., Durán, G., and Groshaus, M., Coordinated graphs and clique graphs of clique-Helly perfect graphs, Utilitas Math., 2007, vol. 72, pp. 1–14.
Gusakova, S.M., Formalization of the notion of similarity and its application in intelligent systems, Cand. Sci. (Phys.–Math.) Dissertation, Moscow: VINITI RAN, 1988.
Escalante, F., Über iterierte Clique-Graphen, Abh. aus dem Math. Seminar Universität Hamburg, 1973, vol. 39, no. 1, pp. 58–68. https://doi.org/10.1007/bf02992818
Roberts, F.S. and Spencer, J.H., A characterization of clique graphs, J. Comb. Theory, Ser. B, 1971, vol. 10, no. 2, pp. 102–108. https://doi.org/10.1016/0095-8956(71)90070-0
Escalante, F. and Toft, B., On clique-critical graphs, J. Comb. Theory, Ser. B, 1974, vol. 17, no. 2, pp. 170–182. https://doi.org/10.1016/0095-8956(74)90084-7
Gusakova, S., Canonical representation of similarities, Nauchn.-Tekhn. Inform., Ser. 2. Protsessy Sist., 1987, no. 9, pp. 19–22.
Gusakova, S.M., Analysis of spaces of similarity generated by a fact base in JSM problems, Autom. Doc. Math. Linguist., 2018, vol. 52, no. 1, pp. 44–50. https://doi.org/10.3103/s0005105518010065
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
The author declares that she has no conflicts of interest.
Additional information
Translated by L. Solovyova
About this article
Cite this article
Gusakova, S.M. Structural Similarity of Objects Represented by Ordinary Graphs. Autom. Doc. Math. Linguist. 57, 206–210 (2023). https://doi.org/10.3103/S0005105523040039
Received:
Published:
Issue Date:
DOI: https://doi.org/10.3103/S0005105523040039