若干图的伴随分解及色等价性

设Pm和Cm分别表示具有m个顶点的路和圈,G是任意的r阶连通图,设m是正奇数,把路Pm的标号为奇数的2-1(m+1)个顶点分别与2-1(m+1)G每个分支的第i个顶点Vi重迭后所得到的图记为ρG(i)m+2-1(m+1)r。运用图的伴随多项式的性质,首先给出了一类图簇ρG(i)(2 m+2)+((m+1)r的伴随多项式。进而令m=2t-1 q-1,λn=(2nq-1)+2n-1 qr,在讨论上述图的伴随多项式的基础上,我们证明了图ρG(i)λt和ρG(i)λt∪(t-1)K1的伴随多项式的因式分解定理,进而证明了这些图类的补图的色等价性。     

超能整循环图的构造

图G的能量E(G)定义为图的特征值的绝对值之和.如果图G的能量E(G)2n-2,则具有n个顶点的图G称为超能图;如果它是循环群上的Cayley图,即其邻接矩阵是一个循环矩阵,则称其为循环图.整循环图是指循环图的特征值全为整数.基于Ramanujans和,利用Euler函数和Mobius函数,讨论了整循环图的超能性.同时,利用Cartesian积图给出了一个构造超能整循环图的方法.     

变换图G++-的超力连通性

对于图G,一般有λ(G)≤δ(G).如果λ(G)=δ(G),称图G是较大边连通的.如果G的每一个最小边割只能分离G的一个孤立点.称图G是超边连通的.本文证明了几乎所有的有限图G,其变换图G -都是超边连通的.     

一类一致最优完全多部图

以(n,m)表示具有n个顶点m条边的图的集合.假设图G的边可靠,而顶点可靠的独立概率为p,若对于所有1 p∈(0,1),图G均为(n,m)中的最可靠图,则称G为一致最优图.本文证明了完全k-部图K(b,(b+2)k 1)在其图类中是一致最优的,而当i>3时,完全k-部图K(b,(b+2)k 2,b+i)在其图类中不是一致最优的.     

冠图G1. Km1,m2的邻接谱

给定简单图G1和G2,G1的顶点标记为v1,v2………,vn1.图G1和G2的冠图G1.G2被定义为取n1个G2的拷贝,然后连接vi与相应的G2的第i个拷贝中的每一个点(i=1,2………,n1)所得到的图.在文献[2]中,对连通图G1和任一正则图G2,S.Barik,S.Pati和B.K.Sarma给出了G1.G2的邻接谱的完整的表达式.继文献[2]的工作进一步考虑当G2是非正则图时冠图G1.G2的邻接谱.本文完全确定了冠图G1.Km1,m2的邻接谱,其中Km1,m2是完全二部图.     

双圈图的极小广义Randi指标(英文)

图G的广义R and i′c指标定义为Rα(G)=∑uv∈E(G)Rα(uv)=∑uv∈E(G)(d(u)d(v))α,其中d(u)是顶点u的度,α是实数.胡玉梅等给出了树的广义R and i′c指标的下界及其极图,吴宝音都仍等基本上给出了单圈图的广义R and i′c指标的下界及其极图.本文讨论双圈图G的R and i′c指标.利用吴宝音都仍的方法得到:当α>0时,Rα(G)≥6.6α (n-5).4α(这里n=G).同时确定了这样的极图.     

图中存在[a,b]-因子的一个充分条件

设G是一简单连通图,其联结数定义为b(G)=min{|NG(X)|/|X|:■≠X■V(G),N_G(X)≠V(G)}.文章通过图G的联结数刻画了其中存在[a,b]-因子的一个充分条件.     

关于边色数GOLDBERG问题的注记

本短文指出度数为3、边色数为4的图的边数 e(G):e(G)≥[11v(G)-3]/8是否为真的图,指的是临界图.其中 v(G)表示 G 的点数.     

全变换图G~(xyz)

设G=(V (G),E(G))是一个简单无向图, x,y,z是取+或-的3个变量.图G的变换图G~(xyz)是以V (G)∪E(G)为其顶点集,且对任意的α,β∈V (G)∪E(G),α,β相邻当且仅当以下条件之一成立:(i)α,β∈V (G), x=+时当且仅当α和β在图G中相邻, x=-时当且仅当α和β在图G中不相邻;(ii)α,β∈E(G), y=+时当且仅当α和β在图G中相邻,y=-时当且仅当α和β在图G中不相邻;(iii)α∈v(G),β∈E(G), z=+时当且仅当α和β在图G中关联,z=-时当且仅当α和β在图G中不关联.变换图G~(xyz)作为全图的变形是由吴和孟在2001年首次提出的.自那时起,大量的工作致力于研究这些变换图的各种性质.本文主要是对变换图G~(xyz)的已知结论与未解决的问题进行综述.     

几类亚随意匹配图

David P.Sumner在[1]中引入了随意匹配图的概念;如果图G的任意匹配都能扩充为G的完备匹配,则称G为随意匹配图.他证明了当且仅当G为     

超连通图的充分条件（英文）

设G是一个连通图.图的连通度κ(G)存在一个最小正整数k,使得FV,|F|=k且G-F不连通或是一个平凡图.如果每一个最小点割都孤立G的一个点,则图G是超连通的或超-κ的.定义没有孤立点的图G的逆度为R(G)=∑v∈V1/d(v).得到:设n阶连通图G,最小度为δ,若R(G)1+2/(δ+1)+(n-2δ-1)/((n-1)(n-3)),则G是超-κ的.     

与边控制相关的两类图

在图G中,如果存在一个边集D,使得不在D中的每一条边都与D中的某条边关联,则称D为G的边控制集.在G的所有边控制集中,包含边数最少的称为最小边控制集,其包含的边数称为边控制数,记为γ′(G).在一个图中,我们研究了加边或去边对该图边控制数的影响.一个图称为边控制临界图(边控制极小图)如果任意增加(去除)一条边都会使边控制数下降.在本文中,我们研究了这两类图的性质,并分别刻画了3-边控制临界图和3-点控制极小图.     

列表双临界图（英文）

G是k-可着色的连通图,如果对于G中的所有边uv,都有G-u-v是(k-2)-可着色的,则称图G是双临界图.由Erdo?s和Lova′sz提出了一个长期未能解决的猜想:完全图是唯一的双临界图[1].连通图G称为边双临界图,如果G中包含多对不相邻的边,并且对于任意一对不相邻的边e1,e2,都有χ(G-e1-e2)=χ(G)-2,其中χ(G)表示图G的色数.Kawarabayashi等人[2]及后来的Lattanzio[3]证明了完全图是唯一的边双临界图.文章证明了在图G中,对于任意的两个点u,v∈V(G),如果ch(G-u-v)=ch(G)-2,则图G是完全图,其中ch(G)表示G的选择数,还证明了完全图是唯一的列表双临界图.     

偶匹配可扩图的度和连通度条件(英文)

称图G是偶匹配可扩的,是指G的每一个导出二部偶子图的任意完美匹配都可以扩充为G的一个完美匹配.记δk(G)为一个k元独立集的最小度和,κ(G)为图G的连通度.在本文章中,给出了2n个顶点的图G满足κ(G)≥2(n/2)+1,和δ3(G) ≥ 3(3n/2)-2.那么G是偶匹配可扩的.并给出例子说明两个条件都是紧的.     

Ramsey定理的一种推广

Ramsey定理指出:对于任何一个正整数k,存在一个最小的正整数r(k,k),使得对任意一个至少有r(k,k)个顶点的图G,它或者有k个顶点的完全子图Kk,或者有k个顶点是独立集.由此定理易得:设G是顶点数n>r(k,k)的简单图,其边数e>0,且G的所有k阶导出子图的边数相等,那么G是完全图.并给出上述结论的推广:设G是n(n≥4)阶简单图,其边数e>0,对某个给定的自然数k(2≤k≤n-2),若G的所有k阶导出子图的边数相等,则G是完全图.     

广义Mycielskian图的连通度(英文)

Mycieski定义了一个图的运算即把一个图G变换为一个称为G的Mycielskian图的新图μ(G).广义Mycielskian图μm(G)(m≥0)是图的Mycielskian图的一个自然推广.本文证明对任意非平凡连通图G有κ(μm(G))=min{δ(G)+1,(m+1)κ(G)+1},而且对于m,i≥1,λ(μm(G))=λ(G)+i当且仅当δ(G)=λ(G)+i 1,其中κ(G),λ(G)和δ(G)分别为图G的连通度,边连通度和最小度.     

二面体群的双凯莱图的匹配可扩性（英文）

令G为有限群,S为G的非空有限子集,G关于S的双凯莱图BC(G,S)是一个二部图,其顶点集是G×{0,1},边集是{(g,0)(sg,1)|g∈G,s∈S}.若有完美匹配的连通图Γ至少有2n+2个顶点,且每一个大小为n的匹配都可以扩充为一个完美匹配,则称此完美匹配的连通图Γ是n-可扩的,并对二面体群的双凯莱的2-可扩性进行了刻画.     

关于直积图的坚韧度和边坚韧度的注记（英文）

图G的坚韧度t(G)定义为:对非完全图是t(G)=min{|S|/ω(G-S)|SV(G),ω(G-S)≥2},而对完全图是∞,其中ω(G-S)表示G-S的连通分支数.边坚韧度定义为t′(G)=min{|X|/ω(G-X)-1|X是G的边割集}.在本文中,我们给出了完全图和圈的直积图的坚韧度,并且提供了完全图和正则图类的直积图的边坚韧度公式.     

路图P3(G)的色数

设G是一个图,G的路图P3(G)的顶点集是G中所有三个顶点的路P3, 当G中的两个P3路形成P4路或C3圈时,在P3(G)中它们所代表的两个顶点相邻. 在这篇文章中,我们得到对于一个无三角形的图G, χ(P3(G))≤β(G),其中β(G)表G的点覆盖数. 对于顶点数至少为3的连通图G,χ(P3(G))≤2当且仅当G是二部图, 并且χ(P3(G))=1当且仅当 G是星图. 对于K4的剖分图G,2≤χ(P3(G))≤3. 对于系列平行图和外可平面图G,χ(P3(G))≤3.     

化学单圈图的原子键连通性指数

图G的原子键连通性指数的定义如下:ABC(G)=∑uv∈E(G)((du+dv-2)dudv)(1/2).其中du、dv分别表示图G的边uv的2个端点u、v的度数.ABC指数已被证实为研究烷烃的稳定性以及环烷烃的应变能提供了一个很好的模型.讨论了n阶化学单圈图,给出了其ABC指数的可达的下界及其相应的极图