共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
本文刻划了周期为p的稳定平移箭图Z△/(τp)的邻接矩阵,并给出了由星形箭图△所决定的平移箭图Z△/(τp)的邻接矩阵的具体形式. 相似文献
3.
4.
谱半径前六位的n阶单圈图 总被引:1,自引:0,他引:1
郭曙光 《高校应用数学学报(A辑)》2003,18(4):480-486
恰含一个圈的简单连通图称为单圈图。Cn记n个顶点的圈。△(i,j,κ)记C3的三个顶点上分别接出i,j,κ条悬挂边所得的图,其中i≥j≥κ≥0.Sl^n-l记Cl的某一顶点上接出n-l条悬挂边所得到的图。△(n-4 1,0,0)记△(n-4,0,0)的某个悬挂点上接出一条悬挂边所得到的图。本文证明了:若把所有n(n≥12)阶单圈图按其最大特征值从大到小的顺序排列,则排在前六位的依次是S3^n-3,△(n-4,1,0),△(n-4 1,0,0),S4^n-4,△(n-5,2,0),△(n-5,1,1)。 相似文献
5.
对于一个图G的正常边着色,如果此种边着色使得该图没有2—色的圈,那么这种边着色被称为是G的无圈边着色.用d(G)表示图G的无圈边色数,即G的无圈边着色中所使用的最小颜色数.Alon N,Sadakov B and Zaks A在[1]中有如下结果:对于围长至少是2000△(G)log△(G)的图G,有d(G)≤△ 2,其中△是图G的最大度.我们改进了这个结果,得到了如下结论:对于围长至少是700△(G)log△(G)的图G,有d(G)≤△ 2. 相似文献
6.
研究了一类简单图G的色数x(G)与最大度△(G)的关系,对满足x(G)>(S~2+S)/2的X(G)+S阶色临界图G,证明了x(G)=△(G)+1-S,或等价地,△(G)+1-[((8△(G)+17~(1/2)-3/2]≤X(G)≤△(G)+1,这一结果部分改进了Brooks经典不等式X(G)≤△(G)+1,并完全刻画n+3(n≥4)个顶点的n-临界图的结构。 相似文献
7.
吴春生 《数学的实践与认识》2013,43(2)
设△是一个有限无圈的箭图.引入了由△所决定的偏周期预投射代数,它是一个定义在周期为p的稳定平移箭图Z△/(rp)上的代数,记为Π_(Q(△,p),J).推广了Eting和Eu的方法并得到无圈的连通星形箭图△所决定的偏周期预投射代数Π_((Q(△,p)),J)的希尔伯特级数的计算公式. 相似文献
8.
本文刻划了周期为P的稳定平移箭图ZΔ/(τ^p)的邻接矩阵,并给出了由星形箭图△所决定的平移箭图ZΔ/(τ^p)的邻接矩阵的具体形式. 相似文献
9.
一个平面图G的边面色数xef(G)是指对G的边和面进行染色所用最少的颜色数目,并同时使得相邻或相关联的两个元素间染不同颜色.若G是一个系列平行图,也就是不含K_4的剖分作为子图的平面图,则有Xef(G)≤max{7,△(G) 1};同时如果G还是2-连通的且△(G)>6,则有Xef(G)=△. 相似文献
10.
用P(G,λ)表示简单图G的色多项式.设G是一个给定的简单图,若对任意简单图H,当P(H,λ)=P(G,λ)时都有H和G同构(记为H≌G),则称图G是色唯一的.本文证明了以下结果:设n,k,△都为非负整数,其中k≥0,△∈{4,5},若n≥1/3k~2+1/3△~2-1/3k△-1/3k-1/3△+4/3,则完全三部图K(n,n+△,n+k)是色唯一的.同时还给出了一个猜想. 相似文献
11.
12.
13.
14.
广义图K(n,m)的全色数 总被引:1,自引:0,他引:1
1965年,M.Behzad和Vizing分别提出了著名的全着色猜想:即对于简单图G有:XT(G)≤△+2,其中△是图G的最大度.本文确定了完全图Kn的广义图K(n,m)的全色数,并利用它证明了Lm×Kn(m≥3)是第Ⅰ型的. 相似文献
15.
The Entire Coloring of Series-Parallel Graphs 总被引:2,自引:0,他引:2
Jian-liangWu Yu-liangWu 《应用数学学报(英文版)》2005,21(1):61-66
The entire chromatic number X_(vef)(G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color. Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K_(4-) It is proved in this paper that X_(vef)(G)≤max{8, △(G) 2} and X_(vef)(G)=△ 1 if G is 2-connected and △(G)≥6. 相似文献
16.
17.
1988年,张忠输等证明了对于△(G)≥3的外平面图G,全色数XT(G)=△(G)+1.本文给出此结论一个简单证明,方法是全新的. 相似文献
18.
子图识别问题(SRP)就是在一个图G中确定并寻找是否存在和另一个图H相同构的子图.本文将引入图的层分解概念,并以此为基础建立识别图的同构子图的算法.该算法的复杂性为O(n(△-1)^k-1),其中△是图G的度,即G中点的最大度,n,k分别是图G,H的阶. 相似文献
19.
吴春生 《数学的实践与认识》2010,40(12)
设△是一个有限无圈的箭图.引入了由Δ所决定的偏周期预投射代数,它是一个定义在周期为p的稳定平移箭图Z△/(τ~p)上的代数,记为Π_(Q(Δ,p),J).当周期p=1时,偏周期预投射代数就是偏预投射代数.我们推广了Eting和Eu的方法并得到无圈的星形箭图△所决定的偏周期预投射代数Π_((Q(Δ,p)),J)的Hilbert级数的计算公式. 相似文献
20.
无K4—图子式的图的谱半径 总被引:1,自引:0,他引:1
G是一个无K4-图子式、顶点数为n的简单图,ρ(G)是图G的谱半径。本文得出一个关于ρ(G)的上解界。ρ(G)≤1/2 √2n-15/4。等式成立当且仅当G≌K2倒△(n-2)K1,其中G1倒△G2是由G1∪G2组成,并且G1中的第一个点和G2中的每一个点之间都有一定边相连:(n-2)K1表示(n-2)个孤立点的集合。 相似文献