检索结果-南通市图书馆

一致超图中Berge线性森林的Turán数

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

数学进展 2023年第6期52卷 1005-1012页

作者：康丽英黄家韦薛益赛吴志伟上海大学数学系上海200444

设F是一个图,H是一个超图,如果存在一个双射Φ:E(F)→E(H),使得■e∈E(F)有e■Φ(e),那么称超图H是Berge-F.不含Berge-F作为子超图的n阶r-一致超图所能达到的最大边数称为Berge-F的Turán数,记作ex_(r)(n,Berge-F).线性森林是指连通分... 详细信息

设F是一个图,H是一个超图,如果存在一个双射Φ:E(F)→E(H),使得■e∈E(F)有e■Φ(e),那么称超图H是Berge-F.不含Berge-F作为子超图的n阶r-一致超图所能达到的最大边数称为Berge-F的Turán数,记作ex_(r)(n,Berge-F).线性森林是指连通分支全是路或者孤立顶点的图.设L_(n,k)是一类含有n个顶点k条边的线性森林图族.本文研究了r-一致超图中Berge-L_(n,k)的Turán数.当r≥k+1和3≤r≤[(k-1)/2]-1时,分别确定了ex_(r)(n,Berge-L_(n,k))的精确值;当[(k-1)/2]≤r≤k时,给出了ex_(r)(n,Berge-L_(n,k))的上界.

关键词：一致超图 Berge超图线性森林 Turán数

在线全文

学校读者我要写书评

暂无评论

关于线性森林的广义图兰问题研究

数学进展 2020年第4期49卷 406-412页

作者：段秀转王健杨卫华太原理工大学数学学院太原山西030024

令G表示n个顶点的图.图G的一个线性森林是G中由顶点不交的路以及孤立点组成的子图.其中,G的边数最多的线性森林称为图G的最大线性森林,用l(G)表示最大线性森林的边数.设定t=[k-1/2].令r3(G)表示图G中三角形的个数.在本文中,我们证明了如... 详细信息

令G表示n个顶点的图.图G的一个线性森林是G中由顶点不交的路以及孤立点组成的子图.其中,G的边数最多的线性森林称为图G的最大线性森林,用l(G)表示最大线性森林的边数.设定t=[k-1/2].令r3(G)表示图G中三角形的个数.在本文中,我们证明了如果l(G)=k-1且δ(G)≥δ,那么对于任意的k

关键词：广义Turán数线性森林三角形 k-闭包

在线全文

学校读者我要写书评

暂无评论

匹配与线性森林的图兰型问题研究

匹配与线性森林的图兰型问题研究

作者：贺雪媛太原理工大学

学位级别：硕士

给定两个简单图T和***数ex（n,H）定义为不包含H作为子图的n个顶点的图中边数的最大值.广义Turan数ex（n,T,H）定义为不包含H作为子图的n个顶点的图中T子图的最大个数.当T=K2时,广义Turan数ex（n,T,H）即为Turan数ex（n,H）.如果G的每... 详细信息

给定两个简单图T和***数ex（n,H）定义为不包含H作为子图的n个顶点的图中边数的最大值.广义Turan数ex（n,T,H）定义为不包含H作为子图的n个顶点的图中T子图的最大个数.当T=K2时,广义Turan数ex（n,T,H）即为Turan数ex（n,H）.如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N（G,F）表示G中F子图的个数.图G的线性森林是指由图G中顶点不交的路和孤立点组成的子图.其中,边数最多的线性森林称为图G的最大线性森林.令Ks,t*是通过将Ks,t中大小为s的部集替换为相同大小的团得到的图.近年来,Turan数和广义Turan数受到国内外学者的广泛研究.本文主要研究了退化图中团和二部图的最大个数问题,当n充分大时,给定匹配数和最小点覆盖数的图中最大边数问题以及给定最大线性森林大小的图中团和二部图个数问题,具体内容如下:第2章研究了退化图中的团的个数和完全二部图的个数.我们计算了n个顶点的k-退化图G中N（G,Kt）的精确上界,以及在s,t≥1,n≥k+1且s+t≤k条件下,N（G,Ks,t）的精确上界,并刻画了所对应的极值图;此外,当n ≥ 2k+2r2+r+1时,给定最大匹配和最小点覆盖数,我们计算了图G的最大边数.第3章研究了线性森林中的Kr和Ks,t*的个数.首先,我们介绍了移位操作的定义,进一步证明移位操作不会增加G中最大线性森林的边数.其次,通过移位操作,刻画了包含k-1条边的最大线性森林的所有移位图.最后,计算了不包含k条边的n个顶点的线性森林的图中Kr和Ks,t*的最大个数.

