字典积图的任意可分性

摘要

给定n个顶点的图G,对于满足■ni=n的任意一个正整数序列(n1, n2,···, nk),如果都存在顶点集V (G)的划分(V1, V2,···, Vk),满足Vi导出的子图G[Vi]是连通的,并且|Vi|=ni,其中1≤i≤k,则称图G是任意可分图(简称为AP).两个图G和H的字典积图记为G?H,其顶点集为V (G)×V (H),(g, h)(g, h)是G?H的一条边当且仅当gg∈E(G)或者g=g且hh∈E(H).讨论了可迹图和任意可分图的字典积图的任意可分性,证明了对于最大度至多为n+1的树T,如果T有一条路P满足全部度数为(T)的顶点属于顶点集V (P),则字典积图T?Pn是任意可分图;如果G是一个可迹图且H是任意可分图,则图G?H是任意可分图;如果G=S(2,a,b)是一个满足2≤a≤b的任意可分星型树,则图G?G是任意可分图;如果G是哈密顿图且H是一个图,则G?H是任意可分图.

关键词

图的任意可分性 / 字典积图 / 星型树 / 可迹图