检索结果-南通市图书馆

山东大学学报(理学版) 2024年

作者：刘兆志买吐肉孜·买司地克新疆师范大学数学科学学院

本文由因子图的退化度来刻画乘积图的退化度,再结合关于退化图线性荫度的结论,给出笛卡尔积图和部分直积图、强积图满足线性荫度猜想的退化度条件。证明了两个1-退化图字典积图满足线性荫度猜想,并给出了其在大部分情况下的线性荫度。

关键词：线性荫度猜想退化图笛卡尔积直积字典积

同方期刊数据库评论

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

退化图的均匀染色

嘉兴学院学报 2010年第3期22卷 31-34,50页

作者：朱俊蕾嘉兴学院数学与信息工程学院浙江嘉兴314001

若图G有一个正常k-顶点染色满足任两个色类中的顶点数至多相差1,则称G是k-均匀可染的.χe(G)=min{k|G是k-均匀可染的}称为图G的均匀色数.如果图G的任意子图H中都存在一个顶点v使得dH(v)≤d,则称图G为d-退化图.证明了满足|E(G)|≤2/3|V(... 详细信息

若图G有一个正常k-顶点染色满足任两个色类中的顶点数至多相差1,则称G是k-均匀可染的.χe(G)=min{k|G是k-均匀可染的}称为图G的均匀色数.如果图G的任意子图H中都存在一个顶点v使得dH(v)≤d,则称图G为d-退化图.证明了满足|E(G)|≤2/3|V(G)|的d-退化图(其中d=1,2)G是3-均匀可染的,满足|E(G)|≤3/4|V(G)|的d-退化图(其中d=2,3)G是4-均匀可染的.

关键词：均匀染色均匀色数退化图

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

图的邻和可区别染色

图的邻和可区别染色

作者：姚京京河北工业大学

学位级别：硕士

本文所考虑的图均为有限、无向、简单图,分别用V(G)和E(G)表示图G的顶点集和边集.图G的一个k-全染色是指从V(G)∪E(G)到{1,2,...,k}的一个映射.图G的k-全染色称为是正常的,如果满足相邻的或者相关联的两个元素染不同的颜色.类似的,可以... 详细信息

本文所考虑的图均为有限、无向、简单图,分别用V(G)和E(G)表示图G的顶点集和边集.图G的一个k-全染色是指从V(G)∪E(G)到{1,2,...,k}的一个映射.图G的k-全染色称为是正常的,如果满足相邻的或者相关联的两个元素染不同的颜色.类似的,可以定义图G的正常边染色.令φ为图G的正常k-边染色,用f(v)表示与点v相关联的边在φ中所染颜色的加和,即f(v)= Σe(?)v φ(e).若对于图G中的任何一条边uv∈E(G)都有f(u)≠ f(v),则称φ为图G的邻和可区别k-边染色,使得图G存在邻和可区别k-边染色的最小整数k称为图G的邻和可区别边色数,记作χ’Σ(G).类似的,若φ为图G的正常k-全染色,令g(v)=φ(v)+∑e(?)vφ(e),若对任一条边uv∈E((G)都有g(u)≠g(v),则称φ为图G的邻和可区别k-全染色,使得图G存在邻和可区别k-全染色的最小整数k称为图G的邻和可区别全色数,记作χ"(G).如果对于图G的每一条边e,都给定一个颜色集合Le,那么这个映射L就称为图G的一个边列表.如果图G存在邻和可区别边染色φ使得任意边e ∈E(G),都有φ(e)∈Le 则称图G是邻和可区别L-边可染的.对于图G的任意一个满足条件|Le| ≥ k的边列表L,其中e ∈E(G)为G的任意一条边,如果G都是邻和可区别L-边可染的,那么就称图G是邻和可区别k-边可选择的.使得图G是邻和可区别k-边可选择的最小整数k称为图G的邻和可区别边可选择性,记作ch’Σ(G).类似的,可以给出图G的邻和可区别全可选择性chΣ(G)的定义.由定义可知:ch’Σ(G)≥χ’Σ(G),ch"Σ(G)≥χ"Σ(G).本文主要考虑了若干图的邻和可区别边染色、邻和可区别边可选择性、邻和可区别全染色和邻和可区别全可选择性,并运用著名的组合零点定理与权转移方法得到以下主要结论.定理1 若图 G 为 Halin 图,当 △(G)≠ 4 时,χ’Σ(G)≤ △(G)+ 2;当△(G)≥ 6 时,χ’Σ(G)≤ △(G)+ 1.定理2 若图G为正常2-退化图且△(G)≥ 4,则ch’Σ(G)≤△(G)+ 4.定理3 设图G是2-退化图,则χ"(G)≤ △(G)+ 3.并且,若△(G)≥ 5,则χ"Σ(G)≤△(G)+ 2.定理4 设图G为最大度等于3的图且mad(G)图G为最大度等于3的图且mad(G)图G为最大度等于4的图且mad(G)图G是最大度至少为11的图且mad(G)图G是d-退化图,若图G满足以下条件之一:(1)d ≤ 8 且 △(G)≥ 2d;(2)d ≥9 且 △(G)≥ 5/2d-5.则 ch"Σ(G)≤ △(G)+ d+1.

关键词：邻和可区别边染色邻和可区别边可选择性邻和可区别全染色邻和可区别全可选择性退化图 Halin图组合零点定理

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图的邻点可区别全染色与局部反魔幻标号

图的邻点可区别全染色与局部反魔幻标号

作者：胡杰山东大学

学位级别：硕士

图的染色与标号问题是图论中的重要分支,其研究历史久远.作为图论发展的先导之一:四色定理,就是典型的染色问题.一直以来,图的染色与标号问题备受关注,它们不仅在图论上扮演重要角色,而且在社会科学、生命科学等方面都有着广泛应用.图... 详细信息

图的染色与标号问题是图论中的重要分支,其研究历史久远.作为图论发展的先导之一:四色定理,就是典型的染色问题.一直以来,图的染色与标号问题备受关注,它们不仅在图论上扮演重要角色,而且在社会科学、生命科学等方面都有着广泛应用.图的染色与标号本质上都是从图的点集或边集到实数集的映射.我们首先研究的是平面图的邻点可区别全染色问题.图G的k-全染色是指用集合[k]中的颜色(即元素)对图的点和边同时进行染色,使得相邻的点、相邻的边以及相关联的点和边都染不同颜色.对于G的一个k-全染色φ,我们用C(v)来表示由点v以及v的所有关联边的颜色构成的集合.我们称点v和点u是冲突的,如果两点相邻且Cφ(v)=Cφ(u).如果G中任意两个邻点都不冲突,则称k-全染色φ是邻点可区别的.我们将能够使得G具有邻点可区别全染色的最小的颜色数k称为图G的邻点可区别全色数,记作χ"a(G).2005年,Zhang等人首次提出这种染色并猜想:对于至少有两个点的连通图G,均有χ"a(G)≤△(G)+ ***等人已经证明对于最大度至少为10的平面图,上述猜想成立.本文在第二章中证明了对于最大度△(G)≥9的平面图G,有χ"a(G)≤ △(G)+ 3,改进了已有的结果,从而推动猜想的解决.进一步,对于最大度△(G)≥ 10的平面图G,我们得到了更好的上界,即χ"a(G)≤ △(G)+ 2.在第三章中,我们主要考虑图的局部k-反魔幻定向.设D是图G的一个定向且G的边数为m,D的局部k-反魔幻标号是指这样一个映射:将D的边集映射到[m + k],使得任意两条边的标号(即像)不同,且任意两个邻点的点和互异,其中点和是指该点所有入边的标号之和减去所有出边的标号之和.如果D有局部k-反魔幻标号,那么就称D是图G的一个局部k-反魔幻定向.当k = 0时,简称局部k-反魔幻标号(定向)为局部反魔幻标号(定向).之所以考虑该问题,是受著名的反魔幻标号猜想和1-2-3猜想的启发.反魔幻标号猜想自1990年被提出以来受到广泛关注,但至今仍未完全解决,其难度在于不仅要求任意两条边的标号互异,而且任意两个点所关联的边的标号之和也要不同.而1-2-3猜想只要求区分邻点,受此启发,我们开始研究图的局部反魔幻标号,进而推广到有向图.Chang等人猜想:每一个连通图都存在一个局部反魔幻定向.本文中,我们证明了每一个d-退化图都存在一个局部(d + 2)-反魔幻定向,并且该结论对于列表形式也成立,其中列表中元素均为正实数.由于平面图是5-退化的,因此每一个平面图都存在一个局部7-反魔幻定向.

关键词：邻点可区别全染色平面图局部反魔幻标号退化图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

稀疏图的均匀染色及其约束数

稀疏图的均匀染色及其约束数

作者：张华强西安电子科技大学

学位级别：硕士

如果将图G的顶点集V(G)分成k对两两不交的子集V(G)=∪i=1k Vi,使得每个子集Vi都能诱导出一个q-退化的子图,称这样的划分为图G的一个q-退化k-可染(划分).如果图G的q-退化k-染色,对于任意的1 ≤ i 详细信息

如果将图G的顶点集V(G)分成k对两两不交的子集V(G)=∪i=1k Vi,使得每个子集Vi都能诱导出一个q-退化的子图,称这样的划分为图G的一个q-退化k-可染(划分).如果图G的q-退化k-染色,对于任意的1 ≤ i图的均匀划分可以基于一些基本原则将大型复杂网络划分为一些小的子模块进行建模,这种划分在网络科学和信息科学中有很多实际应用.在第二章,基于均匀染色理论提出一个猜想:如果对于任意的整数k和d都满足k≥(Δ(G)+1)/(d+1),那么图G是均匀d-退化k-可染并且是均匀d-退化k-可选.这个猜想很强,因为它暗含了 Hajnal-Szemeredi均匀染色定理、均匀列表染色猜想(Kostochka,Pelsmajer和West,2003)、均匀点荫度猜想(Wu,Zhang和Li,2013)和均匀列表点荫度猜想(Zhang,2016).并证明该猜想对于完全图、区间图、(d+1)-退化图、最大平均度有界的图和最大度较大的平面图是成立的.在第三章,研究了将退化图均匀划分为低阶退化图的理论和算法,证明了最大度至多为n/β且具有n个顶点的d-退化图,当q,α和β满足明确定义的不等关系,且对于任意的k≥αd,每个Vi的大小至多为[n/k]时,该图有一个均匀q-退化k-划分(V1,V2,...,Vk),这样的均匀划分可以在O(n3)时间内完成.如果一个图可以嵌入在平面内使得每条边最多被交叉一次、任何两个交叉不共享关联点、任何两个交叉最多共享一个关联点,分别称该图为1-可平面图、IC-可平面图、NIC-可平面图.这三类超越可平面图在模块网络,社交网络和生物网络上有重要的应用.图的支配数是顶点集S的最小基数使得图中的每个点满足要么属于顶点集S要么是S的邻点.图的约束数是使图的支配数严格增加所需要删除的最少的边数,它是衡量网络脆弱性的一个重要参数.在第四章,研究1-可平面图,IC-可平面图与NIC-可平面图的结构,并利用得到的结构定理证明它们的约束数分别最多是13,11与12.

关键词：均匀染色退化图平面图 1-可平面图约束数

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

关于一些图的定向染色

关于一些图的定向染色

作者：王本娟山东大学

学位级别：硕士

一个定向图就是指一个无向图的定向,即给它的每条边一个方向.本文所说的定向图都是简单的有向图,即无环或无重弧的有向图.对一个定向图,我们用V（G）、A（G）、δ6（G）、Δ（G）分别表示图G的点集、弧集、最小度和最大度,d（υ）表示... 详细信息

一个定向图就是指一个无向图的定向,即给它的每条边一个方向.本文所说的定向图都是简单的有向图,即无环或无重弧的有向图.对一个定向图,我们用V（G）、A（G）、δ6（G）、Δ（G）分别表示图G的点集、弧集、最小度和最大度,d（υ）表示点υ的度.如果u、υ是图G中两个相邻的点,用uυ表示从u到υ的弧.G的阶数即为图G的点数. 假设G和H是两个有向图,那么从G到H的一个同态是指一个作用在V（G）到V（H）的一个映射φ,满足:（x,y）∈E（G）→（ψ（x）,ψ（y））∈E（H）则称H是G的一个目标图,记作G→H. 图H的一个k-正常染色是指将图H的点集分成K个子集（颜色类）的一个剖分,且满足任何两个相邻的点不属于同一个子集,相当于从H到完全图KK的一个同态,那么图H的染色数χ（H）就可以定义为H的所有k-正常染色中最小的k,即k满足H→Kκ,H→Kκ-1. 一个定向图G的一个k-定向染色是指将点集V（G）分成k个子集（颜色类）的一个剖分,且满足：（1）任何两个相邻的点不属于同一个子集;（2）任何两个子集之间的弧都有相同的方向.同样定向图G的定向色数χ0（H）可以定义为G的所有k-定向染色中最小的k,即k为满足G→H的所有定向图H的最小阶,也就是G的所有目标图的最小阶.对于一个无向图,它的定向色数是指它的所有定向中的最大的定向色数.其中强定向染色是指目标图为Cayley图的定向染色,强定向染色数记为χs（H）. 关于图的定向染色,Kostochka和Sopena等人做了图的无圈定向色数的研究,Robert Samal研究了平面图的强定向染色Ochern研究了无三角平面图的定向染色,Borodin等人研究了给定围长的全体平面定向图,并在2004年发表了围长不限的稀疏图之间的同态问题的文章,同时对一个图的最大平均度与定向色数之间的关系也作了深入研究. 本文主要研究几类退化图,双外平面图和特殊平面图的强定向染色问题,得到如下结果：定理1令G为2-退化图,则χs（G）≤7. 定理2令G为3-退化图,则χs（G）≤19. 定理3令G为4-退化图,则χs（G）≤67. 定理4令G为双外平面图,且G不同构于P,则χs（G）≤19,χs（P）≤67. 定理5设G为平面图,且G不含4-7圈,则χs（G）≤19. 对上述问题本文主要是运用可约化的方法和权值重新分配的方法来证明的. 在本文的最后我们对定向染色的定义进行了推广,定义了一种新的染色—有向2-路染色. 令m为大于等于1的整数.定向图G的一个有向m-路k染色f是指一个映射f：V（G）→｛1,2,…,k｝,满足：（1）对任意的两个点x,y，如果1≤d（x, y）≤m,则f（x）≠f（y）;（2）任何两个子集之间的弧都有相同的方向.定向图G的有向m-路色数χm（G）是指G的所有有向m-路k染色f的最小的k.那么无向图G的有向m-路色数χm（G）是它的所有定向图的有向m-路色数χm（G）中的最大值.当m=2时,即为有向2-路染色. 根据Halin图的有向2-路色数小于等于7的结论,我们对2-退化图的有向2-路色数作了猜想：猜想如果G是一个2-退化图,则χ2（G）≤5.

关键词：双外平面图退化图定向染色强定向染色有向2-路染色