关键词： k-退化最大匹配最小点覆盖线性森林移位操作

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

若干线性森林与圈的拉姆齐数研究

若干线性森林与圈的拉姆齐数研究

作者：王珂青海师范大学

学位级别：硕士

拉姆齐理论是离散数学的一个主要分支,图的拉姆齐数研究是拉姆齐理论的研究中占有重要地位.拉姆齐数的作用在于量化拉姆齐理论中的一些存在性定理.所以,图的拉姆齐数的研究是有理论意义的,它的研究求解对解决其他NP困难问题也有重大作用... 详细信息

拉姆齐理论是离散数学的一个主要分支,图的拉姆齐数研究是拉姆齐理论的研究中占有重要地位.拉姆齐数的作用在于量化拉姆齐理论中的一些存在性定理.所以,图的拉姆齐数的研究是有理论意义的,它的研究求解对解决其他NP困难问题也有重大作用.拉姆齐数的研究求解不仅在数学的理论发展中有着重要的价值,而且也应用于信息论和理论计算机科学等许多领域.1930年,英国数学家Ramsey建立了拉姆齐理论.图的拉姆齐数的研究中常见的是二部拉姆齐数,加莱-拉姆齐数和边拉姆齐数.1975年,Beineke和Schwenk对经典拉姆齐数进行了推广,给出了二部拉姆齐数br(m,n)的定义.二部拉姆齐数是指对于整数m,n(1≤m≤n),找到最小的整数p使得在对完全二部图K的边进行任意的二着色后,一定会存在单色的K.1978年,Erd(?)s给出了关于边拉姆齐数(?)r(G,H)的定义:给定两个图G和H,对于最小的正整数m,对满足|E(F)|=m的图F的边进行二着色,如红蓝着色,在图F中要么存在一个红色子图G,要么存在一个蓝色子图H.1967年,Gallai首先在图的传递方向的前提下研究了不包含彩虹三角形的结构.k-边着色的加莱-拉姆齐数gr(G:H)的定义:对于给定的两个图G和H,定义了最小的整数m使得在对完全图K的边进行任意k-边着色后,要么包含彩虹的图G,要么包含单色的图H.二部拉姆齐数,边拉姆齐数和加莱-拉姆齐数的区别是:二部拉姆齐数是对完全二部图的边进行任意着色,确定的是完全二部图的一个部集的顶点数;边拉姆齐数是对图的边进行着色,确定的是图的边数;加莱-拉姆齐数是对完全图的边进行任意着色,确定的是完全图的顶点数.本文首先研究了有关路图的二部拉姆齐数,并给出了准确值;接下来研究了有关线性森林的边拉姆齐数,对于有关2K与线性森林的边拉姆齐数给出了准确值,涉及t K(t≥3)与线性森林的边拉姆齐数给出了较好的上下界;最后研究了关于圈图的加莱-拉姆齐数,给出了准确值或上下界,并推广到了一般情况.

关键词：二部拉姆齐数加莱-拉姆齐数边拉姆齐数线性森林圈图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

度条件与过线性森林的圈

度条件与过线性森林的圈

作者：何剑华中师范大学

学位级别：硕士

设k,s,t为满足s≤t的非负整数,F是由t条点不交的路构成的边数为k的森林,如果F中恰有s条路是单点,则称F为(k,t,s)-线性森林。不必考虑单点路的个数时,可称F为(k,t)-线性森林。如果对于n阶图G中的每个(k,t)-线性森林F,都存在G中的一个哈... 详细信息

设k,s,t为满足s≤t的非负整数,F是由t条点不交的路构成的边数为k的森林,如果F中恰有s条路是单点,则称F为(k,t,s)-线性森林。不必考虑单点路的个数时,可称F为(k,t)-线性森林。如果对于n阶图G中的每个(k,t)-线性森林F,都存在G中的一个哈密顿圈过F,则称G是(k,t)-哈密顿的。Ralph ***等人给出了G是(k,t)-哈密顿图的σ型条件。本文讨论了G中其他长度的过(k,t,0)-线性森林的圈,得到: 设k,t和n是满足2≤k+t≤n的正整数,G是n阶图,F是(k,t,0)-线性森林。如果(i)σ(G)≥2+k,当F=P,(ii)σ(G)≥n+k-∈(n,k),其它情况,则对任意r∈[max{4,k+2t},n],G中存在长为r或r+1的圈过F。

关键词：圈线性森林度泛圈

过线性森林的圈问题研究与禁止6长路的连通极图刻画

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

