On a problem of Hering concerning orthogonal covers of \({\mathbf K}_ n\) (Q1903018)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On a problem of Hering concerning orthogonal covers of \({\mathbf K}_ n\)
scientific article

    Statements

    On a problem of Hering concerning orthogonal covers of \({\mathbf K}_ n\) (English)
    0 references
    18 June 1996
    0 references
    A Hering configuration of type \(k\) and order \(n\) is a factorization of the complete digraph \({\mathbf K}_n\) into \(n\) factors each of which consists of an isolated vertex and the vertex-disjoint union of directed \(k\)-cycles, which has the additional property that for any pair of distinct factors, say \({\mathbf G}_i\) and \({\mathbf G}_j\), there is precisely one pair of vertices, say \(\{a, b\}\), such that \({\mathbf G}_i\) contains the directed edge \((a, b)\) and \({\mathbf G}_j\) contains the directed edge \((b, a)\). Clearly, a necessary condition for a Hering configuration is \(n\equiv 1\text{ mod }k\). It is shown that for any fixed \(k\), this condition is asymptotically, and, it is shown to be always sufficient for \(k= 4\). It was shown in \textit{B. Ganter} and the second author [On two conjectures of Demetrovics, Füredi, and Katona, concerning partitions, Discrete Math. 88, No. 2/3, 149-155 (1991; Zbl 0739.05004)] that the condition is sufficient for \(k= 3\) with the exception \(n= 10\), where a factorization does not exist, see \textit{A. Rausche} [On the existence of special block designs, Rostocker Math. Kolloq. 35, 13-30 (1988; Zbl 0688.05012)].
    0 references
    0 references
    0 references
    0 references
    0 references
    problem of Hering
    0 references
    orthogonal covers
    0 references
    Hering configuration
    0 references
    factorization
    0 references
    complete digraph
    0 references
    0 references
    0 references
    0 references