Geodesic
Blocks in Constrained Random Graphs with Fixed Average Degree
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) (2009).

Voir la notice de l'article provenant de la source Episciences

This work is devoted to the study of typical properties of random graphs from classes with structural constraints, like for example planar graphs, with the additional restriction that the average degree is fixed. More precisely, within a general analytic framework, we provide sharp concentration results for the number of blocks (maximal biconnected subgraphs) in a random graph from the class in question. Among other results, we discover that essentially such a random graph belongs with high probability to only one of two possible types: it either has blocks of at most logarithmic size, or there is a \emphgiant block that contains linearly many vertices, and all other blocks are significantly smaller. This extends and generalizes the results in the previous work [K. Panagiotou and A. Steger. Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), pp. 432-440, 2009], where similar statements were shown without the restriction on the average degree. 
@article{DMTCS_2009_special_256_a32,
     author = {Panagiotou, Konstantinos},
     title = {Blocks in {Constrained} {Random} {Graphs} with {Fixed} {Average} {Degree}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)},
     year = {2009},
     doi = {10.46298/dmtcs.2710},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2710/}
}
TY  - JOUR
AU  - Panagiotou, Konstantinos
TI  - Blocks in Constrained Random Graphs with Fixed Average Degree
JO  - Discrete mathematics & theoretical computer science
PY  - 2009
VL  - DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2710/
DO  - 10.46298/dmtcs.2710
LA  - en
ID  - DMTCS_2009_special_256_a32
ER  - 
%0 Journal Article
%A Panagiotou, Konstantinos
%T Blocks in Constrained Random Graphs with Fixed Average Degree
%J Discrete mathematics & theoretical computer science
%D 2009
%V DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2710/
%R 10.46298/dmtcs.2710
%G en
%F DMTCS_2009_special_256_a32
Panagiotou, Konstantinos. Blocks in Constrained Random Graphs with Fixed Average Degree. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) (2009). doi : 10.46298/dmtcs.2710. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2710/

Cité par Sources :