共查询到18条相似文献,搜索用时 93 毫秒
1.
陈锡平 《数学物理学报(A辑)》1990,10(1):69-73
设G为图,f是定义在V(G)上的正整数值函数。称图G的支撑子图F为f-因子如果d_(?)(x)-f(x),x∈V(G).称图G是f-因子覆盖的如果G的每条边包含在一个f-因子中.本文给出了一个图是f-因子覆盖的图的充要条件,其结果推广了C.H.C.Little et al.[1]的1-因子覆盖定理。 相似文献
3.
与任意图正交的[0,ki]1^m—因子分解 总被引:1,自引:0,他引:1
设G是一个图,k1,…,km,是正整数,若图G的边能分解成m个边不交的[0,k1]-因子 F1,…,[0,]-l因子Fm,则称F={F1,…,Fm}是G 的一个[0,ki]1^m-因子分解,如果H是G的一个有m条边的了了图且对任意的1≤i≤m有E(H)E(Fi)=1,则称F与H正交,证明了若G是一个[0,k1 ,…, km-m 1]-图,。H是G的一个有m条边的子图,则图G有一个[0,ki]1^m-因子分解与H正交。 相似文献
4.
一个图叫做1-正则的, 如果它的自同构群在它的弧集上作用正则. 设n是一个无平方因子的正整数. 证明了存在2n阶3度1-正则图当且仅当n=3tp1p2… ps≥13, 其中t≤1, s≥1, pi (1≤ i≤s)为互不相同的素数且满足3|(pi-1). 进一步, 对每个满足上述条件的整数n, 共有2s8722;1个互不同构的2n阶3度1-正则图, 并且这些图均为2n阶二面体群上的Cayley图. 由此可知, 不存在4m阶3度1-正则图, 其中m为无平方因子的奇数. 相似文献
5.
6.
(mg+m—1,mf—m+1)—图的(g,f)—因子 总被引:8,自引:0,他引:8
本文证明了(mg+m-1,mf-m+1)-图具有一些特殊的(g,f)-因子,从而推广到了关于(g,f)-覆盖图和(g,f)-消去图的有关结果,有助于进一步研究(mg+m-1,mf-m+1)-图的正交因子分解问题。 相似文献
7.
假设G是一个1-可扩图.G的1-因子覆盖是G的某些1-因子的集合M使得∪M∈M M=F(G).1-因子数目最小的1.因子覆盖称为excessive factorization.一个excessive factorization中的1.因子数目称为图G的excessive index,记为x:(G).本文我们基于G的耳朵分解和E(C)的依赖关系给出了X'e(G)的上界.对任意正整数k≥3,我们构造出一个图G使得A(G)=3而X'e(G)=k.进而,我们考虑了乘积图的excessive index. 相似文献
8.
Hamiltonian[k,k+1]-因子 总被引:4,自引:0,他引:4
本文考虑n/2-临界图中Hamiltonian[k,k+1]-因子的存在性。Hamiltonian[k,k+1]-因子是指包含Hamiltonian圈的[k,k+1]-因子;给定阶数为n的简单图G,若δ(G)≥n/2而δ(G\e)相似文献
9.
一个κ-正则图若满足对任意正整数s,1≤s≤κ,均存在一个s-因子或一个2[s/2]因子,则称其有泛因子或偶泛因子性质.本文证明了每个奇度Cayley图是泛因子的,每个偶度Carley图是偶泛因子的.同时证明了二面体群上的每个Cayley图均是泛因子的. 相似文献
10.
图的1-因子、f-因子和(g,f)-因子 总被引:5,自引:0,他引:5
设G是一个图且有一个1-因子F,g和f是定义在V(G)上的非负整数值函数且对每个X∈V(G)有g(X)<f(X)≤dG(x),且f(v(G))为偶数.(i)若对每个xy∈F有f(x)=f(y)且G-{x,y}有一个(g,f)-因子,则G有一个(g,f)-因子;(ii)若对每个xy∈F有f(X)=f(y)且G-{X,y}有f-因子,则G有f-因子. 相似文献
11.
Recently Alon and Friedland have shown that graphs which are the union of complete regular bipartite graphs have the maximum number of 1-factors over all graphs with the same degree sequence. We identify two families of graphs that have the maximum number of 1-factors over all graphs with the same number of vertices and edges: the almost regular graphs which are unions of complete regular bipartite graphs, and complete graphs with a matching removed. The first family is determined using the Alon and Friedland bound. For the second family, we show that a graph transformation which is known to increase network reliability also increases the number of 1-factors. In fact, more is true: this graph transformation increases the number of k-factors for all k≥1, and “in reverse” also shows that in general, threshold graphs have the fewest k-factors. We are then able to determine precisely which threshold graphs have the fewest 1-factors. We conjecture that the same graphs have the fewest k-factors for all k≥2 as well. 相似文献
12.
We begin the study of sets of near 1-factors of graphs G of odd order whose union contains all the edges of G and determine, for a few classes of graphs, the minimum number of near 1-factors in such sets. 相似文献
13.
Adams Peter Bryant Darryn El-Zanati Saad I. Gavlas Heather 《Graphs and Combinatorics》2003,19(3):289-296
In this paper, we show that K10n can be factored into C5-factors and 1-factors for all non-negative integers and satisfying 2+=10n–1.Research partially supported by an NSF-AWM Mentoring Travel Grant 相似文献
14.
Guantao Chen Ralph J. Faudree Ronald J. Gould Michael S. Jacobson Linda Lesniak 《Graphs and Combinatorics》2000,16(1):67-80
In the study of hamiltonian graphs, many well known results use degree conditions to ensure sufficient edge density for the
existence of a hamiltonian cycle. Recently it was shown that the classic degree conditions of Dirac and Ore actually imply
far more than the existence of a hamiltonian cycle in a graph G, but also the existence of a 2-factor with exactly k cycles, where . In this paper we continue to study the number of cycles in 2-factors. Here we consider the well-known result of Moon and
Moser which implies the existence of a hamiltonian cycle in a balanced bipartite graph of order 2n. We show that a related degree condition also implies the existence of a 2-factor with exactly k cycles in a balanced bipartite graph of order 2n with .
Revised: May 7, 1999 相似文献
15.
We investigate the maximum number of edges in a graph with a prescribed number of 1-factors. We also examine the structure of such extremal graphs. 相似文献
16.
François Bry 《Journal of Combinatorial Theory, Series B》1983,34(1):48-57
Every infinite locally finite graph with exactly one 1-factor is at most 2-connected is shown. More generally a lower bound for the number of 1-factors in locally finite n-connected graphs is given. 相似文献
17.
G. R. T. Hendry 《Journal of Graph Theory》1984,8(3):399-403
Several authors have shown that if G is a connected graph of even order then its square G2 has a 1-factor. We show that the square of any connected graph of order 2n has at least n 1-factors and describe all the extremal graphs. 相似文献
18.
In this paper the properties of some maximum fractional [0, κ]-factors of graphs are presented. And consequently some results on fractional matchings and fractional 1-factors are generalized and a characterization of fractional κ-factors is obtained. 相似文献