• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    超級-λ’無三角圖的度和充分條件

    2015-12-25 01:28:30原軍,劉愛霞
    太原科技大學學報 2015年5期

    超級-λ′無三角圖的度和充分條件

    原軍, 劉愛霞

    (太原科技大學應用科學學院,太原 030024)

    摘要:設S是連通圖G的一個邊割。 若G-S不包含孤立點,則稱S是G的一個限制邊割。 如果圖G的每個最小限制邊割恰好分離出圖G的一條邊,則稱圖G是超級限制邊連通的,簡稱超級-λ′的。 設G是一個階n≥4的連通無三角圖。 本文證明了若G中任意滿足dist(u,v)=2的點對u,v∈V(G)有d(u)+d(v)≥2+3,則G是超級-λ′的。 最后,舉例說明該結論是最好的。

    關鍵詞:限制邊連通度;超級-λ′圖;無三角圖

    收稿日期:2015-03-11

    基金項目:國家數(shù)學天元基金(11126076);國家青年科學基金(61402317);山西省青年自然科學基金(2012021001-2)

    作者簡介:原軍(1979-),男,副教授,主要研究方向為圖論及其應用。

    中圖分類號:O157.5文獻標志碼:A

    1預備知識

    互連網(wǎng)絡的可靠性是互連網(wǎng)絡設計中一個最基本而又重要的研究課題?;ミB網(wǎng)絡通常用G=(V,E)圖來模擬。此時,網(wǎng)絡的可靠性可以用圖的邊連通度和連通度來度量。為了更精確的度量互連網(wǎng)絡的可靠性,人們提出了兩種新的參數(shù)——限制邊連通度和限制連通度。不含三角形的圖,被稱作無三角圖。無三角圖在互連網(wǎng)絡設計方面有著廣泛的應用。本項目研究了無三角圖的限制邊連通度的優(yōu)化問題,證明了無三角圖是超級-λ′的度和條件。

    在文中,Shang等[7]證明了超級-λ′無三角圖的一個充分條件。

    本文證明了G是超級-λ′的一個度和條件,改進了定理1的結果。

    2主要結果及其證明

    本文證明了超級-λ′無三角圖的一個度和條件,該結論是對文獻[7]結果的推廣。下面先給出與其相關的引理。

    引理1[8]設G是一個階n≥4的連通無三角圖,若對任意滿足dist(u,v)=2的點對u,v∈V(G),有:

    與λk(G)≤ξk(G)的假設矛盾,證明完畢。

    下面給出主要的結論及其證明。

    定理2設G是一個階n≥4的連通無三角圖。若對任意滿足dist(u,v)=2的點對u,v∈V(G),有:

    證明:由引理1知G是λ′-最優(yōu)的,因此λ′(G)=ξ(G).

    ξG(uv)=min{ξG(e)∶e∈E(G[U])}

    (1)

    因為G是無三角圖,所以有Ii(u)∩Ij(v)=φ,i,j∈{1,2}.下面分兩種情況進行討論。

    情形1:I2(u)=φ且I2(v)=φ.

    由Ii(u)∩Ij(v)=φ和Ii(u)∪Ij(v)?U{u,v} 可以推出:

    與引理2矛盾。

    情形2:I2(u)和I2(v)至少有一個是空集。

    不失一般性,假設I2(u)≠φ.令w是I2(u)中任意的一個點。 由式(1),有:

    (2)

    (3)

    從而有:

    (4)

    (5)

    結合上式和式(3)~式(5)及I1(v)的定義,可推出:

    與引理2矛盾。

    由定理2,直接有以下推論。

    推論1設G是一個階n≥4的連通二部圖,若對滿足dist(u,v)=2的點對u,v∈V(G),有:

    圖1 不滿足定理1度和條件的非超級- λ′圖

    則G是超級-λ′的。

    參考文獻:

    [1]BALBUENA C,CARMONA A,F(xiàn)ABREGA J,et al.Super connectivity of bipartite digraphs and graphs[J].Discrete Mathematics,1999,197-198:61-75.

    [2]BALBUENA C,GARCIA-VAZQEZ P,MARCOTE X.Sufficient conditions forλ′-optimality in graphs with girth g[J].Graph Theory,2006,52:73-86.

    [3]HELLWIG A,VOLKMANN L.Sufficient conditions for graphs to beλ′-optimal,super-edge connected,and maximally edge-connected[J].Journal of Graph Theory,2005,48:228-246.

    [4]LI Q L,LI Q.Super edge connectivity properties of connected edge symmetric graphs[J].Networks,1999,33:147-159.

    [5]MENG J X.Optimally super-edge-connected transitive graphs[J].Discrete Mathematics,2003,260:239-248.

    [6]BONDY J A,MURTY U S R.Graph Theory with Applications[M].New York:The Macmillan Press Ltd,1976.

    [7]SHANG L,ZHANG H P.Sufficient conditions for graphs to beλ′-optimal and super -λ′[J].Networks,2007,49 (3):234-242.

    [8]YUAN J,LIU A X.Sufficient conditions forλk-optimality in triangle-free graphs[J].Discrete Mathematics,2009,310:981-987.

    Degree and Sum Conditions for Triangle-free Graphs to be

    Super Restricted Edge-connected

    YUAN Jun,LIU Ai-Xia

    (School of Applied Sciences,Taiyuan University of Science and Technology,Taiyuan 030024,China)

    Abstract:An edge cut S of a connected graph G is called as a restricted edge cut if G-S contains no isolated vertices.A graph is to be super restricted edge-connected for short super -λ′,if every minimum restricted edge cut isolates an edge.In this paper,we study the degree sum conditions for triangle-free graphs to be super restricted edge connectivity,and prove that:Let G be a connected triangle-free graph of order.If d(u)+d(v)≥2+3 for each pair vertices u,v∈V(G) with dist(u,v)=2,then G is super -λ′.Moreover, the result is demonstrated to be the best possible.

    Key words:restricted edge connectivity,super -λ′ graph,triangle-free graph

    泾源县| 盐城市| 娄底市| 卢氏县| 会东县| 谢通门县| 鹿泉市| 英吉沙县| 连山| 延长县| 喀什市| 台中县| 安平县| 阳原县| 绥棱县| 淳安县| 灵璧县| 乐陵市| 化德县| 太原市| 宁海县| 扎鲁特旗| 彩票| 眉山市| 江陵县| 赣榆县| 荃湾区| 都匀市| 永修县| 高雄县| 武宣县| 辽宁省| 合江县| 东阳市| 申扎县| 上思县| 彩票| 万载县| 金川县| 扎兰屯市| 思南县|