On Stability of the Independence Number of a Certain Distance Graph

被引：0

作者：

P. A. Ogarok

A. M. Raigorodskii

机构：

[1] Department of Discrete Mathematics,

[2] Faculty of Innovation and High Technology,undefined

[3] Moscow Institute of Physics and Technology (State University),undefined

[4] Phystech School of Applied Mathematics and Informatics and Laboratory of Advanced Combinatorics and Network Applications,undefined

[5] Moscow Institute of Physics and Technology (State University),undefined

[6] Department of Mathematical Statistics and Random Processes,undefined

[7] Faculty of Mechanics and Mathematics,undefined

[8] Lomonosov Moscow State University,undefined

[9] Caucasus Mathematical Center,undefined

[10] Adyghe State University,undefined

[11] Institute of Mathematics and Computer Science,undefined

[12] Buryat State University,undefined

来源：

Problems of Information Transmission | 2020年 / 56卷

关键词：

random graph; distance graph; independence number;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We study the asymptotic behavior of the independence number of a random subgraph of a certain (r, s)-distance graph. We provide upper and lower bounds for the critical edge survival probability under which a phase transition occurs, i.e., large new independent sets appear in the subgraph, which did not exist in the original graph.

引用

页码：345 / 357

页数：12

共 50 条

[21] Adjacency Rank and Independence Number of a Signed Graph
Li, Xueliang
Xia, Wen
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2020, 43 (01) : 993 - 1007
[22] On the independence number of distance graphs with vertices in {−1, 0, 1}n
A. É. Guterman
V. K. Lyubimov
A. M. Raigorodskii
S. A. Usachev
Mathematical Notes, 2009, 86 : 744 - 746
[23] Spectral Inequalities on Independence Number, Chromatic Number, and Total Chromatic Number of a Graph
Li, Rao
JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2015, 18 (1-2) : 41 - 46
[24] Bounds on the Clique and the Independence Number for Certain Classes of Graphs
Brimkov, Valentin E.
Barneva, Reneta P.
MATHEMATICS, 2024, 12 (02)
[25] The Q-minimizer graph with given independence number
Hu, Yarong
Lou, Zhenzhen
Ning, Wenjie
LINEAR ALGEBRA AND ITS APPLICATIONS, 2024, 685 : 1 - 23
[26] Laplacian eigenvalue distribution of a graph with given independence number
Choi, Jinwon
Suil, O.
Park, Jooyeon
Wang, Zhiwen
APPLIED MATHEMATICS AND COMPUTATION, 2023, 448
[27] WEIGHTED MATRIX EIGENVALUE BOUNDS ON THE INDEPENDENCE NUMBER OF A GRAPH
Elzinga, Randall J.
Gregory, David A.
ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2010, 20 : 468 - 489
[28] Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank
Wang, Long
Wong, Dein
DISCRETE APPLIED MATHEMATICS, 2014, 166 : 276 - 281
[29] DISTANCE LAPLACIAN EIGENVALUES OF GRAPHS, AND CHROMATIC AND INDEPENDENCE NUMBER
Pirzada, Shariefuddin
Khan, Saleem
REVISTA DE LA UNION MATEMATICA ARGENTINA, 2024, 67 (01): : 145 - 159
[30] On the independence number of distance graphs with vertices in {-1,0,1} n
Guterman, A. E.
Lyubimov, V. K.
Raigorodskii, A. M.
Usachev, S. A.
MATHEMATICAL NOTES, 2009, 86 (5-6) : 744 - 746

← 1 2 3 4 5 →