共查询到19条相似文献,搜索用时 46 毫秒
1.
谈谈与图有关的几种复形的同调群 总被引:2,自引:0,他引:2
我们从组合拓扑方法在图论的应用中,着重介绍与图有关的几种复形的近期研究动态,论述其中一些基础性的问题,并提出一些可供研究的新问题。 相似文献
2.
图与补图全独立数间的关系 总被引:1,自引:0,他引:1
对图G(V,E),V∪E中既不相邻、又不相关联的最大元素个数,称为G的全独立数,并简记为α_T(G)。本文研究了图和补图全独立数之间的关系,得到α_T(G) α_T(G~C)≤「3y 1/2」。其中y=|V(G)|,G~C是G的补图,「x」为不大于x的最大整数,且界可达。 相似文献
3.
一、 引言 本文中未加说明的图论术语来自文献[1]。图G=(V,E)称为弦图,如果G的任何长度大于3的圈都有弦,或者等价地,任何长度大于3的圈都不会是G的点导出子图。本文中,子图总是指点导出子图,点子集S导出的G的子图记为G[S]。团是指完备子图,通常用它的点集来表示。如果图G的每个点v都带有点权w(v),则点子集S的权定义为S中点的权的和。 相似文献
4.
如果对一个简单图G的每一个与G的顶点数同奇偶的独立集I,都有G-I有完美匹配,则称G是独立集可削去的因子临界图.如果图G不是独立集可削去的因子临界图,而对任意两个小相邻的顶点x与y,G xy足独立集可削去的因子临界图,则称G足极大非独立集可削去的因子临界图,本刻画了极大非独立集可削去的因子临界图。 相似文献
5.
设α(G)表示简单图G=(V,E)的独立数.本文给出了α(G)的一个新的下界:α(G)≥∑v∈V(λd(v)+1)/(d(v)+λd(v)+1),其中λd(v)=max{0,βN(v)-d(v)},d(v)=|N(v)|,N(v)={w∈V|(v,w)∈E},βN(v)=minw∈N(v)d(w). 相似文献
7.
本文证明了图与其去点主子图的独立集复形构成的相对同调群族是可重构的;当图满足一定的条件时,图与其去点主子图的邻域复形构成的相对同调群族也是可重构的. 相似文献
8.
9.
徐新萍 《数学的实践与认识》2009,39(10)
设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果. 相似文献
10.
11.
吴举林 《高校应用数学学报(A辑)》1991,6(3):420-426
本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图G的导出森林独立系统是拟阵当且仅当G是块森林.文中同时给出了在强弦图上求最大导出森林的多项式算法. 相似文献
12.
消去图、覆盖图和均匀图的若干结果 总被引:2,自引:0,他引:2
设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献
13.
三正则平面图的对偶图的哈密顿性的注记 总被引:1,自引:0,他引:1
陈婵 《高校应用数学学报(A辑)》2001,16(2):248-250
本文给出了三正则平面图的对偶图为哈密顿图的一个充分条件。 相似文献
15.
16.
《Quaestiones Mathematicae》2013,36(4):383-398
Abstract A set B of vertices of a graph G = (V,E) is a k-maximal independent set (kMIS) if B is independent but for all ?-subsets X of B, where ? ? k—1, and all (? + 1)-subsets Y of V—B, the set (B—X) u Y is dependent. A set S of vertices of C is a k-maximal clique (kMc) of G iff S is a kMIS of [Gbar]. Let βk, (G) (wk(G) respectively) denote the smallest cardinality of a kMIS (kMC) of G—obviously βk(G) = wk([Gbar]). For the sequence m1 ? m2 ?…? mn = r of positive integers, necessary and sufficient conditions are found for a graph G to exist such that wk(G) = mk for k = 1,2,…,n and w(G) = r (equivalently, βk(G) = mk for k = 1,2,…,n and β(G) = r). Define sk(?,m) to be the largest integer such that for every graph G with at most sk(?,m) vertices, βk(G) ? ? or wk(G) ? m. Exact values for sk(?,m) if k ≥ 2 and upper and lower bounds for s1(?,m) are de termined. 相似文献
17.
本文建立了Harper型割宽下界估计式,由此求出了轮形图Wn、完全二部图K(m,n)、圈幂Cnr、格子图:Pm×Pn、Pm×Cn、Cm×Cn以及乘积图:Km×Pn、Km×Cn、Cms×Cnr、Km×Kn和强乘积图Pm Pn的割宽。 相似文献
18.
SOME CLASSES OF UPPER EMBEDDABLE GRAPHS 总被引:7,自引:0,他引:7
1IntroductionSincetheintroductoryinvestigationofmaximumgenusbyNordhaus,Stewart,andWhite[3],theupperembeddabilityofgraphshasreceivedgreatemphasissofar.AlthoughLiu[16]andNebesky[9]haverespectivelyprovideddifferentnecessaryandsufficientconditionsontheupperembeddabilityofgraphs,weknowlessaboutwhatclassesofgraphsareupperembeddable.Jaeger,PayanandXuong[10]provedthateverygraphobtainedbyconnecting(withanynumberofedges)twovertex-disjointupperembeddablegraphswithevenBettinumberisupperembeddable.Skov… 相似文献
19.
王殿军 《高校应用数学学报(A辑)》1993,(4):425-429
本文给出完全图圈分解的一种新方法,设Kn(n≥3)是一个n阶完全图,我们得到下列结果:(1)若n为奇数,G是n阶群,并且{o(x)│∈G,o(x)≥3}={a1,…,at},则Kn=m1Ca1+…+mtCat。(2)若n为偶数,G是n阶群,T={x│x∈G,o(x)=2}={x0,x1,y1,…,xs,ys},o(xiyi)=bi,i=1,…,s及{o(x)│x∈G,o(x)≥}={a1,…,at 相似文献