共查询到20条相似文献,搜索用时 129 毫秒
1.
2.
圈和Dn图的补图的色唯一性 总被引:37,自引:0,他引:37
圈和Dn图的补图的色唯一性王守中刘儒英(青海师范大学数学系,西宁810008)关键词图,色多项式,色唯一性.分类号AMS(1991)05C/CCLO157.5用Pn和Cn表示有n个顶点的路和圈.用Dn表示把K3的一个顶点与Pn-2的一个一度顶点重迭后... 相似文献
3.
关于图B(m,n,p)的优美性 总被引:2,自引:1,他引:2
在[1][2]中已证明“除去三种特殊情形,连结两个顶点的三条独立路所成简单图B(m,n,p)是优美图”,并猜想:对除去的三种情形,B(m,n,p)也是优美的。本文证实了上术猜想。这样一来,也就证明了[3]中的猜想:有-h-链弦的圈是优美的(h≥2)。 相似文献
4.
本文给出了一个关于长圈和长路的新的充分条件.主要结果是:设在3-连通图G中,任一对距离为2的顶点u,v,都满足max{d(u),d(v)}≥m/2,那么d*(G)≥min{n-1,m-2}. 相似文献
5.
6.
一个图G是泛圈的,如果它含有长为3,4,…,n(=|V(G)|)的圈.本文探讨了一类无爪Hamilton图的圈结构,主要结果为:设G=(V,E)是n阶无爪Hamilton图.如果G中有节点x使d(x)≧n/2且N(x)连通,则除少数几个例外,G是泛圈的. 相似文献
7.
给一个图G,定义σ3(G)=min{Σ^3i=1d(vi)│{v1,v2,v3}}是G的无关集},p3(G)=min{│U^3i=1N(vi)‖{v1,v2,v3}是G中使│n^3i=1N(vi)│≠0}的无关集}。本文证明了:设G是n阶1-坚韧图,如果σ3(G)≥n,则G包含长度至少为min{n,2p3(G)+4}的圈,为个结果推广了若干已知结果,也解决了Broersma-Heuvel-Veld 相似文献
8.
关于Abel群上Cayley图的Hamilton圈分解 总被引:3,自引:0,他引:3
设G(F,T∩T^-1)是有限Abel群F上的Cayley图,T∩T^-1只含2阶元,此文证明了当T是F的极小生成元集时,若d(G)=2k,则G是k个边不相交的Hamilton圈的并,若d(G)=2k+1,则G是k个边不相交的Hamilton圈与一个1-因子的并。 相似文献
9.
本文给出了2-连通图有Hamilton圈的又一个充分条件.定理设G为有n(n>3)个顶点的2-连通图,如果对G中任意两个顶点u、v,当d(u,v)=2时,都有max(d(u),d(v))≥n/2,则G有Hamilton圈.证用反证法.假设G没有Ham... 相似文献
10.
11.
12.
设G(V,E)是简单连通图,T(G)为图G的所有顶点和边构成的集合,并设C是k-色集(k是正整数),若T(G)到C的映射f满足:对任意uv∈E(G),有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),并且C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.那么称f为图G的邻点可区别E-全染色(简记为k-AVDETC),并称χ_(at)~e(G)=min{k|图G有k-邻点可区别E-全染色}为G的邻点可区别E-全色数.图G的中间图M(G)就是在G的每一个边上插入一个新的顶点,再把G上相邻边上的新的顶点相联得到的.探讨了路、圈、扇、星及轮的中间图的邻点可区别E-全染色,并给出了这些中间图的邻点可区别E-全色数. 相似文献
13.
Let G be a (molecular) graph. The Hosoya index Z(G) of G is defined as the number of subsets of the edge set E(G) in which no two edges are adjacent in G, i.e., Z(G) is the total number of matchings of G. In this paper, we determine all the connected graphs G with n + 1 ≤ Z(G) ≤ 5n ? 17 for n ≥ 19. As a byproduct, the graphs of n vertices with Hosoya index from the second smallest value to the twenty first smallest value are obtained for n ≥ 19. 相似文献
14.
Megan Cream Ralph J. Faudree Ronald J. Gould Kazuhide Hirohata 《Graphs and Combinatorics》2016,32(6):2295-2313
A chord is an edge between two vertices of a cycle that is not an edge on the cycle. If a cycle has at least one chord, then the cycle is called a chorded cycle, and if a cycle has at least two chords, then the cycle is called a doubly chorded cycle. The minimum degree and the minimum degree-sum conditions are given for a graph to contain vertex-disjoint chorded (doubly chorded) cycles containing specified elements of the graph, i.e., specified vertices, specified edges as cycle-edges, specified paths, or specified edges as chords. Furthermore, the minimum degree condition is given for a graph to be partitioned into chorded cycles containing specified edges as cycle-edges. 相似文献
15.
The pure-dimer problem was solved in exact closed form for many lattice graphs. Although some numerical solutions of the monomer–dimer problem were obtained, no exact solutions of the monomer–dimer problem were available (except in one dimension). Let G be an arbitrary graph with N vertices. Construct a new graph R ( G ) from G by adding a new verex e * corresponding to each edge e = ( a , b ) of G and by joining each new vertex e * to the vertices a and b . If the suitable activities of vertices and edges in R ( G ) are selected, then the monomer–dimer problem can be solved exactly for the graph R ( G ), which generalizes the result obtained by Yan and Yeh. As applications, if we select suitable activities for the vertices and edges of , we obtain the exact formulae for the MD partition function, MD free energy, and MD entropy of for the d -dimensional lattice with periodic boundaries. 相似文献
16.
设U*为一个未定向的n个顶点上的单圈混合图,它是由一个三角形在其某个顶点上附加n-3个悬挂边而获得.在文[Largest eigenvalue of a unicyclic mixed graph,Applied Mathematics A Journal of Chinese Universities(Ser.B),2004,19(2):140-148]中,作者证明了:在相差符号同构意下,在所有n个顶点上的单圈混合图中,U*是唯一的达到最大Laplace谱半径的混合图.本文应用非负矩阵的Perron向量,给出上述结论的一个简单的证明. 相似文献
17.
扈生彪 《数学的实践与认识》2011,41(15)
设A(G)是简单图G的邻接矩阵,H是由G的独立边和不交圈组成的生成子图的集合,e是H中某个图的独立边,C是H中图的圈,且e∈E(C).记G-e是G的删边子图,G\W是从G中删去导出子图W中的顶点及其关联边后得到的图.那么A(G)的行列式为detA(G)=detA(G-e)-detA(G\e)-2(-1)~(|V(C)|)detA(G\C)A(G)的积和式为perA(G)=perA(G-e)+perA(G\e)+2perA(G\C)这里,C取遍H中图的经过边e的圈. 相似文献
18.
用P_n表示n个点的路,C_n表示长为n的圈,C_6+3K_2表示圈C_6添加三条相邻的边3K_2=C_3得到的图.在Kleitman给出的完全二部图的交叉数cr(K_(6,n))=Z(6,n)的基础上,得到了特殊六阶图C_6+3K_2与路P_n,圈C_n的联图交叉数分别为Z(6,n)+3[n/2]+2与Z(6,n)+3[n/2]+4. 相似文献
19.
令简单图G=(V,E)是有p个顶点q条边的图.假设G的顶点和边由1,2,…,p+q所标号,且f:V∪E→{1,2,…,p+q}是一个双射,如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic).本文证明了三路树P(m,n,t)当n为偶数,t=n+2时也是边幻图. 相似文献
20.
具有最小度距离的双圈图 总被引:2,自引:0,他引:2
记G(n)为所有n阶连通简单双圈图所构成的集合.本文主要讨论G(n)按其度距离从小到大进行排序的问题,并确定了该序的前两个图及其相应的度距离,其中具有最小度距离的图是由星图K1,n-1的一个悬挂点与另外两个悬挂点之间各连上一条边所得的图Sn. 相似文献