直积图的邻点可区别全染色

设G,H为简单图.给出直积图G×H的邻点可区别全色数的一个上界,得到星、轮、扇分别与m阶路、圈的直积图的邻点可区别全色数.

直积图P_m∧S_n、P_m∧F_n与P_m∧W_n的第一类弱全染色

图染色是图论的重要组成部分,它有着一定的理论意义和实际应用背景.给出了直积图P_m∧S_n、P_m∧F_n与P_m∧W_n的第一类弱全染色数,并分别给出了构造性的证明,进而验证了这些图对第一类弱全染色猜想成立.

直积图P_m∧P_n与P_m∧C_n的第一类弱全染色

图染色是图论的重要组成部分,它有着一定的理论意义和实际应用背景.应用构造染色函数法给出了直积图P_m∧P_n与P_m∧C_n的第一类弱全染色数,从而验证了第一类弱全染色猜想的成立.

弱直积图的2-距离色数

图G(V,E)的2-距离染色是指正常的顶点染色,且任意距离不大于2的两个顶点着不同的颜色.得到弱直积图的一个2-距离色数的可达界,即Δ(G).Δ(H)+1≤χ2(G×H)≤χ2(G).2χ(H),且给出一些特殊弱直积图的2-距离色数,说明此界可达.如χ2(P2×Pn)=Δ(P2).Δ(Pn)+1=3(n≥3),χ2(Pm×Pn)=Δ(Pm).Δ(Pn)+1=5(m≥3,n≥3)说明下界可达,χ2(Km×Kn)=χ2(Km).2χ(Kn)=mn,说明上界可达.

直积图的分数色数

有关直积图的色数,在图论中有Hedetniemi猜想,该猜想是建立在连通图的基础上,并且已证明该猜想对于一些特殊图是成立的.证明了对于连通的点传递图,Hedetniemi猜想在分数染色意义下也是成立的.

若干直积图的邻点可区别I-全色数

应用穷染递推的方法研究了路与扇、路与轮、路与完全图构成的直积图的邻点可区别I-全色数,进一步验证了若干直积图的邻点可区别I-全染色猜想。

直积图C_m×C_n的多彩染色问题

研究圈和圈的直积图C_m×C_n的多彩染色.通过构造C_m×C_n的同构图,利用反证法确定了C_m×C_n的2-多彩色数以及C_m×C_4的3-多彩色数的确切值,其中m、n≥3.

在两个圈的直积图上的平衡二元映射

对于直积图G=C m□C n,f∶V(G)→Z2={0,1}是任意一个定义在顶点集上的二元映射,定义V0=f-1(0),V1=f-1(1)。若|V1|-|V0|≤1,则称映射f是平衡的。f可以自然诱导出一个定义在边集E(G)上的二元映射f E∶E(G)→Z2,且f E(xy)=f(x)+f(y)。令E0=f-1E(0),E1=f-1E(1),那么D(G,f)=|E1(f)|-|E0(f)|。文章通过在两个圈的直积图C m□C n上构造一系列平衡二元映射的方法,完全确定了在平衡映射下的边差集D(Cm□Cn)。

刍议直积图C_(m)×C_(n)的多彩染色问题

基于4色问题产生了图染色理论,该理论在离散数学知识中作为重要知识之一,被广泛应用于社会生活各方面,例如交通规划、经济分析、网络通信。对直积图C_(m)×C_(n)多彩染色展开研究,构造同构图C_(m)×C_(n),运用反证法证明C_(m)×C_(n)的2-多彩色数与C_(m)×C_(4)的3-多彩色数确切值,公式中m、n均≥3。

若干直积图的邻点可区别VE-全色数

应用穷染递推的方法研究了路与路(圈、星、扇、轮、完全图)构成的直积图的邻点可区别VE-全染色,并给出了具体的染色方案,进一步得到了邻点可区别的VE-全色数.

路和完全图的乘积图的线性荫度

