共查询到19条相似文献,搜索用时 109 毫秒
1.
2.
设I为图G顶点集的子集.如果I中的任意两个点均不相邻,则称I为G的独立集.G的最大独立集的阶数称为独立数,记为α(G).图G的分数匹配是边集上的函数f∈[0,1],使得对每个顶点v都有∑f(e)≤1,这里是对所有与顶点v相关联边的函数值求和.分数匹配数β(G)是所有的分数匹配f中∑(e∈E(G))f(e)的最大值.本文给出了随机图上关于独立数α(G)与分数匹配数β(G)的一些结果. 相似文献
3.
折叠立方体网络的最小反馈点集 总被引:1,自引:0,他引:1
对简单图G=(V,E),顶点子集F V,如果由V\F导出的子图不含圈,则称F是G的反馈点集。点数最小的反馈点集称图的最小反馈点集,最小的点数称为反馈数。一个k维折叠立方体是由一个k维超立方体加上所有的互补边构成的图。本文证明了k维折叠立方体网络的反馈数f(k)=c.2k-1(k 2),其中c∈k-1 相似文献
4.
设 G=(V,E) 为简单图,图 G 的每个至少有两个顶点的极大完全子图称为 G 的一个团. 一个顶点子集 S\subseteq V 称为图 G 的团横贯集, 如果 S 与 G 的所有团都相交,即对于 G 的任意的团 C 有 S\cap{V(C)}\neq\emptyset. 图 G 的团横贯数是图 G 的最小团横贯集所含顶点的数目,记为~${\large\tau}_{C}(G)$. 证明了棱柱图的补图(除5-圈外)、非奇圈的圆弧区间图和 Hex-连接图这三类无爪图的团横贯数不超过其阶数的一半. 相似文献
5.
如果对一个简单图G的每一个与G的顶点数同奇偶的独立集I,都有G-I有完美匹配,则称G是独立集可削去的因子临界图.如果图G不是独立集可削去的因子临界图,而对任意两个小相邻的顶点x与y,G xy足独立集可削去的因子临界图,则称G足极大非独立集可削去的因子临界图,本刻画了极大非独立集可削去的因子临界图。 相似文献
6.
7.
关于哈密尔顿连通图的一个基本结果是Ore给出的:设G是n阶图,若对于任意两个不相邻顶点u和v,有d(u) d(v)≥n 1,则G是哈密尔顿连通的.设G是一个图,对于任意u (?)V(G),令N(U)=∪_(u∈∪)N(u),d(U)=|N(U)|,称d(U)是U的度.本文利用独立集的度和得到如下结果:设s和t是正整数,G是(2s 2t 1)-连通n阶图.若对于任两个强不交独立集S,T,|S|=s,|T|=t,有d(S) d(T)≥n 1.则G是哈密尔顿连通的.同时也得到图的哈密尔顿性的其它相关结果.两个独立集S和T称为强不交的,如果S∪T也是独立集. 相似文献
8.
2-控制数和连通2-控制数相等的图(英文) 总被引:1,自引:0,他引:1
任意一个图G =(V ,E) ,S是V(G)的子集 ,如果对每一个顶点u∈V-S都存在顶点v∈S ,使得d(u ,v) ≤ 2 ,则称S为G的一个 2 控制 .称最小的 2 控制集的顶点个数为G的 2 控制数 ,记为γ2 (G) .如果G的一个 2 控制集S的生成子集〈S〉是一个连通图 ,则称S为G的一个连通 2 控制集 .称最小的连通 2 控制集的顶点个数为G的连通 2 控制数 ,记为γc2 (G) .本文论述了树和单圈图中 2 控制数和连通 2 控制数相等的充分必要条件 . 相似文献
9.
张磊 《数学的实践与认识》2021,(1):302-307
设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限制边连通二部图的充分条件. 相似文献
10.
11.
12.
图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 .Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) ≤Δ2 .本文给出了Kneser图 ,Mycieklski图 ,Descartes图 ,Halin图的λ值的上界 ,并证明了上述猜想对以上几类图成立 相似文献
13.
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}. 相似文献
14.
Journal of Algebraic Combinatorics - A set $$S\subseteq V$$ is independent in a graph $$G=\left( V,E\right) $$ if no two vertices from S are adjacent. The independence number $$\alpha (G)$$ is the... 相似文献
15.
关于图中子图的(n,k)—正交因子分解 总被引:1,自引:0,他引:1
设G是一个具有顶点集V(G)和边集E(G)的图.
设g和f是定义在V(G)上的两个整数值函数,使得g(x)f(x)对所有的点x∈V(G)都成立.如果G是一个(mg+n,mf-n)-图,1n<m2k,且g(x)2k-1对所有的点x∈V(G)都成立,则对任意给定具有|E(H)|=nk边的G的子图H,存在G的一个子图G′使G′有一个(g,f)-因子分解(n,k)-正交H. 相似文献
16.
A set S of vertices of a graph G is dominating if each vertex x not in S is adjacent to some vertex in S, and is independent if no two vertices in S are adjacent. The domination number, γ(G), is the order of the smallest dominating set in G. The independence number, α(G), is the order of the largest independent set in G. In this paper we characterize bipartite graphs and block graphs G for which γ(G) = α(G). 相似文献
17.
可迹图即为一个含有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}$,则该图为可迹图. 相似文献
18.
19.
设G=(X,Y,E(G))是一个二分图,分别用V(G)=XUY和E(G)表示G的顶点集和边集.设f是定义在V(G)上的整数值函数且对(A)x∈V(G)有f(x)≥k.设H_1,H_2,…,H_k是G的k个顶点不相交的子图,且|E(H_i)|=m,1≤i≤k.本文证明了每个二分(0,mf-m+1)-图G有一个(0,f)-因子分解正交于Hi(i=1,2,…,k). 相似文献