共查询到18条相似文献,搜索用时 55 毫秒
1.
图G中同构于K1,p的子图叫G的p-爪(p3).如果G中任意一个p-爪中1度顶点之间边的数目p-2,则称G为K1,p-受限图,它是无爪图(p=3时)的推广.本文证明了:连通、局部3-连通的K1,4-受限图是路可扩的. 相似文献
2.
K1,p^-约束图的完全圈可扩性 总被引:3,自引:0,他引:3
本文定义了一个新的图类——Ki,p^-约束图,它包含了无爪圈和几乎无爪图,本文证明:顶点数不小于3的连通、局部连通的Ki,p^-约束图是完全圈可扩的,这一结果包含了Hendry和Ryjacek在无爪图和几乎无爪图上的相应结果。 相似文献
4.
5.
徐玉华 《纯粹数学与应用数学》1996,12(2):100-103
设G=(V,E)为一连通图,d〉0整数。G中存在生成对T,使得Δ(T)小于d吗.这一问题已被证明是NP-完全的,故不太可能有多项式解法。本文证明了当G是K1,r-free时,则有O(n^2)的算法求出G生成树T,使Δ(T)≤r,并用一个例子显示了这一结果是最好可能的。 相似文献
6.
图G中同构于K_(1,p)的子图叫G的p-爪(p≥3).如果G中任意一个p-爪中1度顶点之间边(在G中的边)的数目≥p-2,则称G为K(1,p-)-受限图,它是无爪图(p=3)时的推广.本文证明了:连通的K_(1,4-)受限图G,若|G|≥7,则G有Hamilton路或有长至少为2δ+2的路. 相似文献
7.
设G是一个图,n,k和d是三个非负整数,满足n+2k+d≤|V(G)|-2,|V(G)|和n+d有相同的奇偶性.如果删去G中任意n个点后所得的图有k-匹配,并且任一k-匹配都可以扩充为一个亏d-匹配,那么称G是一个(n,k,d)-图.Liu和Yu[1]首先引入了(n,k,d)-图的概念,并且给出了(n,k,d)-图的一个刻划和若干性质. (0,k,1)-图也称为几乎k-可扩图.在本文中,作者改进了(n,k,d)-图的刻划,并给出了几乎k-可扩图和几乎k-可扩二部图的刻划,进而研究了几乎k-可扩图与n-因子临界图之间的关系. 相似文献
8.
设G是一个有限的简单连通图。D(G)表示V(G)的一个子集,它的每一个点至少有一个最大匹配不覆盖它。A(G)表示V(G)-D(G)的一个子集,它的每一个点至少和D(G)的一个点相邻。最后设C(G)=V(G)-A(G)-D(G)。在这篇章中,下面的被获得。⑴设u∈V(G)。若n≥1和G是n-可扩的,则(a)C(G-u)=φ和A(G-u)∪{u}是一个独立集,(b)G的每个完美匹配包含D(G-u)的每个分支的一个几乎守美匹配,并且它匹配A(G-u)∪{u}的所有点与D(G-4)的不同分支的点。⑵若G是2-可扩的,则对于u∈V(G),A(G-u)∪{u}是G的一个最大障碍且G的最大障碍的个数是2或是│V(G)│.⑶设X=Cay(Q,S),则对于u∈Q,(a)A(X-u)=φ=C(G-u)和X-u是一个因子临界图,或(b)C(X-u)=φ和X的两部是A(X-u)∪{u}和D(X-u)且│A(X-u)∪{u}│=│D(X-u)│。⑷设X=Cay(Q,S),则对于u∈Q,A(X-u)∪{u}是X的一个最大障碍且X的最大障碍的个数是2或是│Q│。 相似文献
9.
无爪图的导出匹配可扩性 总被引:6,自引:0,他引:6
若图G的一个匹配M也是G的点导出子图,则称M是图G的一个导出匹配.我们称图G是导出匹配可扩的,若它的任何一个导出匹配可以扩充成一个完美匹配,本文我们讨论无爪图的导出匹配可扩性,得出如下结论,并同时指出这些结果是最好可能的.设图G是有2n个顶点的无爪图,1.若图G是最小度大于或等于2 1,则图G是导出匹配可扩的.2.若图G是局部2连通的,则留G是导出匹配可扩的.3.若图G是k正则的且k≥n,则图G是导出匹配可扩的. 相似文献
10.
令H,G是两个简单图,G是H的一个子图.H的G-分解,记为(λH,G)-GD,是指将图λH的所有边分拆为若干个与G同构的子图(称为G-区组).H的G-分解的大集,记为(λH,G)-LGD,是指图H的所有与G同构的子图的一个分拆Β1,Β2,…,Βm,使得每个Bj(1≤j≤m)为一个(λH,G)-GD (称为小集).本文中,我们对完全二部图的K(p,p)-分解的大集进行了研究,利用Kv的λ重Kκ-因子大集的存在性结果,采用直接构造的方法,得到了大集(λK(m,n),K(p,p))-LGD的存在谱,其中p为任意素数. 相似文献
11.
12.
令G是一个有限图,H是G的一个子图.若V(H)=V(G),则称H为G的生成子图.图G的一个λ重F-因子,记为Sλ(F,G),是G的一个生成子图且可分拆为若干与F同构的子图(称为F-区组)的并,使得V(G)中的每一个顶点恰出现在λ个F-区组中.一个图G的λ重F-因子大集,记为LSλ(F G),是G中所有与F同构的子图的一个分拆{B_i}_i,使得每个B_i均构成一个Sλ(F,G).当λ=1时,λ可省略不写.本文中,我们证明了当v≡4 mod 24时,存在LS(K1,3,Kv,v,v). 相似文献
13.
An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is called contraction critically k-connected. For k≥4, we prove that if both G and its complement Gˉ are contraction critically k-connected, then |V(G)|<k
5/3+4k
3/2.
Received: October, 2001 Final version received: September 18, 2002
AMS Classification: 05C40 相似文献
14.
Let Г be a G-symmetric graph admitting a nontrivial G-invariant partition
. Let Г
be the quotient graph of Г with respect to
. For each block B ∊
, the setwise stabiliser GB of B in G induces natural actions on B and on the neighbourhood Г
(B) of B in Г
. Let G(B) and G[B] be respectively the kernels of these actions. In this paper we study certain “local actions" induced by G(B) and G[B], such as the action of G[B] on B and the action of G(B) on Г
(B), and their influence on the structure of Г.
Supported by a Discovery Project Grant (DP0558677) from the Australian Research Council and a Melbourne Early Career Researcher
Grant from The University of Melbourne. 相似文献
15.
Aleksandar Jurišić Jack Koolen Paul Terwilliger 《Journal of Algebraic Combinatorics》2000,12(2):163-197
We consider a distance-regular graph with diameter d 3 and eigenvalues k = 0 > 1 > ... >
d
. We show the intersection numbers a
1, b
1 satisfy
We say is tight whenever is not bipartite, and equality holds above. We characterize the tight property in a number of ways. For example, we show is tight if and only if the intersection numbers are given by certain rational expressions involving d independent parameters. We show is tight if and only if a
1 0, a
d = 0, and is 1-homogeneous in the sense of Nomura. We show is tight if and only if each local graph is connected strongly-regular, with nontrivial eigenvalues –1 – b
1(1 + 1)–1 and –1 – b
1(1 +
d
)–1. Three infinite families and nine sporadic examples of tight distance-regular graphs are given. 相似文献
16.
Let be a graph and G be a 2-arc transitive automorphism group of . For a vertex x let G(x)(x) denote the permutation group induced by the stabilizer G(x) of x in G on the set (x) of vertices adjacent to x in . Then is said to be a locally projective graph of type (n,q) if G(x)(x) contains PSLn(q) as a normal subgroup in its natural doubly transitive action. Suppose that is a locally projective graph of type (n,q), for some n 3, whose girth (that is, the length of a shortest cycle) is 5 and suppose that G(x) acts faithfully on (x). (The case of unfaithful action was completely settled earlier.) We show that under these conditions either n=4, q=2, has 506 vertices and
, and contains the Wells graph on 32 vertices as a subgraph. In the latter case if, for a given n, at least one graph satisfying the conditions exists then there is a universal graph W(n) of which all other graphs for this n are quotients. The graph W(3) satisfies the conditions and has 220 vertices. 相似文献
17.