关于（ξ,k）—临界图

设G为连通图,且ξ（G）=k≥1,若对G中任意边e,均有ξ（G\e）=k-1,则称G为(ξ,k)-临界图。本文刻划了ξ-1-临界图的若干性质,给出了一个图为ξ-1-临界图的一些充分或必要条件,以及一些ξ-1-临界图类。     

Hamiltonian[k,k+1]-因子

本文考虑n/2-临界图中Hamiltonian[k,k+1]-因子的存在性。Hamiltonian[k,k+1]-因子是指包含Hamiltonian圈的[k,k+1]-因子;给定阶数为n的简单图G,若δ(G)≥n/2而δ(G\e)相似文献   

临界h-边-连通图的临界度

图G称为k-临界h-边-连通的,若h=λ(G)且对每个k顶点集{u1,…,uk}有λ(G-{u1,…,ui})≤λ(G-{u1,…,ui-1})-1,I≤k.若G是k-临界h-边-连通但不(k 1)-临界h-边-连通,则记之为(h*,k*)λ.本文证明了:存在(h*,k*)λ图的充要条件是(1)1≤k≤[(h 1)/2],h≡0,1,2(mod 4);1≤k≤[(h-1)/2],h≡3(mod 4);或(2)k=h,G=Kk 1.     

C2(4,k) 中的强支撑可迹图

设2≤h≤3,l0,k≥0是整数,C_h(l,k)是由h-边连通简单图组成的集合,图G∈C_h(l,k)当且仅当对图G的任意一个二边割或三边割X,图G-X的每个分支都至少有︱V(G)-k︱/l个点.设e=u_1v_1和e'=u_2v_2是图G的两条边.若e≠e',G(e,e')是将图G中的边e=u_1v_1和e'=u_2v_2分别用路u_1v_ev_1和u_2v_e'v_2替换得到的图(其中,v_e,v_e'是不在V(G)中的两个新的点).若e=e',G(e,e')是将图G中的边e=u_1v_1用路u_1v_ev_1替换得到的图,也记作G(e).若对任意的e,e'∈E(G),G(e,e')都有支撑(v_e,v_e')迹,则称图G是强支撑可迹的.作者证明了,若图G∈C_2(4,k)且|V(G)|5k,则要么图G是强支撑可迹图,要么存在e,e'∈E(G),使得G(e,e')可以收缩成一个有限图类F中的图.当k=4时,F被完全确定了.     

边覆盖临界图的一些性质

设G是一个简单图,其顶点集为V(G)而边集为E(G),S∈E(G)称为 G的一个覆盖,如果由S导出的子图为G的一个生成子图. G的边覆盖色数χ'c(G)是E(G,)所能划分成的最大边覆盖数.已知δ-1 ≤χ'c(G)≤δ,由此将χ'c(G)=δ的图称为CI类图,否则称为CII类图.若G是连通CII类图,且G不是完全图,对任意的u,u∈V(G),e=uv( )E(G),都有χ'c(G+e)＞χ'c(G)成立,则称G为边覆盖临界的.本文研究了边覆盖临界图的一些性质.即若G为边覆盖临界图,则对任意的u,v∈V(G),若e=uv( )E(G),总存在w∈{u,v},有d(w)≤2δ-2,且w至少与max{d(w)-δ+1,3d(w)-4δ+4}个最小度顶点相邻.     

图的k符号边控制数

设G=(V,E)是一个图,一个函数f:E→{-1,+1},如果对于G中至少k条边e有sum from e'∈N[e]f(e')≥1成立,则称f为图G的一个k符号边控制函数.一个图的k符号边控制数定义为γ_(ks)^/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)^/(G)的若干新下限,并确定了路和圈的k符号边控制数.     

图的符号星k控制数

引入了图的符号星k控制的概念.设G=（V,E）是一个图,一个函数f：E→{-1,＋1},如果∑e∈E[v]f（e）≥1对于至少k个顶点v∈V（G）成立,则称f为图G的一个符号星k控制函数,其中E（v）表示G中与v点相关联的边集.图G的符号星k控制数定义为γkss（G）=min{∑e∈Ef（e）｜f为图G的符号星k控制函数}.在本文中,我们主要给出了一般图的符号星k控制数的若干下界,推广了关于符号星控制的一个结果,并确定路和圈的符号星k控制数.     

一个关于图是分数(k,n)-临界的邻域并条件

设G是一个图,以及k是满足1≤k的整数.一个图G在删除任意n个顶点后的子图均含有分数k-因子,则称G是一个分数(k,n)-临界图.给出了图是一个分数(k,n)-临界图的一个邻域并条件,并且该条件是最佳的.     

几类图的拉普拉斯特征值的前三项和的上界