过线性森林的圈问题研究与禁止6长路的连通极图刻画

作者：邵雅欣太原理工大学

学位级别：硕士

二十世纪六十年代以来,图论中很多著名的问题和猜想引起了全世界学者的广泛研究,如哈密尔顿问题,图兰问题,谱图兰问题等等.图的圈和路理论是图论研究中的一个重要分支,在图论乃至整个离散数学领域中占有非常重要的地位,其实际应用也越... 详细信息

二十世纪六十年代以来,图论中很多著名的问题和猜想引起了全世界学者的广泛研究,如哈密尔顿问题,图兰问题,谱图兰问题等等.图的圈和路理论是图论研究中的一个重要分支,在图论乃至整个离散数学领域中占有非常重要的地位,其实际应用也越来越广泛.在日常生活中,许多优化问题和网络问题诸如计算机网络中的文件传输问题,时间表问题等等都涉及到图的圈和路理论.本文主要研究了图论中关于圈和路的一些性质,包括哈密尔顿性、泛圈性和禁止路的刻画问题.主要内容如下:第1章首先介绍了本文涉及到的一些重要概念和符号,接着从圈和路的哈密尔顿性与泛圈性、禁止子图的谱Turán问题两方面对本文相关的研究进展进行阐述,最后介绍了本文所得到的主要结果.第2章研究了Faudree等提出的(k,t,2t+k)-泛圈图的问题猜想,证明了特定度和条件下,对任意r∈[max{4,k+2t},n],G中存在长为r或r+1的圈过线性森林F.另外,还研究了图G是(k,t)-哈密尔顿图的边数条件,并举例说明了该条件是紧的.第3章着眼Nikiforov提出的谱图兰猜想,即对于h≥2,n足够大,exsp(n,C2h+2)=ρ(sn,h+),且Sn,h+是唯一的极图,研究了禁止6长路的连通极图的刻画问题,得到极图同构于Sn,2+,且在此情况下取到极值2n-2.第4章总结了本文研究的成果并提出可供进一步讨论的问题及研究思路.

关键词：线性森林哈密尔顿圈泛圈禁止子图极图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

度和与边数条件下过线性森林圈的一些研究

应用数学进展 2023年第1期12卷 29-36页

作者：邵雅欣杨卫华太原理工大学数学学院山西太原

2009年,Faudree提出在给定的σ2(G)条件下,图G过(k,t)-线性森林的(k,t,2t+k)-泛圈问题。本文证明了在该σ2(G)条件下,对任意,G中存在长为r或r+1的圈过(k,t)-线性森林。此外,本文还给出了图G是(k,t)-哈密顿的一个边数条件。

关键词：线性森林哈密顿圈泛圈

维普期刊数据库博看期刊评论

在线全文

学校读者我要写书评

暂无评论

可嵌入到欧拉示性数非负的曲面图的线性荫度

山东大学学报（理学版） 2018年第12期53卷 17-22页

作者：陈洪玲王慧娟高红伟青岛大学数学与统计学院山东青岛266071

图G的线性荫度是一种非正常的边染色,即它的边集合E(G)可以分割成线性森林的最小数量,用la(G)表示。主要研究最大度Δ(G)≥7且可嵌入到欧拉示性数非负曲面图G上的线性荫度,证明了如果图G中不含相邻的含弦6-圈,则图G的线性荫度为「Δ/2」。

关键词：欧拉示性数线性森林圈

在线全文

学校读者我要写书评

暂无评论

最大平均度不超过4的图的线性2-荫度

山东大学学报（理学版） 2018年第6期53卷 7-10页

作者：张江悦徐常青河北工业大学理学院天津300401

一个2-线性森林是指每个分支均为长至多为2的路的图。将图G的边集合划分为m个线性2-森林的最小整数m,称为图G的线性2-荫度,记作la_2(G)。确定了mad(G)≤4的图的线性2-荫度的上界,若图G为mad(G)≤4的图,则la_2(G)≤「Δ(G)/2」+5(Δ(G)≡... 详细信息

一个2-线性森林是指每个分支均为长至多为2的路的图。将图G的边集合划分为m个线性2-森林的最小整数m,称为图G的线性2-荫度,记作la_2(G)。确定了mad(G)≤4的图的线性2-荫度的上界,若图G为mad(G)≤4的图,则la_2(G)≤「Δ(G)/2」+5(Δ(G)≡1,2(mod4));la2(G)≤「Δ(G)/2」+4(Δ(G)≡0,3(mod4))。

关键词：最大平均度线性森林线性2-荫度