首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 46 毫秒
1.
本文首先给出了(g,f)-3-覆盖图的定义,即一个图G称为(g,f)-3-覆盖图,如果G的任何三条边都属于它的一个(g,f)-因子;其次,黄光鑫曾先后给出了当g<f时一个二部图分别是(g,f)-2-覆盖图和(g,f)-3-覆盖图的充分必要条件,在此基础上,本文进一步得到了,当g≤f时一个二部图G=(X,Y)是(g,f)-3-覆盖图的一个充分必要条件;最后,研究了f(X)=f(Y)的情形,得到了当f(X)=f(Y)时一个二部图G=(X,Y)是f-3-覆盖图的一个充分必要条件.  相似文献   

2.
设D是一个有向图,S是V(D)的子集.在D中推S,是指颠倒D中所有的只有一个端点在S中的弧的方向. Klostermeyer提出了对于任给的一个有向图D,能否通过推点使之成为强连通的有向图的问题.他证明了上述判定问题是NP-完备的.而我们论证了对于任意的二部竞赛图D,如果V(D)的二划分是(X,Y),并满足3≤|X|≤|Y|≤2|X|-1-1, 则可以通过推点使D成为强连通的有向图,而且,|Y|的上界2|X|-1-1是最好可能的.  相似文献   

3.
图G=(V,E)的Tutte集定义为X■V(G)满足ω_o(G-X)一|X|=def(G).若不存在Tutte集Y■X,则称X为图G的极大Tutte集.通过找极大extreme集和D-图的极大独立集给出一般图G的找极大Tutte集的两个有效算法,并给出结论:X■V(G)是二部图G的极大Tutte集当且仅当X为二部图G的最小覆盖,从而得到找二部图G的极大Tutte集的一个有效算法.  相似文献   

4.
图 G的一个 k-正则支撑子图称为 G的 k-因子 ,若对 G的任一边 e,图 G- e总存在一个 k-因子 ,则称 G是 k-消去图 .证明了二分图 G=( X,Y) ,且 | X | =| Y|是 k-消去图的充分必要条件是 k| S|≤ r1 + 2 r2 +…+ k( rk+… + rΔ) - ε( S)对所有 S X成立 .并由此给出二分图是 k-消去图的充分度条件 .  相似文献   

5.
一个图G称为(X,Y)-free图,如果G不含同构于子图X和Y的导出子图.本文证明了X=K_(1,3)、Y∈{D,W,B}的3-连通(X,Y)-free图是Hamiltonian-连通的.  相似文献   

6.
设G=(X,Y;E)是一个偶图。如果|X|≥2|Y|-3且d(v)=3对任意v∈X,那么G含有K3.3的剖分。有例子表明|X|的下界在一定程度上是不可改进的。  相似文献   

7.
设G=(X,Y,E(G))是一个二分图,分别用V(G)=X∪Y和E(G)表示G的顶点集和边集.设f是定义在V(G)上的整数值函数且对任意x∈V(G)有f(x)≥k.设H1,H2,…,Hk是G的k个顶点不相交的子图,且|E(Hi)|=m,1≤i≤k.本文证明了每个二分(0,mf—m+1).图G有一个(0,f)-因子分解正交于Hi(i=1,2,…,k)  相似文献   

8.
广义联图的正则性   总被引:2,自引:0,他引:2  
程辉  陈祥恩 《数学研究》2001,34(3):302-305
讨论了两个图的广义联图的End-正则性,给出了当图X、Y的广义联图G(y1,…ym)End-正则时,图X也End-正则应满足的条件。  相似文献   

9.
二面体群D_(2n)的4度正规Cayley图   总被引:4,自引:0,他引:4  
王长群  周志勇 《数学学报》2006,49(3):669-678
设G是有限群,S是G的不包含单位元1的非空子集.定义群G关于S的 Cayley(有向)图X=Cay(G,S)如下:V(x)=G,E(X)={(g,sg)|g∈G,s∈S}. Cayley图X=Cay(G,S)称为正规的如果R(G)在它的全自同构群中正规.图X称为1-正则的如果它的全自同构群在它的弧集上正则作用.本文对二面体群D2n以Z22 为点稳定子的4度正规Cayley图进行了分类.  相似文献   

