Gallai图中的圈与完全k部图（英文）

设G是一个E(G)非空的图。图G的Gallai图Gal(G)是把G的边集作为它的点集,若G中的两条边e和f相邻但不在同一个三角形中,则Gal(G)中的两个不同顶点e和f相邻。显然,图G的Gallai图Gal(G)是线图L(G)的一个生成子图。本文刻画Gallai图分别是圈和完全k-部图的原图。

D-图的特征

给出图G当def(G)≠0时,level(G)分别为0,1,2的充要条件,并给出路、星图、圈、哈密尔顿图和三正则图的level.

图的最大匹配个数的下界

设G是一个具有n个顶点且最大匹配为k-匹配的连通图,这里n≥2k+1.证明了G至少有n-2k+1个互不相同的最大匹配,并且刻画了恰好具有n-2k+1个最大匹配的图.