临界2-棱-连通图

§1.引言 以G=(X,E)表示有限阶的简单图,其中X是G的顶点集,E是G的棱集。若x∈X,我们以G—x表示从G中删去x及与它相关联的棱所得到的图。其它未加说明的术语及记号,均见于[1]。 设G是2-棱-连通图,x是G的一个顶点。若G—x不是2-棱-连通的,则称x关于图G的2-棱-连通性是临界的,或简称x是G的一个临界点;反之,若G—x也是2-棱-连通的,则称x是G的非临界点。每一个顶点都是临界点的2-棱-连通图,称为临界2-棱-     

极小2-棱-连通图的若干性质

<正> 设G=(X,E)是有限阶的简单图,X是G的顶点集,E是G的棱集.若对于不同的x_1,x_2∈X,G中有两条连接x_1和x_2的无公共棱的初等链,则称G是2-棱-连通的.若G是2-棱-连通的,而对于任何e∈E,部分图G-e不是2-棱-连通的,则称G是极小2-棱-连通的.其他未加说明的术语或记号均见于[1].     

最大临界2-边连通图的结构

假若G是一个2-边连通图,但对G中任一点v,G\{v}不是2-边连通图,则称G为一个临界2-边连通图。具有最大边数的临界2-边连通图称为一个最大临界图。文[1]中,作者给出了p阶临界2-边连通图的边数的最大界f(p),列出了最大临界图结构的不同情况。并且他们猜测已经找出所有这类图。本文将证明他们的猜想是正确的。     

关于Δ-临界图的构造

研究了 Δ-临界图的构造 ,并且给出了一种由给定 Δ-临界图构造新的 Δ-临界图的方法     

收缩临界5-连通图的平均度

M．Kriesell证明了收缩临界5-连通图的平均度不超过24并猜想收缩临界5-连通图的平均度小于10．本文构造了一个反例证明M．Kriesell的猜想不成立并给出了收缩临界5-连通图平均度新的上界．     

应用群论方法对极小2-连通图计数

§1.引言在通讯网络和其它一些网络问题中需要研究保证一定的连通度而造价最低的网络设计问题,极小连通图的理论正是以这类实际问题为背景的.设 G=(V,E)是点集为V、边集为 E 的图,称|V|=n 为 G 的阶.若(?)v∈V,G-v 仍是连通的,则称 G 是2-连通图.一个2-连通图 G 若去掉其中任何一条边就不再是2-连通了,则称 G 是一个极小2-连通图,又称极小块.极小块早于60年代由 Dirac 和 Plummer 所研究,其后很多著作([4],[5])都对它的性质作了论述.Hobbs 于1973年用逐次加点法构造出10阶以下的全部极小块,Read 和 Hu 于1985年用压缩图法计算出12阶以下的全部极小块的数目.下面我们先给出极小块的一些性质和它的压缩图的概念.     

关于△-临界图的构造

研究了△-临界图的构造,并且给出了一种由给定△-临界图构造新的△-临界图的方法。     

临界 h 棱连通图的最大棱数及其极值图

对于给定的正整数 p 和 h,p≥h+1且 h≥4,本文给出了 p 阶临界 h棱连通图的最大棱数并且确定了所有达到最大棱数的 p 阶临界 h 棱连通图.     

临界 h 棱连通图的最大棱数及其极值图

对于给定的正整数 p 和 h,p≥h+1且 h≥4,本文给出了 p 阶临界 h棱连通图的最大棱数并且确定了所有达到最大棱数的 p 阶临界 h 棱连通图.     

关于临界h棱连通图的最大棱数及最大图的结构(Ⅰ)——每点都与h度点相邻的最大临界h棱连通或h连通图的结构

图G称为临界h棱连通(或h连通)的,如果G是h棱连通(或h连通)的,但对每个x∈V(G),G-x不再是h棱连通(或h连通)的。对h≥4,本文确定了每点都与h度点相邻的所有具有最大棱数的临界h棱连通(或h连通)图的结构。     

2-边连通3-正则非上可嵌入图的扩充（英文）

