А.D. Glukhov
Èlektron. model. 2021, 43(2):29-36
ABSTRACT
In the study of the structural properties of complex discrete systems, graph theory is widely used. Thus, to assess the ability of a system to retain certain structural properties when breaking the relationships between its elements, it is important to study different types of connectivity of the graph and their generalizations. Of particular interest is the question of how likely it is that a given graph will remain connected or have a sufficiently large connected component when a certain number of its edges are removed? In this paper, the theorem on random permutations is proved and a number of its applications in graph theory are considered. The operation of "permutation gluing of graphs" is introduced. It is shown how with the help of such gluing of two given graphs of a rather simple structure it is possible to construct graphs which with sufficient probability have the necessary connected properties. In particular, the constructions are described, which with a given probability allow to build expanders as well as graphs of greater connectivity. This approach allows you to synthesize graphs with certain properties as a result of some stochastic process followed by selection.
KEYWORDS
complex discrete system, graph, permutation group.
REFERENCES
- Glukhov, (2016), “Quasi-Random Graphs and Structural Stability of Complex Discrete Systems”, Elektronnoe modelirovaniye, Vol. 38, no. 5, pp. 35-41.
https://doi.org/10.15407/emodel.38.05.035 - Glukhov, O. and Korostil, Ju. (2004), “Structural safety of complex discrete systems with random failures”, Modelirovanie ta informaziyni tehnologii, Vol. 27, pp. 91-95.
- Diestel, R. (2000), Graph Theory, Springer-Verlag, NY, USA.
- Erdős, P. and Rényi, A. (1959), “On Random Graphs I”, Publicationes Mathematicae Debrecen, Vol. 6, pp. 290-297.
- Glukhov, O. (2008), “On the application of permutation groups in some combinatorial problems”, Ukrayinskyy matematychnyy zhurnal, Vol. 60, no. 11, pp.1568-1571.
https://doi.org/10.1007/s11253-009-0173-5 - Kartesi, F. (1980), Vvedenie v konechnye geometrii [Introduction to finite geometries], Nauka, Moscow, Russia.
- Hoory, S., Linial, N. and Wigderson, A. (2006), “Expander graphs and their applications”, Bulletin of the American Mathematical Society, Vol. 43, no. 4. pp. 439-561.
https://doi.org/10.1090/S0273-0979-06-01126-8 - Diniz, E.A, Karzanov, A.V. and Lomonosov, M.V. (1976), “About a structure of a system of minimum cut sets of the graph”, Issledovaniya po diskretnoy optimizatsii, pp. 290-306.
- Sachkov, V. (1978), Veroyatnostnye metody v kombinatornom analise [Probabilistic methods in combinatorial analysis], Nauka, Moscow, Russia.