All Ramsey numbers for brooms in graphs (Q311540): Difference between revisions

Summary: For \(k,\ell\geqslant 1\), a broom \(B_{k,\ell}\) is a tree on \(n=k+\ell\) vertices obtained by connecting the central vertex of a star \(K_{1,k}\) with an end-vertex of a path on \(\ell-1\) vertices. As \(B_{n-2,2}\) is a star and \(B_{1,n-1}\) is a path, their Ramsey number have been determined among rarely known \(R(T_n)\) of trees \(T_n\) of order \(n\). \textit{P. Erdős} [Congr. Numerantium 35, 283--293 (1982; Zbl 0513.05038)] determined the value of \(R(B_{k,\ell})\) for \(\ell\geqslant 2k\geqslant 2\). We shall determine all other \(R(B_{k,\ell})\) in this paper, which says that, for fixed \(n\), \(R(B_{n-\ell,\ell})\) decreases first on \(1\leqslant\ell \leqslant 2n/3\) from \(2n-2\) or \(2n-3\) to \(\lceil\frac{4n}{3}\rceil-1\), and then it increases on \(2n/3 < \ell\leqslant n\) from \(\lceil\frac{4n}{3}\rceil-1\) to \(\lfloor\frac{3n}{2}\rfloor -1\). Hence \(R(B_{n-\ell,\ell})\) may attain the maximum and minimum values of \(R(T_n)\) as \(\ell\) varies.