The bigraph decomposition number of a graph. (English) Zbl 0698.05043

Zelinka, Bohdan

Čas. Pěstování Mat. 113, No. 1, 56-59 (1988).

The concept mentioned in the title was introduced by D. West [Graphs and order, NATO ASI Ser., Ser. C 147, 267-350 (1985; Zbl 0568.05042), Problems 3.11 and 3.12]. The bigraph decomposition number of a graph G, denoted by b(G), is understood to be the minimum number of edge-disjoint complete bipartite graphs into which G can be decomposed. First, the author recalls two operations on graphs, the direct product and the weak product of \(G_ 1\) and \(G_ 2\). No notational abbreviations are used here, but \(G_ 1\times G_ 2\) usually stands for the first one and \(G_ 1\oplus G_ 2\) for the second one. Among other things, it is shown that for graphs without isolated vertices the following inequalities hold: \(b(G_ 1\times G_ 2)\leq 2b(G_ 1)b(G_ 2)\), \(b(G_ 1\oplus G_ 2)\leq | V(G_ 1)| b(G_ 2)+| V(G_ 2)| b(G_ 1)\).

MSC:

05C35	Extremal problems in graph theory
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

bigraph decomposition number; minimum number of edge-disjoint complete bipartite graphs

Citations:

Zbl 0568.05042