Greedy construction of nearly regular graphs (Q1260772)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Greedy construction of nearly regular graphs |
scientific article |
Statements
Greedy construction of nearly regular graphs (English)
0 references
25 August 1993
0 references
The authors study a sequence of nearly regular graphs which are built starting with the empty graph on \(n\) vertices and adding randomly one single edge at each step in such a way that at each step the new constructed edge must join some vertices with minimum degrees. The function \(f(n,m)\) is defined as the largest difference of degrees in such constructed graphs with \(n\) vertices and \(m\) edges. Main results: Theorem 1. For any positive integer \(d\) there exist positive integers \(n\), \(m\) such that \(f(n,m)\geq d\). Theorem 2. \[ \begin{alignedat}{4} &f(4k,&&\;4k^ 2+9k-3)&&\geq 3 \qquad &&\text{for }11\leq k\\ & f(4k+1,&&\;4k^ 2+10k)&&\geq 3\qquad &&\text{for }9\leq k\\ & f(4k+2,&&\;4k^ 2+11k+3) &&\geq 3\qquad &&\text{for }4\leq k\\ & f(4k+3,&&\;4k^ 2+14k+6) &&\geq 3\qquad &&\text{for }10\leq k\end{alignedat} \] Theorem 3. \[ \begin{alignedat}{3} &f(4k, &&\;4k^ 2+9k-4) &&\leq 2\\ &f(4k+1, &&\;4k^ 2+10k-1) &&\leq 2\\ & f(4k+2, &&\;4k^ 2+11k+2) &&\leq 2\\ & f(4k+3, &&\;4k^ 2+14k+5) &&\leq 2\end{alignedat} \] The paper closes with some supplementary results and problems.
0 references
matching
0 references
tree
0 references
factor
0 references
coloring
0 references
nearly regular graphs
0 references
degrees
0 references