Geodesic
The minimal vertex extensions for colored complete graphs
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika, Tome 13 (2021) no. 4, pp. 77-89 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The article proposes the results of the search for minimal vertex extensions of undirected colored complete graphs. The research topic is related to the modelling of full fault tolerant technical systems with a different type of their objects in the terminology of graph theory. Let a technical system be $\Sigma$, then there is a graph $G(\Sigma)$, which vertices reflects system's objects and edges reflects connections between these objects. Type of each object reflected in a mapping of some color from $F = \{1,2\dots,i\}$ to the corresponding vertex. System's $\Sigma$ vertex extension is a graph $G(\Sigma)$ which contains additional vertices. System reflected by graph $G(\Sigma)$ can work even if there are $k$ faults of its objects. Complete graph is a graph where each two vertices have an edge between them. Complete graphs have no edge extensions because there is no way to add additional edge to the graph with a maximum number of edges. In other words, the system reflected by some complete graph cannot be able to resist connection faults. Therefore the article research is focused on vertex extensions only. There is a description of vertex extensions existence condition for those colored complete graphs. This paper considers generating schemes for such minimal vertex extensions along with formulas, which allows to calculate number of additional edges to have an ability to construct minimal vertex extension.
Keywords: graph vertex extensions, complete graphs, graph minimal extensions, colored graph extensions, colored graphs. 
@article{VYURM_2021_13_4_a8,
     author = {P. V. Razumovsky and M. B. Abrosimov},
     title = {The minimal vertex extensions for colored complete graphs},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matematika, mehanika, fizika},
     pages = {77--89},
     year = {2021},
     volume = {13},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURM_2021_13_4_a8/}
}
TY  - JOUR
AU  - P. V. Razumovsky
AU  - M. B. Abrosimov
TI  - The minimal vertex extensions for colored complete graphs
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika
PY  - 2021
SP  - 77
EP  - 89
VL  - 13
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VYURM_2021_13_4_a8/
LA  - ru
ID  - VYURM_2021_13_4_a8
ER  - 
%0 Journal Article
%A P. V. Razumovsky
%A M. B. Abrosimov
%T The minimal vertex extensions for colored complete graphs
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika
%D 2021
%P 77-89
%V 13
%N 4
%U http://geodesic.mathdoc.fr/item/VYURM_2021_13_4_a8/
%G ru
%F VYURM_2021_13_4_a8
P. V. Razumovsky; M. B. Abrosimov. The minimal vertex extensions for colored complete graphs. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika, Tome 13 (2021) no. 4, pp. 77-89. http://geodesic.mathdoc.fr/item/VYURM_2021_13_4_a8/

[1] A. Avižienis, “Fault-tolerance and fault-intolerance: Complementary approaches to reliable computing”, ACM SIGPLAN Notices, 10:6 (1975), 458–464 | DOI

[2] J.P. Hayes, “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., C-25:9 (1976), 875–884 | DOI

[3] F. Harary, J.P. Hayes, “Edge fault tolerance in graphs”, Networks, 23:2 (1993), 135–142 | DOI | Zbl

[4] F. Harary, J.P. Hayes, “Node fault tolerance in graphs”, Networks, 27:1 (1996), 19–23 | 3.0.CO;2-H class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | Zbl

[5] M.B. Abrosimov, Grafovye modeli otkazoustoichivosti, Izd-vo Sarat. Un-ta, Saratov, 2012, 189 pp.

[6] P.V. Razumovskii, M. B. Abrosimov, “Postroenie tsvetnykh grafov bez proverki na izomorfizm”, Izvestiya Saratovskogo universiteta. Novaya seriya. Seriya: Matematika. Mekhanika. Informatika, 21:2 (2021), 267–277 | Zbl

[7] P.V. Razumovsky, “The search for minimal edge 1-extension of an undirected colored graph”, Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika, 21:3 (2021), 400–407

[8] P.V. Razumovskii, “O minimalnykh vershinnykh 1-rasshireniyakh dvukhtsvetnykh polnykh grafov”, Materialy Mezhdunarodnogo molodezhnogo nauchnogo foruma «LOMONOSOV-2021», MAKS Press, M., 2021 https://lomonosov-msu.ru/archive/Lomonosov_2021/data/22112/124513_uid563707_report.pdf

[9] A.M. Bogomolov, V.N. Salii, Algebraicheskie osnovy teorii diskretnykh sistem, Nauka, M., 1997, 367 pp.