APP下载

包含k-树图的毁裂度条件

2016-12-21李红燕

纯粹数学与应用数学 2016年2期
关键词:子图阶数分支

李红燕

(青海民族大学数学院,青海西宁810007)

包含k-树图的毁裂度条件

李红燕

(青海民族大学数学院,青海西宁810007)

连通图G的一个k-树是指图G的一个最大度至多是k的生成树.对于连通图G来说,其毁裂度定义为

毁裂度;k-树;导出子图

1 引言

本文只考虑无环无重边的有限无向图.设图G=(V,E)是一个简单连通图,其顶点集为V(G),边集为E(G).用∆表示图G的最大度,并且用G[S]定义由图G的一个顶点集V(G)的子集S导出的子图.我们用dG(v)表示图G中一个顶点v的度,并且用NG(v)表示与顶点v邻接的点的集合.对图G的顶点集V(G)的一个非空子集S,有

连通图G的一个k-树是指图G的一个最大度不超过k的生成树.显然,如果k=2,它就是图G的一个哈密顿路;由于每一个最大度为∆的树都有一个∆-树,因此本文中连通图G不再考虑树.

设S是图G的一个非空的独立的顶点集.如果对S的任意一个子集S′都能使G-S′连通,则称S是图G的一个框架.如果|S|=k,则称S为一个k-框架.

在文献[1,2]中,作者给出了图G包含一个k-树的Ore型与Fan型条件,具体如下:

定理1.1 如果G的每一个具有k个顶点的独立集S都满足:dG(S)≥n-1,则G是一个k-树.

2013年文献[3]中给出了一个关于k-树的更强的结论,就是下面的定理1.3.

定理1.3 设G是连通图并且k(≥2)是一个整数.如果对G中的每一个k+1-框架S,都有

则G包含一个k-树.

文献[4]中介绍的图G的毁裂度是一个衡量连通图G的结构特征的重要参数,它具体定义如下:

其中ω(G-X)和m(G-X)分别表示G-X中的分支数目和最大分支的阶数.

本文中,考虑一个连通图G中的毁裂度和k-树的存在性的关系,给出了一个图有k-树的新的充分条件.

2 主要结论

设G是一个连通图,k是一个整数并且2≤k≤∆.现在,通过证明下面的定理来讨论图G的毁裂度与图G的k-树的存在性之间的关系.

定理2.1 设G(不是树)是一个连通图,如果对G的任意一个点割集X,若

则G包含k-树.

首先设H是图G包含k-树的所有导出子图中阶数最大的子图之一,A表示子图H中与V(H)之外点相邻的点集.显然,若A=∅,则G包含k-树.现在假设对于图G的任一点割集X⊂V(G)来说有

且A是非空的.下面通过反证法证明以上定理.首先证明几个有用的引理.

[1]Li Y,Zhang S,Li X.The rupture degree of graphs[J].International journal of computer mathematics,2005,82(7):793-803.

[2]李银奎,段宝荣,陈忠.完全k叉树的离散数与完整度[J].纯粹数学与应用数学,2011,27(3):1-7.

[3]李银奎,陈忠.完全k叉树的粘连度[J].纯粹数学与应用数学,2013,29(5):28-34.

[4]武燕,魏暹荪.关于图的边粘连度[J].工程数学学报,2004,21(5):34-39.

[5]魏暹荪.图论基础[M].西安:陕西师范大学出版社,1991.

[6]Bagga K S,Beineke L W,Lipman M I,et al.Edge-integrity:asurvey[J].Discrete Math.,1949,124:3-12.

[7]Piazzal B L,Roberts F S,Stueckle S K.Edge-tenacious networks[J].Networks,1995,25:7-17.

The condition of rupture degree for a graph has k tree

Li Hongyan
(Department of Mathematics,Qinghai Nationalities College,Xining810007,China)

rupture degree,k-tree,induced subgraph

O157.5

A

1008-5513(2016)02-0127-05

10.3969/j.issn.1008-5513.2016.02.003

2015-05-08.

国家自然科学基金(11561056).

李红燕(1977-),硕士,讲师,研究方向:图论.

其中ω(G-X)和m(G-X)分别表示G-X中的分支数目和最大分支的阶数.本文结合毁裂度给出连通图G包含一个k-树的充分条件;利用图的结构性质和毁裂度的关系逐步刻画并给出图G包含一个k-树的毁裂度条件.

2000MSC:05C15

猜你喜欢

子图阶数分支
一类离散时间反馈控制系统Hopf分支研究
确定有限级数解的阶数上界的一种n阶展开方法
巧分支与枝
临界完全图Ramsey数
不含3K1和K1+C4为导出子图的图色数上界∗
关于l-路和图的超欧拉性
复变函数中孤立奇点的判别
Apparent diffusion coefficient by diffusion-weighted magnetic resonance imaging as a sole biomarker for staging and prognosis of gastric cancer
基于频繁子图挖掘的数据服务Mashup推荐
关于动态电路阶数的讨论