均衡二部图中点不交的4-圈和6-圈（英文）

设G=(V_1,V_2,E)是一个均衡二部图满足|V_1|=|V_2|=n.令δ_(1,1)(G)=min{d(x)+d(y)|x∈V_1,Y∈V_2}.Amar猜想对任意的s个整数(n_1,n_2,…,n_s),n=n_1+n_2+…+n_s,其中n_i≥2.若δ_(1,1)(G)≥n+s,则G含s个点不交的圈,其长分别为2n_1,2n_2,…,2n_s(见[Discrete Math.,1986,58(1):1-10]).本文证明了若一个点数为4k的均衡二部图G满足δ_(1,1)(G)≥2k+4(k≥3),则G含k-3个4-圈和2个6-圈使得所有这些圈都是点不交的.     

均衡二部图中含2k条指定边的k个独立圈及2-因子

得到了对于二部图G=(V_1,V_2;E),当|V_1|=|V_2|=n≥2k+1时的结果:对G中任意2k条独立边e_1,e_1~*,…,e_k,e_k~*,G中一定存在k个独立的4-圈C_1,C_2,…,C_k,使得对任意i∈{1,2,…,k}有{e_i,e_i~*}E(C_i).并在此基础上进一步证明了当|V_1|=|V_2|=n≥3k时若对任意两顶点x∈V_1,y∈V_2,都有d(x)+d(y)≥2n-k+1成立,则G有一个2-因子含有k+1个独立圈C_1,C_2,…,C_(k+1)使得对任意i∈{1,2,…,k}有{e_i,e_i~*}E(C_i)且|C_i|=4.     

二分图中关于Enomoto问题的结果

设k,n1和n2是3个正整数,G=（V1,V2;E）是一个二分图,使得｜V1｜=n1,｜V2｜=n2,其中n1≥2k＋1,n2≥2k＋1并且n1-n2≤1．如果对任意不相邻的x∈V1和y∈V2,都有d（x）＋d（y）≥2k＋2,则G包含k个相互独立的圈．以上结果部分地回答了Enomoto提出的关于二分图有独立圈的问题．     

图的上可嵌入性与圈中顶点度

本文利用非上可嵌入图的充要条件,结合圈中顶点最大度与图的上可嵌入性之间的关系,得到了下两个结果:(1)设G是2-边连通简单图,若对G中任意圈G,存在点x∈C满足,d(x)>|V(G)|/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.(2)设G={x,y;E}为简单二都图,且是2-边连通的. |x|=m,|Y|=n(m,n≥3),若对G中任意圈C,存在点x∈C且x∈X满足d(x)>n/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.     

第一类图的一个充分条件

图G的一个k-边染色是一个映射ψ:E(G)→{1,2…k},使得每一对相邻边x和y,有ψ(x)≠ψ(y,).G的边色数χ'(G)是使得G有一个k-边染色的最小的整数k.本文证明了:如果G是一个最大度为6能嵌入到欧拉示性数非负的曲面的图,且满足下列条件之一,那么χ'(G)=6:(1)不含带弦4-圈;(2)同时不含带弦5-圈和带弦6-圈.     

最大亏格、点度和围长

用g(G)和δ(G)分别表示一个图G的围长和顶点最小度. ζ(G)为图G的Betii亏数,主要证明了以下2个结果1)设G为k-边连通简单图,若对G中任意圈C,存在点x∈C满足dG(x)＞|V(G)|/(k-1)2+2)+k-g(G)+2,k=1,2,3,则G是上可嵌入的.且不等式的下界是最好的;2)设G为k-边连通简单图,则ζ(G)≤{max{1,m},k=1,max{1,1/(k-1)m -1}K=2,3 其中m= |V(G)|g(G)-6/g(G)2+(δ(G)-2)g(G)-4'且不等式的上界是可达的.进而得到了最大亏格一个比较好的下界.     

关于P（n1,n2,...nm）和Dm,4的优美性

一个简单图G=(V,E)是k-优美的(k≥1的整数),如果存在一个1-1映射 f:V(G)→(0,1,…,|E| k-1)使得对所有的边e=wv∈E(G),由f~*(u,v)=|f(u)-f(v)|导出的映射 E(G)→{k,k 1,…,|E| k-1}是一个1-1对应。这个关于k-优美的概念是由Slater和Thuillier相互独立地提出来的。当k=1,就是我们通常研究的优美图。显然,k-优美图一定是1-优美图。反之不真。例如,三回路c_3是1-优美图,但对k>1,非k-优美。     

关于图中子图的（n,k）—正交因子分解

设G是一个具有顶点集V(G)和边集E(G)的图. 设g和f是定义在V(G)上的两个整数值函数,使得g(x)f(x)对所有的点x∈V(G)都成立.如果G是一个(mg+n,mf-n)-图,1n<m2k,且g(x)2k-1对所有的点x∈V(G)都成立,则对任意给定具有|E(H)|=nk边的G的子图H,存在G的一个子图G′使G′有一个(g,f)-因子分解(n,k)-正交H.     

折叠立方体网络的最小反馈点集

对简单图G=(V,E),顶点子集F V,如果由V\F导出的子图不含圈,则称F是G的反馈点集。点数最小的反馈点集称图的最小反馈点集,最小的点数称为反馈数。一个k维折叠立方体是由一个k维超立方体加上所有的互补边构成的图。本文证明了k维折叠立方体网络的反馈数f(k)=c.2k-1(k 2),其中c∈k-1     

关于图的L(3,2,1)-标号问题

图 G的 L (2 ,1) -标号是一个从顶点集 V(G)到非负整数集的函数 f (x) ,使得若 d(x,y) =1,则 | f (x)- f (y) |≥ 2 :若 d(x ,y) =2 ,则 | f (x) - f (y) |≥ 1.图 G的 L (2 ,1) -标号数λ(G)是使得 G有 max{ f (v) :v∈ V(G) } =k的 L(2 ,1) -标号中的最小数 k.本文将 L(2 ,1) -标号问题推广到更一般的情形即 L(3,2 ,1) -标号问题 ,并得出了细分图、Descartes图的 λ3 (G)的上界 .     

半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$.若图中任意距离为2的两点$u,v$满足$J(u,v)\neq \emptyset$,则称该图为半无爪图.令$\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$为$G$中含有$k$个点的独立集\},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{3}(G)\geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{2}(G)\geq \frac{2({n-2})}{3}$,则该图为可迹图.     

