• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2016-12-21 08:24:42李紅燕
      關(guān)鍵詞:子圖階數(shù)分支

      李紅燕

      (青海民族大學(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

      猜你喜歡
      子圖階數(shù)分支
      關(guān)于無窮小階數(shù)的幾點(diǎn)注記
      確定有限級數(shù)解的階數(shù)上界的一種n階展開方法
      巧分支與枝
      臨界完全圖Ramsey數(shù)
      一類擬齊次多項(xiàng)式中心的極限環(huán)分支
      基于頻繁子圖挖掘的數(shù)據(jù)服務(wù)Mashup推薦
      一種新的多址信道有效階數(shù)估計(jì)算法*
      關(guān)于動(dòng)態(tài)電路階數(shù)的討論
      不含2K1+K2和C4作為導(dǎo)出子圖的圖的色數(shù)
      生成分支q-矩陣的零流出性
      城口县| 理塘县| 丰台区| 拉孜县| 潼关县| 明溪县| 成武县| 西贡区| 内黄县| 微博| 旅游| 会东县| 丰原市| 莱西市| 乐业县| 札达县| 临猗县| 庐江县| 林甸县| 冷水江市| 通渭县| 康平县| 英山县| 肇源县| 山丹县| 纳雍县| 湄潭县| 合山市| 东乡族自治县| 庆安县| 三穗县| 安乡县| 邵武市| 贡嘎县| 井陉县| 乐昌市| 交口县| 商洛市| 清镇市| 玉林市| 临江市|