2. Home
  3. ARCHIVE
  4. 2024
  5. VOL 46, NO 6 (2024)
  6. pp. 03-07

On the connectivity of quasi-random graphs

O.D. Glukhov, candidate physics and mathematics of science
National Aviation University of Ukraine
Ukraine, 03058, Kyiv, Lubomyra Huzara Avenue, 1
tel. 0677348008, e-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

Èlektron. model. 2024, 46(6):03-07

https://doi.org/10.15407/emodel.46.06.003

ABSTRACT

Graph theory is widely used to study the structural properties of complex discrete systems. Thus, to assess the ability of a system to maintain certain structural properties when the connections between its elements are broken, it is important to study different types of graph connectivity. Quasi-random graphs are a model of complex discrete systems with random disruptions of connections between system elements. The problem of estimating the probability of connectivity in quasi-random graphs is considered. The concepts of multiframe and polynomial of a connected graph are introduced. A new estimator of connectivity for quasi-random graphs based on a 3-edge connected graphs is presented.

KEYWORDS

complex discrete system, quasi-random graph, graph multiframe, connected graph polynomial.

REFERENCES

  1. Frieze A, Karoński M. Introduction to Random Graphs. Cambridge University Press; 2024. P. 576.
  2. Karoński M., Frieze A. Random Graphs and Networks: A First Course. Cambridge University Press, 2023. 220 p.
    https://doi.org/10.1017/9781009260268
  3. Glukhov, O., Korostil, Ju. (2004), Strukturna bezpeka skladnyh dyskretnyh system pry vypadkovyh vidmovah [Structural safety of complex discrete systems with random failu­res], Modelirovanie ta informaziyni tehnologii, IPME NANU, v. 27, Kyiv, p. 91-95.
  4. Glukhov A.D. Kvazisluchaynie grafy I strukturnaya ustoychivost slozhnyh diskretnyh system// Elektronnoe modelirovanie, v. 38, № 5, 2016, с. 35-41.
    https://doi.org/10.15407/emodel.38.05.035
  5. Glukhov O.D. Teorema pro vypadkovi perestanovky ta deyaki yii zastosuvannya// Elektronnoe modelirovanie, v. 43, № 2, 2021, с. 29-36.
    https://doi.org/10.15407/emodel.43.02.029
  6. Diestel R. Graph Theory, Springer-Verlag, Heidelberg, Graduate Texts in Mathematics, v. 173, 2017. 428 p.
    https://doi.org/10.1007/978-3-662-53622-3_7

Full text: PDF