共查询到20条相似文献,搜索用时 62 毫秒
1.
3.
《数学进展》2015,(1)
设G=(V_1,V_2,E)是一个均衡二部图满足|V_1|=|V_2|=n.令δ_(1,1)(G)=min{d(x)+d(y)|x∈V_1,Y∈V_2}.Amar猜想对任意的s个整数(n_1,n_2,…,n_s),n=n_1+n_2+…+n_s,其中n_i≥2.若δ_(1,1)(G)≥n+s,则G含s个点不交的圈,其长分别为2n_1,2n_2,…,2n_s(见[Discrete Math.,1986,58(1):1-10]).本文证明了若一个点数为4k的均衡二部图G满足δ_(1,1)(G)≥2k+4(k≥3),则G含k-3个4-圈和2个6-圈使得所有这些圈都是点不交的. 相似文献
4.
完全图循环分解成2-正则图 总被引:2,自引:0,他引:2
Alspach提出如下猜想:"设n是奇数并且每个m1,m2,…,mh都是大于等于3而小于等于n的整数.若∑mi=n(n-1)/2,则Kn可以分解成圈Cm1,Cm2,…,Cmh."用记号C(mn11 mn22…mn88)表示由ni个mi长圈,i=1,2,…8组成的2-正则图.设Γ={G((2mi)ni…(2m8)n8)|i ∈[1,8]}.研究了循环(Kv,Γ)-分解的构造方法及其存在性问题,并且证明了Alspach猜想的一些特殊情况. 相似文献
5.
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)相似文献
6.
图的正常k-全染色是用k种颜色给图的顶点和边同时进行染色,使得相邻或者相关联的元素(顶点或边)染不同的染色.使得图G存在正常k-全染色的最小正整数k,称为图G的全色数,用χ″(G)表示.证明了若图G是最大度△≥6且不含5-圈和相邻6-圈的平面图,则χ″(G)=△+1. 相似文献
7.
关于Win猜想的部分结果 总被引:1,自引:0,他引:1
<正> 本文假定G=(V,E)是2n个点的简单图,我们用C[U]表示点集U的导出子图,用d(x)表示G中点x的次,d_H(x)表示G的子图H中点x的次.其余符号见[3]. 给定非负整数k,若图G中每一对不相邻的顶点u和ν,都有d(u)+d(ν)≥2n+k,则称G为Ore k-型图.S.Win给出下述猜想: 若G是Ore k-型图,则G有k+2个1-因子.其中k≤2n-4. 相似文献
8.
郝萃菊 《数学的实践与认识》2014,(4)
设G是m阶连同图,我们用S_n~G(n=km+1)表示把kG的每个分支的d_i度点分别与星图S_k+1的k个1度点重迭后得到的图,Y~(SG)(r_1n,n)表示把r_1S_n~G中每个分支的k度点依次与图的k度点邻接后得到的图,Y~(SG)(r_2λ_1,n)表示把τ_2Y~(SG)(τ_1n,n)中每个分支的r_1+k度点依次与图S_n~G的k度点邻接后得到的图,若k≥3,用Y~(sG)(r_kλ__(k-1),n)表示把τ_kY~(sG)(r_(k-1)λ_(k-2),n)中每个分支的τ_(k-1)+k度顶点依次与图S_n~G的k度点邻接后得到的图,这里λ_k=r_kλ_(k-1)+n.运用图的伴随多项式的性质,证明了一类新的图簇Y~(sG)(r_kλ__(k-1),n)∪β_kS_n~G的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价图. 相似文献
9.
10.
线性森林是指每个连通分支都是路的图.图G的线性荫度la(G)等于将其边分解为k个边不交的线性森林的最小整数k.文中利用权转移方法证明了,若G是一个最大度大于等于7且每个6-圈至多含一条弦的平面图,则la(G)=「(△(G))/2」. 相似文献
11.
12.
A graph is symmetric if its automorphism group acts transitively on the set of arcs of the graph. In this paper, we classify hexavalent symmetric graphs of order for each prime . 相似文献
13.
A graph is called edge-primitive if its automorphism group acts primitively on its edge set. In 1973, Weiss (1973) determined all edge-primitive graphs of valency three, and recently Guo et al. (2013,2015) classified edge-primitive graphs of valencies four and five. In this paper, we determine all edge-primitive Cayley graphs on abelian groups and dihedral groups. 相似文献
14.
Brendan D. McKay 《Journal of Graph Theory》2017,85(1):7-11
A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices. 相似文献
15.
图X称为边正则图,若X的自同构群Aut(X)在X的边集上的作用是正则的.本文考察了三度边正则图与四度Cayley图的关系,给出了一个由四度Cayley图构造三度边正则图的方法,并且构造了边正则图的三个无限族. 相似文献
16.
A regular graph X is called semisymmetric if it is edge-transitive but not vertex-transitive. For G ≤ AutX, we call a G-cover X semisymmetric if X is semisymmetric, and call a G-cover X one-regular if Aut X acts regularly on its arc-set. In this paper, we give the sufficient and necessary conditions for the existence of one-regular or semisymmetric Zn-Covers of K3,3. Also, an infinite family of semisymmetric Zn×Zn-covers of K3,3 are constructed. 相似文献
17.
In this paper we give a classification of a family of symmetric graphs with complete 2-arc-transitive quotients. Of particular interest are two subfamilies of graphs which admit an arc-transitive action of a projective linear group. The graphs in these subfamilies can be defined in terms of the cross ratio of certain 4-tuples of elements of a finite projective line, and thus may be called the second type ‘cross ratio graphs’, which are different from the ‘cross ratio graphs’ studied in [A. Gardiner, C. E. Praeger, S. Zhou, Cross-ratio graphs, J. London Math. Soc. (2) 64 (2001), 257–272]. We also give a combinatorial characterisation of such second type cross ratio graphs. 相似文献
18.
Alfredo García Ferran Hurtado Clemens Huemer Javier Tejel Pavel Valtr 《Computational Geometry》2009,42(9):913-922
Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph. 相似文献
19.
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. 相似文献
20.
A graph is one-regular if its automorphism group acts regularly on the set of its arcs.Let n be a square-free integer.In this paper,we show that a cubic one-regular graph of order 2n exists if and only if n=3~tp1p2…p_s≥13,where t≤1,s≥1 and p_i's are distinct primes such that 3|(P_i—1). For such an integer n,there are 2~(s-1) non-isomorphic cubic one-regular graphs of order 2n,which are all Cayley graphs on the dihedral group of order 2n.As a result,no cubic one-regular graphs of order 4 times an odd square-free integer exist. 相似文献