Name
Abstract | ||
|---|---|---|
Let $\mathbf{d}=d_1\leq d_2\leq\dots\leq d_n$ be a nondecreasing sequence of $n$ positive integers whose sum is even. Let $\mathcal{G}_{n,\mathbf{d}}$ denote the set of graphs with vertex set $[n]=\{1,2,\dots,n\}$ in which the degree of vertex $i$ is $d_i$. Let $G_{n,\mathbf{d}}$ be chosen uniformly at random from $\mathcal{G}_{n,\mathbf{d}}$. It will be apparent from section 4.3 that all of the sequences we are considering will be graphic. We give a condition on $\mathbf{d}$ under which we can show that whp $\mathcal{G}_{n,\mathbf{d}}$ is Hamiltonian. This condition is satisfied by graphs with exponential tails as well those with power law tails. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1137/080741379 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
random graphs,positive integer,power law tail,vertex set,fixed degree sequence,nondecreasing sequence,hamilton cycles,leq d_n,exponential tail,power law,hamilton cycle,degree sequence,random graph,satisfiability | Integer,Discrete mathematics,Combinatorics,Random graph,Exponential function,Hamiltonian (quantum mechanics),Vertex (geometry),Vertex (graph theory),Cycle graph,Degree (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
24 | 2 | 0895-4801 |
Citations | PageRank | References |
2 | 0.39 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin Cooper | 1 | 857 | 91.88 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| michael krivelevich | 3 | 1688 | 179.90 |