1970年,Harary提出了图的线性荫度概念,它指的是把图G的边集分解成边不交的线性森林的最少数目。线性森林是指每个连通分支都是路的森林。本文通过对路和完全图的笛卡尔积图、直积图进行边分解,证明了路和完全图的笛卡尔积图、直积图符合线性荫度猜想,进而证明了路和完全图的乘积图满足线性荫度猜想。

若干直积图的Smarandachely邻点全染色

运用分析法和构造Smarandachely邻点全染色函数法研究了若干直积图的Smarandachely邻点全色数,进一步验证了图的Smarandachely邻点全染色猜想.

直积图邻点可区别E-全染色的一些结论

运用分析法研究了直积图的邻点可区别E-全染色,讨论了对于点色数至少为2以及邻点可区别E-全色数为3,4的简单图的直积图的邻点可区别E-全色数,并得出了一些相关推论。

乘积图的博弈染色数

本文讨论的图是两棵树的乘积图. 分别研究了树和树的笛卡尔积图、直积图和强积图的 (a, 1)-博弈染色数, 给出了三种乘积图的 (a, 1)-博弈染色的上界. 特殊地, 如果其中一棵树是一条路, 那么我们类似的可以得出关于树和路的乘积图的 (a, 1)-博弈染色数的结果.

一个路与一个完全二部图直积的L(2,1)-标号

通过分类讨论,归纳综合的方法,研究一个路与一个完全二部图直积的L(2,1)-标号问题,得到以下的结果:(1)当n≥3时,P_3×K_(n,n)的L(2,1)-标号数为3n;(2)当n≥3时,P_4×K_(n,n)的L(2,1)-标号数为3n;(3)当m≥5,n≥3时,P_m×K_n,n的L(2,1)-标号数为3n+1.

一个圈与一个完全二部图的直积的L(2,1)-标号

通过分类讨论、归纳综合的方法,研究了一个圈与一个完全二部图的直积的L(2,1)-标号问题,得到了以下的结果:(1)当n≥3时,C3×Kn,n的L(2,1)-标号数为3n+1;当n≥3时,C4×Kn,n的L(2,1)-标号数的上界是4n;当n≥3时,C5×Kn,n的L(2,1)-标号数为5n-1;(2)当n≥3,m≥6,m≡0(mod3)时,Cm×Kn,n的L(2,1)-标号数为3n+1;当n≥3,m≥6,m≡1(mod3)或m≡2(mod3)时,Cm×Kn,n的L(2,1)-标号数的上界是4n.

树和乘积图的圆L(j,k)-标号数(英文)

设j,k和m是3个正整数.给定一个图G.设f:V(G)→{0,1,…,m-1}是一个映射.如果对图G的任意一对相邻顶点u和v都有f(u)-f(v)m≥j,对任意一对距离为二的顶点都有f(u)-f(v)m≥k,其中a-bm=min{a-b,m-a-b},则称f是图G的一个圆m-L(j,k)-标号.使得图G有圆m-L(j,k)-标号的最小的正整数m称为图G的圆L(j,k)-标号数,记为σj,k(G).对任意2个满足j≤k的正整数,确定了树以及2个完全图的笛卡尔乘积图和直积图的圆L(j,k)-标号数.

路的三类积图的无圈全染色

研究路的三类积图的笛卡尔积、直积与半强积的无圈全染色,并给出了两个路的笛卡尔积、直积和半强积的无圈全染色数.

树和路乘积图的线性荫度

1970 年 Harary 提出图的线性荫度的概念, 指的是将图 G 的边集分解成 m 个边不交的线性森林的最小整数 m. 线性森林即每一个连通分支都是路的图. 本文主要对树和路的乘积结构进行讨论, 通过对乘积图中的边进行划分, 证明了树和路的笛卡尔积图、直积图、强积图满足线性荫度猜想。

路的积图的无圈染色

研究路的两类积图直积与半强积的无圈染色,并给出了两个路的直积和半强积的无圈染色数.