This page collects some good ultra-sparse graphs that were obtained with a randomized Progressive
Edge Growth (PEG) algorithm [1]. By ultra-sparse graph, we mean a bipartite graph with two constant connection
degrees (dv,dc), and with dv=2. When the obtained graph has minimum size (smallest number of nodes), we
indicate that the size is minimum*.
These particular graphs can have multiple possible applications, including building good non-binary LDPC
codes in high order fields [2,3]. The graphs are stored in the MacKay A-list format
(
http://www.inference.phy.cam.ac.uk/mackay/CodesFiles.html).
[1] A. Venkiah, D. Declercq and C. Poulliat, "Design of Cages with a Randomized Progressive Edge-Growth Algorithm", in IEEE Commun. Letters, vol. 12(4), pp. 1-3, April 2008.
[2] X.-Y. Hu, E. Eleftheriou, D.-M. Arnold, "Regular and Irregular Progressive Edge-Growth Tanner Graphs", IEEE Trans. Info. Theo., 51(1), pp. 386-398, January 2005.
[3] C. Poulliat, M. Fossorier and D. Declercq, "Design of regular (2,dc)-LDPC codes over GF(q) using their binary images", accepted in IEEE Trans. Commun., 2007.
| [girth=6,N=6] |
graph with (dv=2,dc=3,girth=6) and minimum* size N=6 |
| [girth=8,N=9] |
graph with (dv=2,dc=3,girth=8) and minimum* size N=9 |
| [girth=10,N=15] |
graph with (dv=2,dc=3,girth=10) and minimum* size N=15 |
| [girth=12,N=21] |
graph with (dv=2,dc=3,girth=12) and minimum* size N=21 |
| [girth=14,N=36] |
graph with (dv=2,dc=3,girth=14) and minimum* size N=36 |
| [girth=16,N=45] |
graph with (dv=2,dc=3,girth=16) and minimum* size N=45 |
| [girth=18,N=114] |
graph with (dv=2,dc=3,girth=18) and size N=114 |
| [girth=20,N=201] |
graph with (dv=2,dc=3,girth=20) and size N=201 |
| [girth=22,N=447] |
graph with (dv=2,dc=3,girth=22) and size N=447 |
| [girth=24,N=726] |
graph with (dv=2,dc=3,girth=24) and size N=726 |
| [girth=26,N=1602] |
graph with (dv=2,dc=3,girth=26) and size N=1602 |
| [girth=6,N=10] |
graph with (dv=2,dc=4,girth=6) and minimum* size N=10 |
| [girth=8,N=16] |
graph with (dv=2,dc=4,girth=8) and minimum* size N=16 |
| [girth=10,N=38] |
graph with (dv=2,dc=4,girth=10) and minimum* size N=38 |
| [girth=12,N=52] |
graph with (dv=2,dc=4,girth=12) and minimum* size N=52 |
| [girth=14,N=260] |
graph with (dv=2,dc=4,girth=14) and size N=260 |
| [girth=16,N=160] |
graph with (dv=2,dc=4,girth=16) and minimum* size N=160 |
| [girth=6,N=15] |
graph with (dv=2,dc=5,girth=6) and minimum* size N=15 |
| [girth=8,N=25] |
graph with (dv=2,dc=5,girth=8) and minimum* size N=25 |
| [girth=10,N=90] |
graph with (dv=2,dc=5,girth=10) and size N=90 |
| [girth=12,N=105] |
graph with (dv=2,dc=5,girth=12) and minimum* size N=105 |
| [girth=6,N=21] |
graph with (dv=2,dc=6,girth=6) and minimum* size N=21 |
| [girth=8,N=36] |
graph with (dv=2,dc=6,girth=8) and minimum* size N=36 |
| [girth=10,N=189] |
graph with (dv=2,dc=6,girth=10) and size N=189 |
| [girth=12,N=186] |
graph with (dv=2,dc=6,girth=12) and minimum* size N=186 |
| [girth=6,N=28] |
graph with (dv=2,dc=7,girth=6) and minimum* size N=28 |
| [girth=8,N=49] |
graph with (dv=2,dc=7,girth=8) and minimum* size N=49 |
| [girth=10,N=385] |
graph with (dv=2,dc=7,girth=10) and size N=385 |
| [girth=12,N=840] |
graph with (dv=2,dc=7,girth=12) and size N=840 |