p阶临界2-边连通图的最大边数

设G=(V,E)是2-边连通图,若对每个点v∈V,G-v不是2-边连通图,则称G是临界2-边连通图. 本文证明了p阶临界2-边连通图的最大边数是 7, P=6; (1/8)(P~2+4p) p=0(mod 4); f(p)= (1/8)(P~2+2p+13) p=1(mod 4); (1/8)(P~2+28) p=(2mod 4),p≠6 (1/8)(P~2+2p+9) p=3(mod 4)。并且给出了达到最大边数的极值图.     

n 阶临界3-边连通图的最大边数

本文中未经说明的术语和记号采自[2].设 G=(V,E)是一个简单图。G 的顶点数记作 n(G),边数记作 m(G),即 n(G)=|V|,m(G)=|E|.假设 G 是3-边连通图.G 的顶点 v(?)V 称为 G 的临界点,如果 G-v 不是3-边连通的;否则称为 G 的非临界点.如果每个 v(?)V 都是 G 临界点,则称 G 是临界3-边连通图.临界3-边连通图类记作 A,A_n 是 A 中所有 n 阶图的集合.假设 G(?)A,则对每个 v∈A,     

最大匹配数的一个问题

一、本文仅讨论简单图。图G的1-因子数记为F(G)。 f(G)记使如下事实正确的最大的K:“假如G是一个n-连通图且G有1-因子,则G至少有k个1-因子”。包含G的所有的点,且每个点的度为0或1的G的子图叫G的一个匹配M,有最大的边数的匹配称为最大匹配。假如匹配M的一个点v的度为0,称v为在M里的分离点。以M(G)表示G的最大匹配的集合。假如图G的一个点v所关连的每一条边都属于G的一个最大匹配,称点v被M(G)完全覆盖。     

色指数临界图的一些新结论

图的边色数是指对图的边进行染色使得任意两相邻边染不同的颜色所需要的最少的颜色数.1965年,Vizing证明了任意最大度为△的图的边色数或者是△或者是△+1.若G是连通的,且G的每一条边e均有X′(G-e)相似文献   

2-边连通图的线图的P3因子

如果图G有一个生成子图使得这个生成子图的每一个分支都是3个点的路，则称G有P3-因子．本文证明了对任何一个2-边连通图G，只要G的边数能被3整除，则G的线图就有P3-因子。     

K1,4-受限图的路可扩性

图G中同构于K1,p的子图叫G的p-爪(p3).如果G中任意一个p-爪中1度顶点之间边的数目p-2,则称G为K1,p-受限图,它是无爪图(p=3时)的推广.本文证明了:连通、局部3-连通的K1,4-受限图是路可扩的.     

图是超限制性边连通的充分条件

设G=（V,E）是连通图.边集S E是一个限制性边割,如果G-S是不连通的且G—S的每个分支至少有两个点.G的限制性连通度λ＇（G）是G的一个最小限制性边割的基数.G是λ＇-连通的,如果G存在限制性边割.G是λ＇-最优的,如果λ＇（G）=ζ（G）,其中ζ（G）是min{d（x）＋d（y）-2：xy是G的一条边}.进一步,如果每个最小的限制性边割都孤立一条边,则称G是超限制性边连通的或是超-λ＇.G的逆度R（G）=∑_（v∈V） 1/d（v）,其中d（v）是点v的度数.我们证明了G是λ＇-连通的且不含三角形,如果R（G）≤2＋1/ζ-ζ/（（2δ-2）（2δ-3））＋（n-2δ-ζ＋2）/（（n-2δ＋1）（n-2δ＋2））,则G是超-λ＇.     

K1,p-受限图

图G中同构于Ki,p的子图叫G的p-爪(P≥3)．如果G中任意一个p-爪中1度顶点之间边(在G中的边)的数目≥P-2,则称G为K1,p-受限图,它是无爪图的推广．本文证明了连通、局部2-连通的K1,4-受限图是完全圈可扩的．     

无爪图泛圈性的邻域并条件

证明了,若G是一个p-阶3-连通无爪图,p≠10,11,15,并对G中任意两个不相邻的点u和v,满足|N(u)∪N(v)|≥(p-1)/2,则G是泛圈图.     

重图的均匀边染色

图G的一个边染色称为是均匀的,如果对G的每个顶点v,与v关联的染任意两种颜色的边数至多相差一,我们给出了重图均匀边染色的一个充分条件。     

三类特殊图的(强)彩虹连通数

如果一条路上的任意两条边均染不同颜色,则称这条路是彩虹路.如果在图G的任意两个顶点间都存在一条彩虹路,就称图G是彩虹连通的.对于一个连通图G,保证它是彩虹连通所需的最少颜色数就是G的彩虹连通数,记为rc(G).一条彩虹(u,v)-测地线是指图G中一条长度为d(u,v)的彩虹(u,v)-路,其中d(u,v)表示图G中u,v两点的距离.如果在图G的任意两个顶点间都存在一条彩虹测地线,就称图G是强彩虹连通的.对于一个连通图G,保证它是强彩虹连通所需的最少颜色数就是G的强彩虹连通数,记为src(G).这篇文章主要研究了三类特殊图的(强)彩虹连通数,并得到了它的精确值.     

