Probability model of connectedness for graphs with logarithmical degree
Abstract
For a graph G of order N, an integer k with 0≤ k< N and a real number p with 0≤ p≤ 1, let p(G,k) and t(G,p) be the probabilities that G is disconnected when k vertices are removed randomly and when each vertex is removed independently with probability p, respectively. We deduce a formula of p(G,k) for Harary graphs and show that the phase transition on p(G,k) and t(G,p) occurs in the class that has logarithmical degree. We also perform simulations on p(G,k) for the Hypercube and randomly generated graphs of the same scale, which suggests that the regularity is a key structural feature that guarantees nice performance on p(G,k). In particular, the Hypercubes have better performance than regular graphs, on average. Surprisingly, Harary graphs, known to be super-connected, have neither better performance than Hypercubes nor even than the average of regular graphs.
Related
- The singularity probability of dense random regular graphs
- Explicit M-polynomial and degree-based topological indices of Hanoi graphs
- Tuza's Conjecture for Graphs of Maximum Degree at Most 10
- Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
- Construction of Basic Probability Assignment for D-S Rough Sets Based on Inclusion-Degree Gradient
BibTeX
@misc{jia2026probability,
title = {{Probability model of connectedness for graphs with logarithmical degree}},
author = {Huanshen Jia and Jianguo Qian},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07581},
eprint = {2611.07581},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07581},
}
RIS
TY - UNPB
TI - Probability model of connectedness for graphs with logarithmical degree
AU - Huanshen Jia
AU - Jianguo Qian
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07581
UR - https://arxiv.org/abs/2611.07581
AB - For a graph G of order N, an integer k with 0≤ k< N and a real number p with 0≤ p≤ 1, let p(G,k) and t(G,p) be the probabilities that G is disconnected when k vertices are removed randomly and when each vertex is removed independently with probability p, respectively. We deduce a formula of p(G,k) for Harary graphs and show that the phase transition on p(G,k) and t(G,p) occurs in the class that has logarithmical degree. We also perform simulations on p(G,k) for the Hypercube and randomly generated graphs of the same scale, which suggests that the regularity is a key structural feature that guarantees nice performance on p(G,k). In particular, the Hypercubes have better performance than regular graphs, on average. Surprisingly, Harary graphs, known to be super-connected, have neither better performance than Hypercubes nor even than the average of regular graphs.
ER -