禁用{B_(k+1),K_(2,l+1)}的图α谱半径极值问题

令K_(s,t)是完全二部图,K_(n)是完全图,其中s,t和n是正整数.令B_(4,l)是由l个共享一条边的K_(4)构成的图,B_(l)是由B_(4,l)的所有生成子图构成的集合.本文研究了禁用{B_(k+1),K_(2,l+1)}的图的最大α-谱半径问题.利用B_(k+1)和K_(2,l+1)的结构特点以及基本不等式,在具有n个顶点、最大度为Δ且禁用{B_(k+1),K_(2,l+1)}的连通图中,获得了α-谱半径的上界,且刻画了达到上界的极值图.相应地,在具有n个顶点、最大度为Δ且禁用B_(k+1)或K_(2,l+1)的连通图中,得到了α-谱半径的上界.

Turán定理在数学竞赛中的应用

Turán定理是图论中的基本定理,是极值图论的开端.以近几年的国内外竞赛试题为例,介绍Turán定理在数学竞赛题中的应用及解决处理问题时的常用方法,以提高竞赛学生分析、解决相关问题的能力.

关于Frankl-Füredi猜想的一个结果

Frankl和Füredi猜测在所有边数为m的r-图中,由N(r)中Colex序最小的m个元素组成的r-图具有最大的拉格朗日极值.本文证明,对于边数为m的3-图,当[(t-1)/3]≤m≤[t-1/3]+[(t-2)/2]且t≤8时,这一猜想成立.

一些极值图问题的谱条件综述

这篇综述分为两个方面.首先,我们总结了图论中的Turan型问题的谱极值结论的最新进展.更准确地说,关于各种图的邻接谱半径和无符号拉普拉斯谱半径,我们总结了它们的谱版本的Turán型函数.例如,完全图、色数至少为3的一般图、完全二部图、奇圈、偶圈、色临界图和相交三角形图.第二个目标是总结一些最近的关于图性质的谱条件.通过一种统一的方法,基于邻接谱半径和无符号拉普拉斯谱半径,我们给出了一些充分条件,使得该图成为哈密顿图、k-哈密顿图、k-边哈密顿图、可迹图、k-路径可覆盖图、k-连通图、k-边连通图、哈密顿连通图、完美匹配图和β-亏量图.

不含三圈的双圈图的谱半径

Nikiforov等人最近将图谱研究与极值图论相结合,提出了谱Turán型问题：给定一个图F,设G是一个不含子图与F同构的n阶图,那么图G的谱半径至多是多少？双圈图是边数等于顶点数加1的简单连通图。近期,部分学者对双圈图的谱半径进行了研究,确定了双圈图谱半径的第1-10大值和相应的极图。受此启发,研究了不含三圈的双圈图,确定不含三圈的双圈图的谱半径的上界,并刻画了相应的极图。

蕴含W_5可图序列的最小度和

Gould,Jacobson和Lehel考虑了下述经典Tur偄n型极值问题的变形:对于给定的图H,确定最小的正偶数σ(H,n),使得对于每一个n项可图序列π=(d1,d2,…,dn),当σ(π)=d1+d2+…+dn≥σ(H,n)时,π有一个实现G包含H作为可图的.本文确定了当n≥11时,σ(W5,n)之值,其中Wr是r个顶点的轮图.

蕴含K_(1,1,3)的正可图序列的最小度和

Gould R J等人考虑了下述经典Turan型极值问题的变形:对于给定的图H,确定最小的正偶数σ(H,n),使得对于每一个n项正可图序列π=(d1,d2,…,dn),当σ(π)=d1+d2+…+dn≥σ(H,n)时,π有一个实现G以H作为子图.本文完全确定了σ(K1,1,3,n)之值,其中Kr,s,t是r×s×t完全三部图.