首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 125 毫秒
1.
Let G be a connected graph on n vertices with chromatic number k, and let ρ(G)be the distance signless Laplacian spectral radius of G. We show that ρ(G) ≥ 2n + 2「n k」- 4,with equality if and only if G is a regular Tur′an graph.  相似文献   

2.
Mycielski图的循环色数   总被引:1,自引:0,他引:1  
刘红美 《数学杂志》2006,26(3):255-260
通过引入一类点集划分的概念,研究了Mylielski图循环染色的性质,证明了当完全图的点数足够大时,它的Mycielski图的循环色数与其点色数相等.  相似文献   

3.
王金超 《应用数学》1995,8(4):396-399
设G是连通图,γ_C(G)和ir(G)分别表示G的连通控制数和无赘数。孙良于1990年证明了γ_c(G)≤4ir(G)—2,同时提出猜想γ_c(G)≤3ir(G)—2。本文进一步研究γ_c(G)与ir(G)的关系,并证得上述猜想成立。  相似文献   

4.
图 G的 pebbling数 f(G)是最小的整数 n,使得不论 n个 pebble如何放置在 G的顶点上 ,总可以通过一系列的 pebbling移动把一个 pebble移到任意一个顶点上 ,其中的 pebbling移动是从一个顶点上移走两个 pebble而把其中的一个移到与其相邻的一个顶点上 .设 K1,n为 n+1个顶点的星形图 .本文证明了 (n+2 )(m+2 )≥ f K1,n× K1,m)≥ (n+1) (m+1) +7,n>1,m>1.  相似文献   

5.
设G是一个简单图,在图G中任意一个最大匹配的基数叫做G的匹配数,记作v(G),在这篇文章中我们获得了下面的结果,(1)设G是连通的和不完全的,则对于x,y∈v(G)和xyE(G),v(G-{x,y}=v(G)-1的充分必要条件是(a)G[A(G)]是完全的和A(G)的每一个点和C(G)的每一个点相邻,(b)c(D(G))=|A(G)| 1,和(c)y∈D(G-x)对于x,y∈C(G)。(2)设G是连通的和不完全的,则v(G-{x,y})=v(G)-2对于x,y∈V(G)和xyE(G)的充分必要条件是GK_(n,n),其中n≥2。  相似文献   

6.
晏卫根  叶永南 《中国科学A辑》2006,36(9):1014-1022
G是一个简单图,把G的每条边e=(a,b)变换成一个三角形ae*b而得到一个新图,记为R (G), 其中新增加的顶点e*的度为2.本文证明R (G)的匹配数完全由图G的顶点度序列确定.  相似文献   

7.
图的分散数     
LI De-ming 《数学季刊》2005,20(2):121-127
The decay number of a connected graph is defined to be the minimum number of the components of the cotree of the graph. Upper bounds of the decay numbers of graphs are obtained according to their edge connectivities. All the bounds in this paper are tight. Moreover, for each integer k between one and the upper bound, there are infinitely many graphs with the decay number k.  相似文献   

8.
设Hn(n≥5)表示一个图:以1,2,...,n为顶点,两个点i和j是相邻的当且仅当|i-j|≤2,其中加法取模n.这篇文章证明了,Hn的色数等于它的选择数.结果被用于刻画最大度至多2的图的列表全色数.  相似文献   

9.
本文研究了对角Paley数的下界问题.利用一个新发现的Paley图的自同构,给出了计算Paley图团数的一个新方法,获得了2个对角Rasey数的新下界:R(20,20)≥18877,R(21,21)≥25949.  相似文献   

10.
刘红美 《数学杂志》2006,26(6):602-608
通过引进Mycielski图点集的一类特殊划分,利用该划分在Mycielski图循环着色中的特点改进了如下猜想:完全图的Mycielski图的循环色数等于它的点色数.  相似文献   

11.
The acyclic matching number of a graph G is the largest size of an acyclic matching in G, that is, a matching M in G such that the subgraph of G induced by the vertices incident to edges in M is a forest. We show that the acyclic matching number of a connected subcubic graph G with m edges is at least m6 except for two graphs of order 5 and 6.  相似文献   

12.
In 1968, Vizing conjectured that if G is a Δ‐critical graph with n vertices, then α(G)≤n/2, where α(G) is the independence number of G. In this paper, we apply Vizing and Vizing‐like adjacency lemmas to this problem and prove that α(G)<(((5Δ?6)n)/(8Δ?6))<5n/8 if Δ≥6. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 202‐212, 2011  相似文献   

13.
In this paper, we prove that the Kneser graphs defined on a ground set of n elements, where n is even, have their circular chromatic numbers equal to their chromatic numbers. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 257–261, 2005  相似文献   

14.
15.
The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I1,…,In with every Ii being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number.  相似文献   

16.
17.
Given a connected graphG, we say that a setC ?V(G) is convex inG if, for every pair of verticesx, y ∈ C, the vertex set of everyx-y geodesic inG is contained inC. The convexity number ofG is the cardinality of a maximal proper convex set inG. In this paper, we show that every pairk, n of integers with 2 ≤k ≤ n?1 is realizable as the convexity number and order, respectively, of some connected triangle-free graph, and give a lower bound for the convexity number ofk-regular graphs of ordern withn>k+1.  相似文献   

18.
In this note, we prove that the cop number of any n‐vertex graph G, denoted by , is at most . Meyniel conjectured . It appears that the best previously known sublinear upper‐bound is due to Frankl, who proved . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 45–48, 2008  相似文献   

19.
An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. An edge of a k-connected graph is called trivially noncontractible if its two end vertices have a common neighbor of degree k. Ando [K. Ando, Trivially noncontractible edges in a contraction critically 5-connected graph, Discrete Math. 293 (2005) 61-72] proved that a contraction critical 5-connected graph on n vertices has at least n/2 trivially noncontractible edges. Li [Xiangjun Li, Some results about the contractible edge and the domination number of graphs, Guilin, Guangxi Normal University, 2006 (in Chinese)] improved the lower bound to n+1. In this paper, the bound is improved to the statement that any contraction critical 5-connected graph on n vertices has at least trivially noncontractible edges.  相似文献   

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

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