设G是一个顶点集为V(G),边集为E(G))的简单图.S_k(G)表示图G的拉普拉斯特征值的前k项部分和.Brouwer et al.给出如下猜想:S_k(G)≤e(G)+((k+1)/2),1≤k≤n.证明了当k=3时,对边数不少于n~2/4-n/4的图及有完美匹配或有6-匹配的图,猜想是正确的.     

极大γt-临界图

如果对没有孤立点的图G的任何一个不相邻于一次点的点υ,子图G-υ的全控制数小于图G的全控制数,则称G是全控点临界的.这类图又被称为γt-临界的.进一步地,如此一个图的全控制数为k,则称它为k-γt-临界的.该文主要是给出一个满足n=△(G)(γt(G)-1)+1的图类的结构性的证明.     

与Riemann Zeta函数有关的一些级数和

本文讨论两类与Riemann Zeta函数有关的级数和,给出级数sum from k=1 to ∞ 1/(k~l(k+1)~n)的求和公式,及级数sum from k=2 to ∞ k~mξ(k)、级数sum from k~mξ(2k)、级数sum from k=1 to ∞(2k+1)~mξ(2k+1)(其中m≥-1,ξ(s)=ξ(s)-1)的求和方法,同时求得了有关的一些级数的和值。     

退化图中的子图计数问题研究

令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了Ν(G,K_t)≤(n-k)(k t-1)+(k t).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了Ν(G,K_s,t)≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s.此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数.记v(G),K(G)分别为图G的最大匹配数和最小点覆盖.证明了当v(G)≤k,K(G)=k+r且n≥2k+2r²+r+1时,有e(G)≤(k+r+1 2)+(k-r)(n-k-r-1).     

一类联图的符号边控制数

设G=(V,E)是一个简单图,一个函数f:E→{-1,1},若满足∑_(e′∈N[e])f(e)≥1对E(G)中的每个边e都成立,则称f是图G的一个符号边控制函数,图G的符号边控制数定义为γ′_s(G)=min{∑_(e∈E)f(e)|f是G的符号边控制函数}.给出了联图C_(2k)+C_(2k)的符号边控制数.     

Petersen图的Hamilton性和边色数

对简单图G(V,E),定义图G的关联图I(G)为V(I(G))={(ve)|v∈V(G)且e∈E(G)和v与e关联},E(I(G))={(ue,vf)Iu=v或e=f或uv=e或uv=f}.本文证明了Petersen图可被分解为边不交的Hamilton-圈和一个1-因子的并.     

核的分解与极大广义Bochner-Riesz平均

设l∈N,δ=k/p-k 1/2,以及相似文献   

随机图中[k,k+1]-因子的存在性

设G=G(n,p)是一个随机图,其顶点数为n,任两个顶点之间有边相关联的概率为p=p(n),k是一个正整数满足knp-2(nplogn)~(1/2).图G的—个支撑子图F称作是图G的—个[k,k+1卜因子,如果对任一个x∈V(G),都有k≤dF(x)≤k+1.我们证明任意满足p≥n~(-2/3)的随机图G(n,p)几乎一定包含[k,k+1]-因子.     

关于Sumner-Blitch猜想的一个注记

设G是一个图。G的最小度，连通度，控制数，独立控制数和独立数分别用δ，k，γ，i和α表示，图G是3－γ-临界的，如果γ=3，而且G增加任一条边所得的图的控制数为2.Sumner和Blitch猜想：任意连通的3－γ临界图满足i=3，本文证明了如果G是使α＝k 1≤δ的连通3－γ-临界图，那么Sumner-Blitch猜想成立。     

奇图的匹配可扩性

设G是一个图,n,k和d是三个非负整数,满足n+2k+d≤|V(G)|-2,|V(G)|和n+d有相同的奇偶性.如果删去G中任意n个点后所得的图有k-匹配,并且任一k-匹配都可以扩充为一个亏d-匹配,那么称G是一个(n,k,d)-图.Liu和Yu[1]首先引入了(n,k,d)-图的概念,并且给出了(n,k,d)-图的一个刻划和若干性质. (0,k,1)-图也称为几乎k-可扩图.在本文中,作者改进了(n,k,d)-图的刻划,并给出了几乎k-可扩图和几乎k-可扩二部图的刻划,进而研究了几乎k-可扩图与n-因子临界图之间的关系.     

极大3限制边连通二部图的充分条件

设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点.称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λ_k(G).定义ξ_k(G)=min{[X,■]:|X|=k,G[X]连通,■=V(G)\X}.称图G是极大k限制边连通的,如果λ_k(G)=ξ_k(G).本文给出了围长为g>6的极大3限制边连通二部图的充分条件.     

图的联结数与分数k-消去图

设G是一个图,若对于图G的任一条边e,G-e都存在一个分数k-因子,则称G是一个分数κ-消去图.若k=2,则称分数κ-消去图为分数2-消去图.本文证明了当bind(G)≥2,并且6(G)≥3时,G是分数2-消去图.