scientific article; zbMATH DE number 1109398

From MaRDI portal
Publication:4374707





This note is an addendum to the author's paper [Ars Comb. 38, 292-298 (1994; Zbl 0817.05019)]. For positive integers \(n,t,m\), \(f(n,t,m)\) is defined as the minimum number of complete \(m\)-partite graphs on the same \(n\)-element set \(V\) such that each pair of vertices of \(V\) occurs as an edge in precisely \(t\) of the graphs (\(f(n,t,m)=\infty \) if such a decomposition does not exist). As for the lower bound on \(f(n,t,m)\), the author says: ``Combining the proof of Theorem 1 of \textit{Q.-X. Huang} [J. Graph Theory 15, No. 1, 1-6 (1991; Zbl 0758.05082)] with that of Theorem 1 of \textit{D. Pritikin} [J. Graph Theory 10, 197-201 (1986; Zbl 0592.05030)], we obtain \(f(n,t,m)\geq \max \{\lceil (n-1)/(m-1)\rceil ,t\}\). Several upper bounds for \(f(n,t,m)\) are derived for special parameters \(n,t,m\), depending on the existence of affine designs of certain types. As a consequence it is proved that if \(m\) is a prime power then for \(n\geq 2\), \(f(k(m^n-1)+1-i,m^{n-1},m)=k(m^n-1)/(m-1)\) if \(i\leq m-2\), and \(f(k(m^n-1)+1-i,m^{n-1},m)\leq k(m^n-1)/(m-1)\) if \(1\leq k\leq s\) and \(m-1\leq i\leq k(m^{n-1}-1)\), or \(s+1\leq k\) and \(m-1\leq i \leq m^n-2\) (here \(s=\lceil (m^n-1)/(m^{n-1}-1)\rceil -1\)).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4374707)