二部图中的独立6-圈

本文主要证明了对二部图G=(V_1,V_2,E),|V_1|=|V_2|=3k,其中k为正整数.若G的最小度至少为2k-1,则G至少包含k-1个独立6-圈.     

图的度和与扩路

本文讨论了两顶点的度和与路可扩之间的关系,得到了如下结果:设G是n阶图,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥n+n/k(2≤k≤n-2),则G中任意一个满足k+1≤|P|相似文献   

无$K_{1,4}$子图的图的路覆盖

For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.     

任意长圈覆盖指定的独立的点

An invariant σ2（G） of a graph is defined as follows： σ2（G） ：= min{d（u） ＋ d（v）｜u, v ∈V（G）,uv ∈ E（G）,u ≠ v} is the minimum degree sum of nonadjacent vertices （when G is a complete graph, we define σ2（G） = ∞）. Let k, s be integers with k ≥ 2 and s ≥ 4, G be a graph of order n sufficiently large compared with s and k. We show that if σ2（G） ≥ n ＋ k- 1, then for any set of k independent vertices v1,..., vk, G has k vertex-disjoint cycles C1,..., Ck such that ｜Ci｜ ≤ s and vi ∈ V（Ci） for all 1 ≤ i ≤ k.
The condition of degree sum σs（G） ≥ n ＋ k - 1 is sharp.     

图G_n的优美表示

将给出三个结果:(i)如果图G是SZ(|S|=n≥2)上的整数和图,那么0∈S当且仅当图G至少有一个(n-1)度顶点;(ii)图G(G≠K2)是至少有两个零点的整数和图当且仅当G■K2·Gn;(iii)设图G(G≠K2)是SZ上的整数和图,|S|=n+2,n∈N+.若图G至少有两个零点,则S={mx|m=-1,0,1,2,…,n;x∈Z且x≠0}.     

Some Existence Theorems on Path Factors with Given Properties in Graphs

A path factor of G is a spanning subgraph of G such that its each component is a path.A path factor is called a P≥_n-factor if its each component admits at least n vertices. A graph G is called P≥_n-factor covered if G admits a P≥_n-factor containing e for any e ∈ E(G), which is defined by[Discrete Mathematics, 309, 2067–2076(2009)]. We first define the concept of a(P≥_n, k)-factor-critical covered graph, namely, a graph G is called(P≥_n, k)-factor-critical covered if G-D is P≥_n-factor covered for any D ? V(G) with |D| = k. In this paper, we verify that(i) a graph G with κ(G) ≥ k + 1 is(P≥2, k)-factor-critical covered if bind(G) 2+k/3;(ii) a graph G with |V(G)| ≥ k + 3 and κ(G) ≥ k + 1 is(P≥3, k)-factor-critical covered if bind(G) ≥4+k/3.     

关于拟k-连通图的一个注释

G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G₁,G₂,且|G₁|≥2,|G₂|≥2,则称T是G的一个非平凡点割。假定G是一个不含非平凡（k-1）点割的（k-1）-连通图,则称G是一个拟k-连通图。证明了对任意一个k≥5且t> $ \frac{k}{2}$的整数,若G是一个不含（K₂+tK₁）的k-连通图,且G中任意两个不同点对v,w,有d（v）+d（w）≥ $\frac{{3k}}{2} $+t,则对G中的任意一个点,存在一条与之关联的边收缩后可以得到一个拟k-连通图,且G中至少有$\frac{{\left| {V\left( G \right)} \right|}}{2} $条边使得收缩其中任意一条边后仍是拟k-连通的。