共查询到20条相似文献,搜索用时 62 毫秒
1.
图G(V,E)的一个正常k-全染色σ称为G(V,E)的一个k-点强全染色,当且仅当v∈V(G),N[v]中的元素着不同颜色,其中N[v]={u vu∈V(G)}∪{v};并且χvTs(G)=m in{k存在G的一个k-点强全染色}称为G的点强全色数.本文确定了完全图Kn的广义图K(n,m)和乘积图Lm×Kn的点强全色数. 相似文献
2.
最大度不大于5的Halin-图的点强全染色 总被引:5,自引:0,他引:5
图G(V,E)的一正常k-全染色f称为G(V,E)的一k-点强全染色当且仅当任意(
A)v∈V(G),N[v]中的元素染不同色,其中N[v]={u|uv∈V(G)}U{v},并且XusT(G)=min{k|存在G的k-点强全染色}称为G(V,E)的点强全色数.本文得到了△(G)≤5的Halin-图G(V.E)的XusT(G),并提出如下猜想设G(V,E)为每一连通分支的阶数不小于6的图,则XusT(G)≤△(G)+2,其中△(G)表示图G的最大度. 相似文献
3.
4.
图G(V,E)的一个k-正常全染色f叫做一个k-点强全染色当且仅当对任意v∈V(G), N[v]中的元素被染不同色,其中N[v]={u|uv∈V(G)}∪{v}.χTvs(G)=min{k|存在图G的k- 点强全染色}叫做图G的点强全色数.对3-连通平面图G(V,E),如果删去面fo边界上的所有点后的图为一个树图,则G(V,E)叫做一个Halin-图.本文确定了最大度不小于6的Halin- 图和一些特殊图的的点强全色数XTvs(G),并提出了如下猜想:设G(V,E)为每一连通分支的阶不小于6的图,则χTvs(G)≤△(G) 2,其中△(G)为图G(V,E)的最大度. 相似文献
5.
6.
设G为简单图.G的全k-染色是指k种颜色1,2,…,k对图G的全体顶点及边的一个分配.设c是图G的一个全k-染色,任意的x∈V(G),称■为点x的扩展和,其中N(x)={y∈V(G)|xy∈E(G)}.称图G的全k-染色c为邻点被扩展和可区别(简记为NESD),如果w(x)≠w(y),其中xy∈E(G).使得图G存在NESD全k-染色的最小值k被称为图G的邻点被扩展和可区别全色数,简记为egndi_∑(G).本文利用数学归纳法探讨了仙人掌图的邻点被扩展和可区别全染色,并证明了这类图的邻点被扩展和可区别全色数不超过2.该结论说明Flandrin等人提出的NESDTC猜想对于仙人掌图是成立的. 相似文献
7.
Pm×Kn的邻点可区别全色数 总被引:6,自引:0,他引:6
设G是简单图.设f是一个从V(G)∪E(G)到{1,2,…,k}的映射.对每个v∈V(G),令C_f(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}.如果f是k-正常全染色,且对任意u,v∈V(G),uv∈E(G),有C_f(u)≠C_f(v),那么称f为图G的邻点可区别全染色(简称为k-AVDTC).数x_(at)(G)=min{k|G有k-AVDTC}称为图G的邻点可区别全色数.本文给出路P_m和完全图K_n的Cartesion积的邻点可区别全色数. 相似文献
8.
联图Fn∨Pm的邻点可区别全染色 总被引:6,自引:0,他引:6
设G(V,E)是阶数至少为2的简单连通图,k是正整数,V∪E到{1,2,3,…k}的映射f满足:对任意uv,uw∈E(G),u≠w,有f(uv)≠f(vw);对任意uv∈E(G),有f(u)≠f(v), f(u)≠f(uv),f(v)≠f(uv);那么称f为G的k-正常全染色,若f还满足对任意uv∈E(G),有G(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G),v∈V(G)}那么称f为G的k-邻点可区别的全染色(简记为k-AVDTC),称min{k|G有k-邻点可区别的全染色}为G的邻点可区别的全色数,记作Xat(G).本文得到了联图Fn∨Pm的全色数. 相似文献
9.
关于图的均匀全色数分类 总被引:1,自引:0,他引:1
对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.将图按均匀全色数分类,证明了简单图在若干情况下的均匀全色数定理,得到了一些联图的均匀全色数. 相似文献
10.
《数学的实践与认识》2013,(20)
设G是简单图,图G的一个k-点可区别Ⅳ-全染色(简记为k-VDIVT染色)f是指一个从V(G)UE(G)到{1,2,…,k}的映射,满足:uv,uw∈E(G),v≠w,有f(uv)≠f(uw);u,v∈V(G),u≠v,有C(u)≠G(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.数min{k|G有一个k-VDIVT染色}称为图的点可区别Ⅳ-全色数,记为χ_(vt)(iv)(G).本文给出了双星S_(2n),轮W_n和扇F_n的点可区别Ⅳ-全色数. 相似文献
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.
图X称为边正则图,若X的自同构群Aut(X)在X的边集上的作用是正则的.本文考察了三度边正则图与四度Cayley图的关系,给出了一个由四度Cayley图构造三度边正则图的方法,并且构造了边正则图的三个无限族. 相似文献
14.
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. 相似文献
15.
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. 相似文献
16.
温一慧 《数学的实践与认识》2008,38(15)
通常没有有效的方法判别一般图G的k-边幻性.本文采用分析方法,讨论了一类非均匀边裂图SPE(Cn,h)的边幻性和k-边幻性,得到一些新的结果. 相似文献
17.
Timothy J. Hetherington 《Discrete Mathematics》2009,309(8):2153-2165
It is proved that if G is a plane embedding of a K4-minor-free graph with maximum degree Δ, then G is entirely 7-choosable if Δ≤4 and G is entirely (Δ+2)-choosable if Δ≥5; that is, if every vertex, edge and face of G is given a list of max{7,Δ+2} colours, then every element can be given a colour from its list such that no two adjacent or incident elements are given the same colour. It is proved also that this result holds if G is a plane embedding of a K2,3-minor-free graph or a -minor-free graph. As a special case this proves that the Entire Coluring Conjecture, that a plane graph is entirely (Δ+4)-colourable, holds if G is a plane embedding of a K4-minor-free graph, a K2,3-minor-free graph or a -minor-free graph. 相似文献
18.
证明了对于正整数k,n,si,ti(si,ti≥2,i=1,2,…,n),图n/U/i=1,Ksi,ti是k-优美图;对于正整数k,d(d≥2),k≠0(roodd)及n,si,ti(si,ti≥2,i=1,2,…,n),图n/U/i=1,Ksi,ti是(k,d)-算术图,前一结论推广了文[6]的相应结果。 相似文献
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.