超级限制边连通二部图的充分条件

设S是连通图G的一个边割.若G-S不包含孤立点,则称S是G的一个限制边割.图G的最小限制边割的边数称为G的限制边连通度,记为λ'(G).如果图G的限制边连通度等于其最小边度,则称图G是最优限制边连通的,简称λ'-最优的.进一步,如果图G的每个最小限制边割恰好分离出图G的一条边,则称图G是超级限制边连通的,简称超级-λ'的.设G是一个最小度δ(G)≥2的n≥4阶二部图,ξ(G)是G的最小边度.本文证明了(a)若ξ(G)≥(n/2-2)(1+1/δ(G)-1),则G是λ'-最优的;(b)若ξ(G)>(n/2-2)(1+1/δ(G)-1),则G是超级-λ'的,除非图G是K2,n-2,n≥6或是Cartesian积图Kn/4,n/4×K2,其中n≥8且n整除4.最后,论文举例说明该结果是最好可能的.     

连通的欧拉生成子图

本文证明了:若 G 是一个 p 个顶点的、2-边-连通简单图,其边数,q≥((p-4)/2)+7.则除 K_(2,5)外,G 有连通的欧拉生成子图.当 q=((p-4)/4)+6和 k(G)=2时,本文给出了全部6个极图.     

3连通平面图的可去边数

设e是3连通图G的一边。如果G-e是某个3连通图的剖分,则称e是G的可去边。用v表示G的顶点数,本文证明了当v≥6时,3连通平面图G的可去边数的下界是v+4/2,此下界是可以达到的。     

关于Sumner-Blitch猜想的一个注记

设G是一个图。G的最小度，连通度，控制数，独立控制数和独立数分别用δ，k，γ，i和α表示，图G是3－γ-临界的，如果γ=3，而且G增加任一条边所得的图的控制数为2.Sumner和Blitch猜想：任意连通的3－γ临界图满足i=3，本文证明了如果G是使α＝k 1≤δ的连通3－γ-临界图，那么Sumner-Blitch猜想成立。     

超欧拉图、可折叠图及匹配

如果图G有一个生成的欧拉子图,则称G是超欧拉图.用α′(G)表示G中最大独立的边的数目.本文证明了:若G是一个2-边连通简单图且α′(G)≤2,则G要么是可折叠图,要么存在G的某个连通子图H,使得对某个正整数t≥2,约化图G/H是K_(2.t.)推广了[Lai H J,Yan H.Supereulerian graphs and matchings.Appl.Math.Lett.,2011,24:1867-1869]中的一个主要结果.并且证明了上述文献中提出的一个猜想:3一边连通且α′(G)≤5的简单图是超欧拉图当且仅当它不可收缩成Petersen图.     

点可迁图的限制边连通性

3限制边割是连通图的一个边割, 它将此图分离成阶不小于3的连通分支. 图G的最小3限制边割所含的边数称为此图的3限制边连通度, 记作λ\-3(G). 它以图G的3阶连通点导出 子图的余边界的最小基数ξ_3(G)为上界. 如果λ_3(G)=ξ_3(G), 则称图G是极大3限制边连通的 . 已知在某种程度上,3限制边连通度较大的网络有较好的可靠性. 作者在文中证明: 如果k正则连通点可迁图的 围长至少是5, 那么它是是极大3限制边连通的.     

边覆盖临界图的一些性质

设G是一个简单图,其顶点集为V(G)而边集为E(G),S∈E(G)称为 G的一个覆盖,如果由S导出的子图为G的一个生成子图. G的边覆盖色数χ'c(G)是E(G,)所能划分成的最大边覆盖数.已知δ-1 ≤χ'c(G)≤δ,由此将χ'c(G)=δ的图称为CI类图,否则称为CII类图.若G是连通CII类图,且G不是完全图,对任意的u,u∈V(G),e=uv( )E(G),都有χ'c(G+e)＞χ'c(G)成立,则称G为边覆盖临界的.本文研究了边覆盖临界图的一些性质.即若G为边覆盖临界图,则对任意的u,v∈V(G),若e=uv( )E(G),总存在w∈{u,v},有d(w)≤2δ-2,且w至少与max{d(w)-δ+1,3d(w)-4δ+4}个最小度顶点相邻.     

K_(1,4)-受限图的最长路

图G中同构于K_(1,p)的子图叫G的p-爪(p≥3).如果G中任意一个p-爪中1度顶点之间边(在G中的边)的数目≥p-2,则称G为K(1,p-)-受限图,它是无爪图(p=3)时的推广.本文证明了:连通的K_(1,4-)受限图G,若|G|≥7,则G有Hamilton路或有长至少为2δ+2的路.     

关于（ξ,k）—临界图

设G为连通图,且ξ（G）=k≥1,若对G中任意边e,均有ξ（G\e）=k-1,则称G为(ξ,k)-临界图。本文刻划了ξ-1-临界图的若干性质,给出了一个图为ξ-1-临界图的一些充分或必要条件,以及一些ξ-1-临界图类。