2-边连通3-正则图G是上可嵌入的当且仅当G可由图θ_1,θ_2或k_4通过一系列的M-或N-扩充得到(见[Acta Math.Appl.Sin.,Engl.Ser.,1998,14(4):337-346]).本文证明了若2-边连通3-正则图G是非上可嵌入的,则G可由图θ_3或双哑铃图通过一系列的M-或N-扩充得到.     

连通的K_{n}-残差图

m-K_{n}-残差图是由P. Erd\"{o}s, F. Harary和M. Klawe等人提出的, 当m=1时, 他们证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}- 残差图. 首先得到了m-K_{n}-残差图的重要性质, 同时证明了当n=1,2,3,4时, 连通K_{n}-残差图的最小阶和极图, 其中当n=1,2时得到唯一极图; 当n=3,4时, 证明了恰有两个不同构的极图, 从而彻底解决连通的K_{n}-残差图的最小阶和极图问题. 最后证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}-残差图.     

三圈图的极小广义和连通指数

图的广义和连通指数作为新提出的一类分子拓扑指数, 在QSPR/QSAR 中有很大的应用价值. 树图、单圈图和双圈图的极值问题已取得很多结果, 而三圈图相关问题的研究较为复杂. 限制 - 1\leqslant \alpha < 0, 对三圈图的广义和连通指数进行了研究. 通过对三圈图的分析, 构造了一种图的变换, 指出在三圈图中广义和连通指 数的极小值必由其中的七种类型图取得. 然后通过悬挂边的变换, 最终得到三圈图广义和连通指 数的极小值并刻画了唯一的极图.     

6连通图中的可收缩边

Kriesell(2001年)猜想：如果κ连通图中任意两个相邻顶点的度的和至少是2[5κ/4]-1则图中有κ-可收缩边．本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点，由此推出该猜想对κ=6成立。     

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,     

Hamiltonian[k,k+1]-因子

本文考虑n/2-临界图中Hamiltonian[k,k+1]-因子的存在性。Hamiltonian[k,k+1]-因子是指包含Hamiltonian圈的[k,k+1]-因子;给定阶数为n的简单图G,若δ(G)≥n/2而δ(G\e)相似文献   

关于2-连通“几乎正则”图的Jackson猜想

Bill Jackson在[1]中作为猜想,提出了一个2-连通“几乎正则”(almost regular)图存在Hamilton圈的充分条件:“如果G是一个次序列为(k,k,…,k,k+1,k+1)的2-连通图,其顶点数不大于3k+2时,G是Hamilton图.本文举例说明     

连通的三重K_{n}-残差图

Erd\"{o}s P, Harary F和Klawe M研究了K_{n}-残差图, 并对连通的m-K_{n}-残差图提出了一些结论和猜想. 利用容斥原理以及集合的运算性质等方法, 研究了连通的3-K_{n}-残差图, 得到当顶点最小度为n时, 3-K_{n}-残差图最小阶的计算公式以及相应的唯一极图. 当n=2时, 得到最小阶为11以及相应的极图; 当n=3时, 得到最小阶为20并找到两个不同构的极图, 不满足Erd\"{o}s等提出的结论; 当$=4时, 得到最小阶为22及相应的极图; 当n=8, 可以找到两个不同构的3-K_{8_{}}-残差图, 不满足Erd\"{o}s等提出的结论; 最后证明了当n=9,10时, 最小阶分别为48和52以及相应的唯一极图, 验证了Erd\"{o}s等在文献~(Residually-complete graphs [J].Annals of Discrete Mathematics, 1980, 6: 117-123) 中提出的结论.     

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)。并且给出了达到最大边数的极值图.     

临界κ连通图中的点度数

如果在—个κ连通图G中删掉任意一个顶点后得到的图都不再是κ连通,则称G为临界κ连通.Chartrand,Kaugars和Lick证明了每一个临界κ连通图(κ≥2)都含有一个度数小于(3κ-1)/2的顶点.Hamidoune进一步证明了每一个临界k连通图都至少含有两个这样的顶点,并且这一下界是最优的.在本文中,我们证明如果一个临界κ连通图恰好含有两个度数小于(3κ-1)/2的顶点,则这两个顶点的度数一定是κ.