Greedy construction of nearly regular graphs
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.
- A randomized construction of high girth regular graphs
- scientific article; zbMATH DE number 5989950
- On a construction using commuting regular graphs
- On the construction of certain graphs
- scientific article; zbMATH DE number 1817540
- Recursive constructions of small regular graphs of given degree and girth
- scientific article; zbMATH DE number 1933248
- Greedy defining sets of graphs
- On constructing regular distance-preserving graphs
- Fast generation of regular graphs and construction of cages
This page was built for publication: Greedy construction of nearly regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1260772)
