包含k-樹圖的毀裂度條件

李紅燕

（青海民族大學(xué)數(shù)學(xué)院，青海西寧810007）

包含k-樹圖的毀裂度條件

李紅燕

（青海民族大學(xué)數(shù)學(xué)院，青海西寧810007）

連通圖G的一個(gè)k-樹是指圖G的一個(gè)最大度至多是k的生成樹.對于連通圖G來說，其毀裂度定義為

毀裂度；k-樹；導(dǎo)出子圖

1 引言

本文只考慮無環(huán)無重邊的有限無向圖.設(shè)圖G=（V，E）是一個(gè)簡單連通圖，其頂點(diǎn)集為V（G），邊集為E（G）.用?表示圖G的最大度，并且用G［S］定義由圖G的一個(gè)頂點(diǎn)集V（G）的子集S導(dǎo)出的子圖.我們用dG（v）表示圖G中一個(gè)頂點(diǎn)v的度，并且用NG（v）表示與頂點(diǎn)v鄰接的點(diǎn)的集合.對圖G的頂點(diǎn)集V（G）的一個(gè)非空子集S，有

連通圖G的一個(gè)k-樹是指圖G的一個(gè)最大度不超過k的生成樹.顯然，如果k=2，它就是圖G的一個(gè)哈密頓路；由于每一個(gè)最大度為?的樹都有一個(gè)?-樹，因此本文中連通圖G不再考慮樹.

設(shè)S是圖G的一個(gè)非空的獨(dú)立的頂點(diǎn)集.如果對S的任意一個(gè)子集S′都能使G-S′連通，則稱S是圖G的一個(gè)框架.如果|S|=k，則稱S為一個(gè)k-框架.

在文獻(xiàn)［1，2］中，作者給出了圖G包含一個(gè)k-樹的Ore型與Fan型條件，具體如下：

定理1.1 如果G的每一個(gè)具有k個(gè)頂點(diǎn)的獨(dú)立集S都滿足：dG（S）≥n-1，則G是一個(gè)k-樹.

2013年文獻(xiàn)［3］中給出了一個(gè)關(guān)于k-樹的更強(qiáng)的結(jié)論，就是下面的定理1.3.

定理1.3 設(shè)G是連通圖并且k（≥2）是一個(gè)整數(shù).如果對G中的每一個(gè)k+1-框架S，都有

則G包含一個(gè)k-樹.

文獻(xiàn)［4］中介紹的圖G的毀裂度是一個(gè)衡量連通圖G的結(jié)構(gòu)特征的重要參數(shù)，它具體定義如下：

其中ω（G-X）和m（G-X）分別表示G-X中的分支數(shù)目和最大分支的階數(shù).

本文中，考慮一個(gè)連通圖G中的毀裂度和k-樹的存在性的關(guān)系，給出了一個(gè)圖有k-樹的新的充分條件.

2 主要結(jié)論

設(shè)G是一個(gè)連通圖，k是一個(gè)整數(shù)并且2≤k≤?.現(xiàn)在，通過證明下面的定理來討論圖G的毀裂度與圖G的k-樹的存在性之間的關(guān)系.

定理2.1 設(shè)G（不是樹）是一個(gè)連通圖，如果對G的任意一個(gè)點(diǎn)割集X，若

則G包含k-樹.

首先設(shè)H是圖G包含k-樹的所有導(dǎo)出子圖中階數(shù)最大的子圖之一，A表示子圖H中與V（H）之外點(diǎn)相鄰的點(diǎn)集.顯然，若A=?，則G包含k-樹.現(xiàn)在假設(shè)對于圖G的任一點(diǎn)割集X?V（G）來說有

且A是非空的.下面通過反證法證明以上定理.首先證明幾個(gè)有用的引理.

［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叉樹的離散數(shù)與完整度［J］.純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2011，27（3）：1-7.

［3］李銀奎，陳忠.完全k叉樹的粘連度［J］.純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2013，29（5）：28-34.

［4］武燕，魏暹蓀.關(guān)于圖的邊粘連度［J］.工程數(shù)學(xué)學(xué)報(bào)，2004，21（5）：34-39.

［5］魏暹蓀.圖論基礎(chǔ)［M］.西安：陜西師范大學(xué)出版社，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.

國家自然科學(xué)基金（11561056）.

李紅燕（1977-），碩士，講師，研究方向：圖論.

其中ω（G-X）和m（G-X）分別表示G-X中的分支數(shù)目和最大分支的階數(shù).本文結(jié)合毀裂度給出連通圖G包含一個(gè)k-樹的充分條件；利用圖的結(jié)構(gòu)性質(zhì)和毀裂度的關(guān)系逐步刻畫并給出圖G包含一個(gè)k-樹的毀裂度條件.

2000MSC:05C15