zbMATH — the first resource for mathematics

On a problem of E.  Prisner concerning the biclique operator. (English) Zbl 1003.05048
Summary: The symbol \(K(B,C)\) denotes a directed graph with vertex set \(B\cup C\) for two (not necessarily disjoint) vertex sets \(B,C\) in which an arc goes from each vertex of \(B\) to each vertex of \(C\). A subdigraph of a digraph \(D\) which has this form is called a bisimplex in \(D\). A biclique in \(D\) is a bisimplex in \(D\) which is not a proper subgraph of any other one and in which \(B\not =\emptyset \) and \(C\not = \emptyset \). The biclique digraph \(\vec C(D)\) of \(D\) is the digraph whose vertex set is the set of all bicliques in \(D\) and in which there is an arc from \(K(B_1, C_1)\) to \(K(B_2,C_2)\) if and only if \(C_1 \cap B_2 \not = \emptyset \). The operator which assigns \(\vec C(D)\) to \(D\) is the biclique operator \(\vec C\). The paper solves a problem of E. Prisner concerning the periodicity of \(\vec C\).

05C20 Directed graphs (digraphs), tournaments
Full Text: EuDML