On the Decomposition of Graphs into Complete Bipartite Graphs

摘要

In a complete bipartite decomposition π of a graph, we consider the number ?(v;π) of complete bipartite subgraphs incident with a vertex v. Let ?(G)= $min limits_{pi } max limits_{vin V(G)}$ ?(v;π). In this paper the exact values of ?(G) for complete graphs and hypercubes and a sharp upper bound on ?(G) for planar graphs are provided, respectively. An open problem proposed by P.C. Fishburn and P.L. Hammer is solved as well.