10.
图G称为弱泛圈图是指G包含了每个长为t(g(V)≤l≤c(G))的圈,其中g(G),c(v)分别是G的围长与周长.1997年Brandt提出以下猜想:边数大于[n2/4]-n 5的n阶非二部图为弱泛圈图.1999年Bollobas和Thomason证明了边数不小于[n2/4]-n 59的n阶非二部图为弱泛圈图.作者证明了如下结论:设G是n阶Hamilton非二部图,若G的边数不小于[n2/4]-n 12,则G为弱泛圈图.  相似文献   

11.
消去图、覆盖图和均匀图的若干结果   总被引: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相似文献   

12.
13.
本文证明了双线性型图与交错型图都不是完美图,从而解决了双线性型图与交错型图的完美图判别问题.  相似文献   

14.
15.
Graph minors play an important role in graph theory. The focus of this paper is on immersion minors and their relationship to planarity. In general, planar graphs can have non-planar immersion minors. This paper shows that by placing a simple restriction on the immersion-minor operations, all immersion minors of a planar graph are planar. This then allows one to easily obtain a characterization of planar graphs using immersion minors. A dual form of this characterization, as well as an extension to binary matroids, are also considered.  相似文献   

16.
Let G=(V,E) be an undirected graph with a node set V and an arc set E. G has k pairwise disjoint subsets T1,T2,…,Tk of nodes, called resource sets, where |Ti| is even for each i. The partition problem with k resource sets asks to find a partition V1 and V2 of the node set V such that the graphs induced by V1 and V2 are both connected and |V1Ti|=|V2Ti|=|Ti|/2 holds for each i=1,2,…,k. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of k=1. On the other hand, it is known that if G is (k+1)-connected for k=1,2, then a bisection exists for any given resource sets, and it has been conjectured that for k?3, a (k+1)-connected graph admits a bisection. In this paper, we show that for k=3, the conjecture does not hold, while if G is 4-connected and has K4 as its subgraph, then a bisection exists and it can be found in O(|V|3log|V|) time. Moreover, we show that for an arc-version of the problem, the (k+1)-edge-connectivity suffices for k=1,2,3.  相似文献   

17.
A decomposition of a multigraph G is a partition of its edges into subgraphs G(1),,G(k). It is called an r-factorization if every G(i) is r-regular and spanning. If G is a subgraph of H, a decomposition of G is said to be enclosed in a decomposition of H if, for every 1ik, G(i) is a subgraph of H(i).Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of λKn to be enclosed in some 2-edge-connected r-factorization of μKm for some range of values for the parameters n, m, λ, μ, r: r=2, μ>λ and either m2n?1, or m=2n?2 and μ=2 and λ=1, or n=3 and m=4. We generalize their result to every r2 and m2n?2. We also give some sufficient conditions for enclosing a given decomposition of λKn in some 2-edge-connected r-factorization of μKm for every r3 and m>(2?C)n, where C is a constant that depends only on r, λ and μ.  相似文献   

18.
In this article, we introduce the algebra of block-symmetric cylinders and we show that symmetric cylindrical constructions on base-graphs admitting commutative decompositions behave as generalized tensor products. We compute the characteristic polynomial of such symmetric cylindrical constructions in terms of the spectra of the base-graph and the cylinders in a general setting. This gives rise to a simultaneous generalization of some well-known results on the spectra of a variety of graph amalgams, as various graph products, graph subdivisions and generalized Petersen graph constructions. While our main result introduces a connection between spectral graph theory and commutative decompositions of graphs, we focus on commutative cyclic decompositions of complete graphs and tree-cylinders along with a subtle group labeling of trees to introduce a class of highly symmetric graphs containing the Petersen and the Coxeter graphs. Also, using techniques based on recursive polynomials we compute the characteristic polynomials of these highly symmetric graphs as an application of our main result.  相似文献   

19.
20.
It is well known that every Eulerian orientation of an Eulerian 2k-edge connected (undirected) graph is strongly k-edge connected. A long-standing goal in the area is to obtain analogous results for other types of connectivity, such as node connectivity. We show that every Eulerian orientation of the hypercube of degree 2k is strongly k-node connected.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号