陸 鋒

(湄洲灣職業(yè)技術學院 福建莆田 351254)

幾類帶寬極圖

陸 鋒

(湄洲灣職業(yè)技術學院 福建莆田 351254)

本文主要在e(p,p-2)的所有極圖的研究的基礎上，進一步考慮帶寬為p-3的圖的補圖結(jié)構，從而確定了e(p,p-3)(p≤9)以及e(p,p-4)(p≤8)的所有極圖，對已有的結(jié)論進一步做了推廣.

圖，帶寬，極圖

圖論是數(shù)學的一個分支，特別是組合數(shù)學的重要分支之一.其廣闊的應用領域涵蓋了人類學、計算機科學、化學、環(huán)境保護、流體動力學、電信領域等等.在實際生活、生產(chǎn)和科學研究中，有許多問題可以利用圖論的方法來解決.在圖論的研究課題中，有一類相當有趣的問題，那就是圖的帶寬問題.由于它在數(shù)值計算、編碼理論、網(wǎng)絡設計及結(jié)構力學分析、超大規(guī)模集成電路(VLSL)布線設計等方面的實際應用，引起了國內(nèi)外學者的關注.圖的帶寬問題是一個既有廣泛的實際應用背景，又是極有趣味的數(shù)學課題.筆者首先介紹一些與帶寬極圖相關的理論成果.定義帶寬極圖如下：

記e(p,B)=min{‖G‖∶|G|=p,B(G)=B,G，其中}，|G|,‖G‖分別表示圖的頂點數(shù)和邊數(shù).達到此最小值的圖就稱為e(p,B)的一個極圖.

1 準備知識

定理1.8[6]設 ，則：

2 e(p,p-3)(p≤9)的所有極圖

文獻[6]考慮了e(p,p-2)的極圖基礎上，本文筆者主要考慮為e(p,p-3)的極圖問題，結(jié)合已有結(jié)論確定e(p,p-3)的所有極圖，對文獻[7]的結(jié)論進一步作了推廣.

定理1.1易得，當p≤6時e(p,p-3)的所有極圖.當p=4時，e(4,1)=3，p4是e(4,1)的唯一極圖.當p=5時，e(5,2)=4，圖1所示為e(5,2)僅有的兩個極圖.當p=6時，e(6,3)=5，k1,5是e(6,3)的唯一極圖.

圖1

文章[7]通過考慮e(7,4)極圖的補圖結(jié)構性質(zhì)，確定了e(7,4)的所有極圖是下列三種圖形的補圖(即圖2中(1)(2)(3)的補圖)

圖2

現(xiàn)在筆者考慮當p=8時，即e(8,5)的極圖及其構造的形式.首先筆者考慮e(8,5)的極圖的補圖，為此先給出如下命題：

對不含H3的圖，可以分兩種情況討論(1)圖中不含C4；(2)圖中含C4.

下面對以上兩種情況進行討論：

(1)如果圖G不含有C4的圖的性質(zhì)，則在文獻[8]給出不含C4且邊數(shù)最多的連通圖情形如下定理：

引理[8]設G頂點數(shù)為p、不含C4、邊數(shù)最多的連通圖，則邊數(shù)‖G‖(1≤p≤21)如表1所示:

表1

(2)現(xiàn)在考慮如果圖G含有C4但不含有H3的情況.本文僅考慮頂點數(shù)不大于8的連通圖，由于點數(shù)較小，可以確定頂點數(shù)8的邊數(shù)最多的連通圖G的，其中：C4?G、H3?G、Δ(G)≤6.按照圖G含有 但不含 的性質(zhì)對 有如下的導出子圖(如圖3)的可能性進行討論(同時含有不止一種情況下，本文就考慮邊數(shù)盡可能多的導出子圖)

圖3 F含有C4但不含H3的性質(zhì)導出子圖

當p=8時，且滿足下列條件C4?G、H3?G、Δ(G)≤6.則G僅有如圖4所示的4種形式.

圖4 p=8時， 符合條件圖

由以上可得如下性質(zhì)：當頂點數(shù)p=8時，邊數(shù)最多的連通圖G，其中C4?G、H3?G、Δ(G)≤6，則‖G‖=13.和比較表1，可見當p=8時，對于相同頂點數(shù)p的圖G，含有子圖C4的圖邊數(shù)更多，因此，就只需考慮含C4的情況.

下面本文考慮e(8,5)的所有極圖：首先，尋找滿足下述條件的頂點數(shù)為8的邊數(shù)最多的圖G，G滿足d(v)≤6，?v∈V(G)，含有p4?G，H3?G.令Gm為圖G中頂點數(shù)最多的連通分支.綜上滿足條件P4?G、H3?G、Δ(G)≤6的圖 的邊數(shù)為13.僅有如下圖5的三種形式.由命題2.1知e(8,5)的所有極圖只有5種分別為如圖5所示的圖形.

圖5 e(8,5)的所有極圖

同理，考慮當p=9時，且滿足下列條件：P4?G、H3?G、Δ(G)≤7.則 僅有如圖6所示的2種形式.

圖6 p=9時，G符合條件圖

由以上可得如下性質(zhì)：當頂點數(shù)p=9時，邊數(shù)最多的連通圖G，其中：P4?G、H3?G、Δ(G)≤7，則‖G‖=16.和比較表1，可見當p=9時，對于相同頂點數(shù)p的圖G，含有子圖C4的圖邊數(shù)更多，因此，只需考慮含C4的情況.由此可以得到e(9,6)的所有極圖，其中G滿足d(v)≤7,?v∈V(G)，含有P4?G、H3?G、Δ(G)≤7. 的圖G的邊數(shù)為16，僅有如圖7的3種形式.

圖7 e(9,6)的所有極圖

3 e(p,p-4)(p≤8)的所有極圖

綜合所述，實際上可以得到e(p,p-4)(p≤8)的所有極圖.當p=5時，e(5,1)=4,P5是e(5,1)的唯一極圖.當p=6時，e(6,2)=5，圖8所示是e(6,2)僅有的4個極圖.當p=7時，e(7,3)=6，圖9是e(7,3)的所有極圖.當p=8時，e(8,4)=7，k1,7是e(8,4)的唯一極圖.

圖8 e(6,3)的4個極圖

圖9 e(7,3)的所有極圖

對于e(p,p-4)(p>9)的極圖由定理1.1至定理1.6可知，可以找到相應的極圖，但是要把所有的極圖一一找出是有一定的困難的，有待今后進一步研究.

[1]RD Dutton and RC Brigham. On the size of graphs of a given bandwidth [J]. Disc Math 1989，76：191.

[2]Y Alavi, J Liu， J McCanna,et al. On the minimum size of graphs with a given bandwidth [J]. Bu11 Inst Comb App1，1992，33(6)：22.

[3]PCB Lam and Y Lin. An extremal graph problem on bandwidth [S]. Manuscript. 1996.

[4]郝建修.關于帶寬極值問題的兩個結(jié)果[J].應用數(shù)學，2000，13(3)：73.

[5]林冶勛.圖帶寬問題的若干刻劃[J].運籌學學報，2000，4(2)：1.

[6]陸鋒.帶寬極圖的一個反例[J].九江學院學報(自然科學版)，2013，28(3)：68.

[7]袁文彬.關于圖的帶寬問題[D].福州：福州大學.2009.

[8]Yang Aifeng， Lin Yixun. Some results on an extreml bandwidth graph problem. Mathematica Applicata，2003，16(1)：143.

(責任編輯李平)

2014-4-23

陸鋒，21848119@qq.com.

O 157.5

A

1674-9545(2014)02-0058-(04)