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

李紅燕

（青海民族大學數學院，青海西寧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