图的联结数及其三角形

简单图G的联结数记作bind(G),它是满足下式的最大实数C。这里V(G)是图G的顶点集,N(u)表示图G中与顶点u相邻接所有顶点作成的集合。     

连通、局部连通、无爪图是点泛圈图

本文只讨论有限、无向、无环和多重边的简单图。V(G)、E(G)分别表示图G的顶点集和边集。如果S(?)V(G),用G[S]表示子集S在G中的导出子图。若u∈V(G),N(u)表示u点的邻域,即邻接于u点的全体顶点的集合。     

(a,b,k)-临界图

本文所考虑的图皆指有限无向简单图。设G是一个图,具有顶点集合V(G)和边集合E(G)。文中未加说明的记号和定义参见文献[1]。设S(?)V(G),用G[S]表示G中由S导出的子图。用d_G(x)表示顶点x在G中的次数。设a和b是两个非负整数且a≤b。图G的一个[a,b]-因子是G的一个支撑子图H,使对任意的x∈V(H)有设。如果去掉图G的任意k个顶点所剩的图仍有[a,b]-因子,则称图G是(a,b,c)-临界图,或者说G是(a,b,k)-临界的。如果a=b=n,则简称(a,b,k)-临界图为(n,k)-临界图。如果n=1,则简称(n,k)-临界图为k-临界图。Plummer和Lovasz讨论了2-临界图的特征和性质。于青林给出了k-临界图的特征。刘桂真和于青林研究了(n,k)-临界图的特征。本文考虑a相似文献   

图的联结数及其泛圈性

简单图G的联结数记作bind(G),它是满足下式的最大实数c:■这里V(G)是图G的顶点集,表示图G中与顶点u相邻接的所有点作成的集合。 1973年Woodall提出一个重要的猜想:     

由一类图的着色导出的素数子集的分类

设P表示全体素数的集合,D(?)P。令G(Z,D)表示这样一个图:它的顶点集是全体整数的集合,两个顶点x和y之间有边连结当且仅当|x—y}∈D。Eggleton,Erds和Skilton等在文献中证明了:不论对任何素数子集D(?)P,图G(Z,D)的色数至     

关于两类图的整和数

本文中的图均指无向简单图,以N,Z分别表示全体自然数及全体整数集合.对子集S(?)Z(N),S上的整和(和)图定义为图G=(S,E),满足条件对u,v∈S,uv∈E当且仅当u v∈s.此时,S称为G的一个整和(和)标号.一个图称为整和(和)图,如果它同构于某一子集S(?)Z(N)上的整和(和)图.容易验证,对一个有m条边的n阶图G,G∪mK_1是一个和图,只需标定G的顶点为2~i,1≤i≤n,同时对v_i,v_j∈E(G),标定对应的孤立点2~i 2~j即可.因此,对每一个图G,存在一个最小的非负整数r,使G∪rK_1为和图,记σ(G)=r,并称为G的和数.图的整和数ξ(G)类似定义,只是标号范围放宽到整数集上.容易看到ξ(G)≤σ(G).     

关于完全3-分图同构因子分解

一个图G=(V,E)的同构因子分解是边集合E的一个分划:{E_1,E_2,…,E_t}使得支撑子图(V,E_1),(V,E_2),…(V,E_t)都彼此同构。如果存在把图G分成t个子图的同构因子分解,就说t能整除G,记为t|G。显然t|G的必要条件是t||E(G)|。t||E(G)|被称为关于G和t的可分条件。Harary等人证明了,当t=2,和4时,可分条件对t|K(m,     

关于简单MCD图的一个定理

设S_n是n个顶点的没有两个等长圈的简单图的集合。如果对于S_n中的一个图G,S_n中不存在适合|E(G′)|>|E(G)|的图G′,则称其为简单最大圈分布图,简称简单MCD图(ma-     

m-k_n×k_s残留图

本文将讨论m-k_u×k_s残留图。定义1 图G=(V,E)为简单图,u∈V,集合N~*(u)={v∈V|v与u邻接}U{u}叫做u的闭邻域。定义2 G叫做F残留图,F是指定的图,如果对每一点u∈V(G),G-N~*(u)≌F,(≌表示同构)递归地定义,图G叫做是m-F残留图,如果对     

荫度与独立数、覆盖数的关系

定义1对图G(V,E),由V中互不相邻的点组成的一个集合,称为G的一个独立集;而β(G)=max{|B||B为G的独立集}     

愉快图的Bodendiek猜想之证明

一个简单图称为愉快的,如果存在用集合S={0,1,2,…,ε}(其中ε=ε(G)是G的边数)中不同整数的顶点标号ι,使得如下定义的诱导边标号ι′对每条边uv都有不同的标号:     

临界2棱连通图的最大度及度大于4的点数

设G是临界2棱连通图,D是G中2度顶点集合,D_(≥2k-1)(G)={x:(x∈G)∧(d(x)≥2k-1)},D_(2k-1):2k(G)={x:(x∈G)∧(2k-1≤d(x)≤2k)},其中k是自然数。[a]表示不大于a的最大整数。我们得到如下结果:     

一个边着色定理

Berge曾给出一个边着色定理,下面为使用方便起见,我们不妨称它为B定理。著名的Vizing定理和另外一些边着色的结果都可以作为B定理的推论。我们叙述这个定理如下:B定理 设G是一个无环重图,[a,b]_0是G的一条边,令G′=G—[a,b]_0,若G′是可q-边着色的,且q≥d_G(a),q≥d_G(b);d_(G′)(x) m_(G′)(a,x)≤q,则G也可q-边着色。这里d_G(x)表示顶点x在图G中的次;m_(G′)(x,y)表示在图G′中以x和y为端点的边数;Γ_(G′)(x)表示顶点x在G′中的邻点集合。     

关于Pòlya-de Bruijn计数定理的一个算法及其应用

假设D、R是有限集合,G、H是作用在D、R上的置换群。记函数集合R~D关于G的等价类所构成的分拆为 P(G): R~D=U_1(G)∪U_2(G)∪…∪U_(m)(G),     

关于优美图Bodendiek猜想的证明

一个简单图G称为优美图,如果存在用集合S={0,1,2,…,ε(G)}中不同整数的顶点标号l,使得如下定义的诱导边标号l'对每条边都有不同标号:     

关于有限群的相关正规补子群

本文所论群均为有限群,π为素数之集合,π′为其余集,π(G)表示群G的阶的素因数集合。     

k连通无爪图中最长的圈

本文所涉及的图都是有限无向简单图。设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路     

Ore-2型图中存在两个边不相重的Hamilton圈

本文讨论的图都是无向的简单图。设G是一个图,分别用V(G)和E(G)表示图G的顶点集和边集。又设“、v∈V(G),用d(v)表示v的次数,用vu表示连结u、v的边。     

关于边不交的Hamiltoh圈

本文所讨论的图均为无向的简单图。用δ(G)表示图G的最小度。一个图G称为Ore-(k)型图,如果任一对不相邻顶点“和v都有d(u)+d(v)≥|V(G)|+k(k为整数)。     

边色数的分类问题及其有关性质

设图G为简单连通图,由Vizing定理可知△(G)≤x′(G)≤△(G)+1。其中,△(G)表示图G的最大顶点次,x′(G)是图G的边色数。若x′(x)=△(G),则称G为第一类图,并记为G∈C~1;若 x′(G)=△(G)+1,则称G为第二类图,记为G∈C~2。本文的目的在于讨论边色数的分类问题及其有关性