共查询到20条相似文献,搜索用时 27 毫秒
1.
2.
3.
全着色边临界图的全色数 总被引:2,自引:0,他引:2
定义 对于简单图G(V,F),(?)e∈E(G),当 χ_T(G)>△(G)+1, χ_T(G-e)=△(G-e)+1时,则称G为全着色边临界图.其中厶(G)表示G的最大度,χ_T(G)表示G的全色数。 引理1 对图G(V,E)。(?)e∈E(G),若△(G)≥2,则 χ_T(G-e)≤χ_T(G)≤χ_T(G-e)+1。 定理1 若图G(V,E)是全着色边临界图,则 χ_T(G)=△(G)+2。 相似文献
4.
5.
6.
一、引言 我们讨论的图均为简单图,K和α分别表示图的连通度和独立数。我们采用文献[1]的术语和符号,并记G_n~k={G丨G为n阶k-连通图},H_e={G丨G是Hamilton连通图},用P_H(u,v)表示从u到v的Hamilton路。图G中的路P称为控制路,如果G[P(G)\V(P)]均为孤立点.给出图G中的一条(x,y)-路P,总认为是从x到y定向,表示的反向。若u,v∈V(P),则uv表示P上沿从u到v的路。又u≠y,v≠x,则u~+和v~-分 相似文献
7.
本文所涉及的图都是有限无向简单图。设G是一个图,总用V(G)、E(G)分别表示G的顶点集、边集,而p=|V(G)|。设UN(G),总用G[U]表示G中由U导出的子图。图G称为无爪的,如果对于任意UV(G),总有G[U]K_(1.3)。图G称为m路 相似文献
8.
定义1对简单图G(V,E),E的分划}普1‘·’‘“,+·““‘,‘”·E一UE,, 讼一t使得E,的导出图G[E;](i一l,2,不含圈的最小n,称为‘的线荫度,。‘(G). 定理1若‘是外平面图,则 a‘(G)成2. 定理2对简单图G(V,E),且下界不可改进.其中P一}V(G).,「x1为不小于x的最小整数.…,,)简记作图和补图线荫度的关系@张忠辅$兰州铁道学院
@王建方$中国科学院应用数学研究所!北京
@徐登洲$西北师范大学~~ 相似文献
9.
§1.引言 设G=(V,E)是简单图,V和E分别是G的顶点集和边集。n=|V|称为顶点数,m=|E|称为边数。设S(?)V,从G中去掉S得到的子图,用G-S表示,就是V-S生成的子图。 G的两条边e_1,e_2若有一个公共端点,称为是关联的.设F(?)E是G的边子集,F中任 相似文献
10.
对于简单图G(V,E),使得VUE的任何两个相邻或关联的元素都着有不同颜色的最少颜色数,称做图G的全色数,简记作x_T(G).定理1 若G为无割点的外平面图,△(G)≥4,则G必至少有下列情况之一:(ⅰ) G有两个2度点相邻;(ⅱ) G有一个2度点与3度点相邻;(ⅲ) G有两个2度点共邻于一个4度点, 相似文献
11.
12.
设G是简单无向图。V(G),E(G)分别表示G的顶点集和边集。如果|E(G)|=|V(G)|-K,则称G是(P,P—K)图。对于同阶图对{G_1,G_2},如果G_1与的某个子图同构,则称图对{G_1,G_2}是可包装 相似文献
13.
本文所涉及的图都是有限无向简单图。设G是一个图,总用V(G)、E(G)、c(G)分别表示G的顶点集、边集、周长,而令p=|V(G)|。设U(?)(G),总用G[U]表示G中由U导出的子图。如果对于任意U(?)V(G),总有G[U](?)K_(1,3),则称G为无爪图。设λ=min{d(u)+d(v)|u,v∈V(G),uv(?)E(G)},δ=min{d(u)|u∈V(G)},其 相似文献
14.
定义1 对图G(V,E)和自然数n,对其长度不大于n的路上所有点(或所有边、或所有点和所有边)均染为不同色,其所用颜色的最少数目称为G的n-色数(或n-边色数、或n-全色数),简记作X_n(G)(或X′_n(G)、或X_n~T(G))。 相似文献
15.
所谓一个可分组设计GD(k,m;v)是指这样一个有序三元组(V,G,B),其中V是一个v元集,G是V的一些m子集(称作组)的集合,B是V的一些k子集的集合,使得 (ⅰ) G构成V的一个划分; (ⅱ) V中任意一对取自G中不同组的元素恰好在唯一的一个区组中相遇。 给定一个GD(k,m;v),若B中的若干个区组构成V的一个划分,则称为一个平行 相似文献
16.
设G是一个图,且t是一个实数,若对每个,其中k(G—S)是G—S的分支数,则称G是t坚韧图(t-tough graph)。显然,1坚韧图是2连通的。用δ,κ,α分别表示G的最小度、连通度和独立数,利用以上记号,有如下定理: 定理1 设G是p阶1坚韧图,若δ≥ 相似文献
17.
本文只讨论有限、无向、无环和多重边的简单图。V(G)、E(G)分别表示图G的顶点集和边集。如果S(?)V(G),用G[S]表示子集S在G中的导出子图。若u∈V(G),N(u)表示u点的邻域,即邻接于u点的全体顶点的集合。 相似文献
18.
本文所讨论的图均为无向的简单图。用δ(G)表示图G的最小度。一个图G称为Ore-(k)型图,如果任一对不相邻顶点“和v都有d(u)+d(v)≥|V(G)|+k(k为整数)。 相似文献
19.
一、引言一个图G是指一有序对(V(G),E(G)),其中V(G)是G的点集,E(G)是G的边集。这里我们仅限于讨论有限、无向、不含环及重边的图。C_k表示长为k的圈,d_G(x)表示G中点x的度。 相似文献
20.
确定图的独立数、覆盖数、支配数等不变量的问题,已公认为困难问题,因而研究这些不变量之间的关系是有意义的。定义1 对图G(V,E),设σ(?)V,若V中 相似文献