Name
Abstract | ||
|---|---|---|
Consider the set $\mathcal{SG}(Q_k)$ of all graphs whose vertices are labeled with nonidentity elements of the group $Q_k=\mathbb{Z}_2^k$ so that there is an edge between vertices with labels $a$ and $b$ if and only if the vertex labeled $a+b$ is also in the graph. Note that edges always appear in triangles since $a+b=c$, $b+c=a$, and $a+c=b$ are equivalent statements for $Q_k$. We define the random cubic sum graph $\mathcal{SG}(Q_k,p)$ to be the probability space over $\mathcal{SG}(Q_k)$ whose vertex sets are determined by $\Pr[x\in V]=p$ with these events mutually independent. As $p$ increases from 0 to 1, the expected structure of $\mathcal{SG}(Q_k,p)$ undergoes radical changes. We obtain thresholds for some graph properties of $\mathcal{SG}(Q_k,p)$ as $k\rightarrow\infty$. As with the classical random graph, the threshold for connectivity coincides with the disappearance of the last isolated vertex. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1137/090746227 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
random cubic sum graph,probability space,graph property,classical random graph,vertex set,expected structure,equivalent statement,undergoes radical change,nonidentity element,random cubic sum graphs,last isolated vertex,random graph,discrete mathematics,connectivity | Graph,Discrete mathematics,Combinatorics,Random graph,Graph property,Probability space,Vertex (geometry),Cubic graph,Connectivity,Mathematics,Independence (probability theory) | Journal |
Volume | Issue | ISSN |
24 | 3 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Beveridge | 1 | 55 | 8.21 |