关于Mycielski图补图的一些指标的结果

拓扑指标是分子结构的数学描述符,它将分子的形状、大小、分支等结构特征数值化,且计算简便、取值客观,不易受经验和实验的影响,是数学与化学研究中非常活跃的领域之一。研究拓扑指标图不变量可用于描述和预测有机化合物的理化或药理性质。文章研究Mycielski图的补图的两类度距离指标:Schultz指标和修正的Schultz指标。同时,还给出了一些特殊图的Mycielski图及其补图的Lanzhou指标的表达式。

Mycielski图的哈密尔顿连通性

2017年,Jarnicki等人提出如下猜想:如果图G是哈密尔顿连通的且不是K2,那么它的Mycielski图也是哈密尔顿连通的。在这篇论文中,证明了该猜想在部分图上是正确的。本文的主要研究结果如下:刻画了特殊图类的Mycielski图是哈密尔顿连通的。当图G满足最小度时,是哈密尔顿连通的。

广义Mycielski图M_(n)(C_(m)^(3))的邻和可区别全染色

将阶数至少为4的圈图中距离为3的任意两点连边得到了圈的3次方图,应用构造染色法,研究了广义Mycielski图M_(n)(C_(m)^(3))和M n(C k 2k)的邻和可区别全染色问题,得到了邻和可区别全色数,验证了邻和可区别全色数的猜想对这两类图的正确性.

轮和路的广义Mycielski图的星全染色

图G的一个正常全染色被称作G的星全染色,如果G中任意路长为2的点和边着色均不相同.图的全部星k-全着色中最小的数k称为它的星全色数.讨论轮和路的广义Mycielski图的星全染色问题,得到不同情况下它们的星全色数,其中每个点的色集合包含该点及其关联边的颜色.

星图和扇图的广义Mycielski图的星全染色

图G的一个正常全染色被称作G的星全染色,如果G中任意路长为2的点和边着色均不相同,则称它为图G的星K-全着色.图的全部星K-全着色中最小的数K称为它的星全色数.讨论了星图和扇图的广义Mycielski图的星全染色问题,得到了不同情况下它们的星全色数,其中每个点的色集合包含该点及其关联边的颜色.

完全图的广义Mycielski图的邻点可区别的全色数

对图 G 的一个 k-正常全染色法,若满足相邻点的点染色和关联边的色集合不同时,称该染色法为邻点可区别全染色,其所用小染色数 k 称为 G 的邻点可区别全色数．得到了完全图 K_m 的广义 Mycieski 图 M_n(K_m)(n≥1,m≥3)的邻点可区别全色数．

多重Mycielski图的邻点可区别全染色

给出了一个简单图G的k重Mycielski图Mk(G)(其中k为正整数)的邻点可区别全色数的上界,得到了圈、星、轮、扇的k重Mycielski图的邻点可区别全色数.

关于几类特殊图的Mycielski图的点可区别全色数

讨论并得到了路、圈、完全图、星、扇、轮的Mycielski图的点可区别全色数.

关于图的广义Mycielski图的邻点可区别关联着色

邻点可区别关联着色是使得相邻顶点的颜色集不同的关联着色。主要研究了路,圈C3m,C4m与完全图的广义Mycielski图的邻点可区别关联色数,拓展了图着色的领域,便于更好的研究图的结构。

若干Mycielski图邻点可区别Ⅰ-均匀全染色

图G的一个邻点可区别Ⅰ-均匀全染色是指对图G的邻点可区别的一个Ⅰ-全染色f,若f还满足||T_i|-|T_j||≤1(i≠j),其中T_i=V_i∪E_i={v|v∈V(G),f(v)=i}∪{e|e∈E(G),f(e)=i},则称f为图G的一个邻点可区别Ⅰ-均匀全染色,而图G的邻点可区别Ⅰ-均匀全染色中所用的最少颜色数称为图G的邻点可区别Ⅰ-均匀全色数.通过函数构造法,得到了M(Pn)、M(Cn)、M(Sn)的邻点可区别Ⅰ-均匀全色数,并且满足猜想.

多重Mycielski图的点可区别全染色

