Sharp bounds for decompositions of graphs into complete r-partite subgraphs
Sharp bounds for decompositions of graphs into complete r-partite subgraphs
复制标题
DOI：
10.1002/(sici)1097-0118(199604)21:4
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
D. Gregory;K. V. Meulen
中科院分区：
文献类型：
--
作者：
D. Gregory;K. V. Meulen
设G是一个n阶图，r = 2 2，m（G）表示划分边集f（G）所需的最小完全多部子图数，其中r为或少于r个部分.在确定m（G）时，我们可以假设G的任何两个顶点都不具有相同的邻集。对于这类约化图G，我们证明了m，（G）2 log，（n + rl）/r.此外，对于每个k2 0和r2 2，存在唯一的约化图G = G（r，k），其中m，（G）= k，且等式成立.最后给出了已知特征值界m，（G）2 max{n+（G），n-（G）/（r I）}的一个简短证明，并证明了当G = G（r，k）时等式成立.
If G is a graph on n vertices and r 2 2, we let m,(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, f(G). In determining m,(G), we may assume that no two vertices of G have the same neighbor set. For such reduced graphs G, w e prove that m,(G) 2 log,(n + r l)/r. Furthermore, for each k 2 0 and r 2 2, there is a unique reduced graph G = G(r, k) with m,(G) = k for which equality holds. We conclude with a short proof of the known eigenvalue bound m,(G) 2 max{n+(G), n-(G)/(r I)}, and show that equality holds if G = G(r, k).