给出了最小度至少是2的图G的k重Mycielski图M^k(G)(其中k为正整数)的点可区别全色数的上界.

路的广义Mycielski图的邻点可区别的全染色

图G的一个正常全染色称为G的邻点可区别的全染色,如果对于G中任意相邻的点u和v有C(u)≠C(v).研究图的邻点可区别的全染色就是找出图的邻点可区别全染色的最小色数.利用穷举法和组合分析法研究路的广义Mycielski图的邻点可区别的全染色,得到路的广义Mycielski图的邻点可区别的全色数.

一些图的Mycielski图的均匀邻强边染色

如果图G的一个正常边染色满足相邻点的色集不同,且任意两种颜色所染边数目相差不超过1,则称为均匀邻强边染色,其所用最少染色数称为均匀邻强边色数.本文得到了路、圈、星和扇的Mycielski图的均匀邻强边色数.

关于S_m广义Mycielski图的若干色性

对图G(V,E),Mn(G)称为G的广义Mycielski图,其中V(Mn(G))={v00,v01,v02,…,v0m;v10,v11,v12,…,v1m;…;vn0,vn1,…,vnm};E(Mn(G))=E(G)∪{vi jv(i+1)k|v0jv0k∈E(G),0≤j,k≤m,i=0,1,…,n-1},m+1阶星Sm的广义Mycielski图,记为Mn(Sm),给出了Mn(Sm)的点色数,边色数,邻强边色数,全色数,邻点可区别的全色数.

Mycielski图的对策染色数

介绍了一种新的图着色——关于图 G的对策色数 和对策色数χ*g ( G) .确定了 Mycielski图的对策色数 ,并给出了选手 A获胜的对策 .讨论了关于对策染色

关于完全图的Mycielski图的循环色数的若干结果

给出了任意图 G的多重 Mycielski图 Mm (G)的简单定义方式 ,用不同的方法证明了当完全图 Kn 的阶数 n足够大时 ,Mm(Kn)的循环色数等于其点色数 .特别证明了 ,n =7,8,9时 ,M3 (Kn)的循环色数等于其点色数 ,从而使得“当 n m +2 ,有χc(Mm(Kn) ) =χ(Mm(Kn) ) =m +n成立”的猜想有了更新的进展 .

圈的Mycielski图的均匀全染色

对图G(V,E),μ(G)称为G的Mycielski图,V(μ(G))=V(G)∪{v′｜v∈V(G)}∪{w},E(μ(G))=E(G)∪{uv′｜u∈V(G),v′∈V′,且uv∈E(G)}∪{wv′｜v′∈V′}.其中,w V(G),V′={v′｜v∈V(G)}.证明了圈Cp的Mycielski图M(Cp)的均匀全色数为Δ(M(Cp))+1,其中Δ(M(Cp))为M(Cp)的最大度.

广义Mycielski图的邻点可约边染色

对简单图G(V,E),若存在自然数k(1≤k≤Δ(G))和映射f∶E(G)→{1,2,…,k}使得对任意相邻两点u,v∈V(G),uv∈E(G),当d(u)=d(v)时,有C(u)=C(v),则f为G的k-邻点可约边染色,其所用最多染色数称为图G的邻点可约边色数,本文得到了若干广义Mycielski图的邻点可约边染色数.

完全二部图的Mycielski图的点可区别全色数

图的一个正常的全染色如果满足不同点的点及其关联边的色集合不同,则称该染色法为点可区别全染色,其所用最少颜色数称为该图的点可区别全色数.给出了完全二部图的Mycielski图的点可区别全色数.

关于图的Mycielski图的边色数

对图G(V,E),μ(G)称为G的Mycielski图,V(μ(G))=V(G)∪{v′｜v∈V(G)}∪{w},且w V(G),而E(μ(G))=E(G)∪{uv′｜u∈V(G),v′∈V′,且uv∈E(G)}∪{wv′｜v′∈V′},其中w V(G),V′={v′｜v∈V(G)}.猜想对简单图G,χ′(μ(G))=Δ(μ(G))+1当且仅当G=K2.其中,χ′(G)表示G得边色数,且证明了Δ(G)>｜V(G)｜2时猜想为真.