調(diào)和指標(biāo)的極值圖

王曉，汪小黎

（商洛學(xué)院數(shù)學(xué)與計算機應(yīng)用學(xué)院，陜西商洛726000）

調(diào)和指標(biāo)的極值圖

王曉，汪小黎

（商洛學(xué)院數(shù)學(xué)與計算機應(yīng)用學(xué)院，陜西商洛726000）

調(diào)和指標(biāo)；極值圖；Split圖

設(shè)G=（V（G），E（G）），表示一個圖，其中V（G）和E（G）分別表示G的頂點集和邊集。對于u∈（V（G），d（u））表示頂點u的度，度為1的頂點稱為葉子點。若圖G的頂點集的子集A的導(dǎo)出子圖G［A］是空圖，則稱A為G的獨立集；若G［A］是完全圖，則稱A為G的團(tuán)。其他本文中涉及到概念參閱文獻(xiàn)［1］。

一個圖稱為Split圖［10］，如果它的頂點集能劃分為一個團(tuán)和一個獨立集。用Sp，q表示頂點集劃分為階為p的團(tuán)和階為q的獨立集的Split圖。本文中首先利用圖的調(diào)和指標(biāo)的另一種表述形式，對非空正則圖的調(diào)和指標(biāo)進(jìn)行研究，然后利用文獻(xiàn)［3］中的一個引理，證明了固定團(tuán)數(shù)和獨立集階數(shù)的Split圖的調(diào)和指標(biāo)的下界，并給出相應(yīng)的極圖。

1 正則圖的調(diào)和指標(biāo)

文獻(xiàn)［5］中給出了最小度δ（G）≥k的圖G的調(diào)和指標(biāo)的另一種表述形式，并證明了不含三角形的圖的調(diào)和指標(biāo)的下界。這里，首先給出一般圖G的調(diào)和指標(biāo)的另外一種表述形式。設(shè)G是階為n的圖，mij表示圖G中兩個端點的度數(shù)分別為i和j的邊的數(shù)目，則有

在文獻(xiàn)［3］中，給出固定階數(shù)的簡單連通圖的調(diào)和指標(biāo)的下界。

結(jié)合定理1和定理2，有如下定理。

2 Split圖的調(diào)和指標(biāo)

［1］Reinhard D.Graph theory（Second Edition）［M］. Hongkong：Springer-Verlag，2000：95-122.

［2］FajtlowiczS.OnconjecturesofGraffiti-II［J］.CongrNumer，1987，60：187-197.

［3］Zhong L.The harmonic index for graphs［J］.Applied Mathematics Letters，2012，25（2）：561-566.

［4］Zhong L.The harmonic index on unicyclic graphs［J］. Arc Combinatoria，2012，104：261-269.

［5］Liu J.On the harmonic index of triangle-free graphs［J］. Applied Mathematics，2013，4（8）：1204-1206.

［6］王曉，段芳.單圈圖的解析［J］.華東師范大學(xué)學(xué)報：自然科學(xué)版，2009，143（1）：13-21.

［7］Deng H，Balachandran S，Ayyaswamy S K，et al.Note：On the harmonic index and the chromatic number of a graph［J］.Discrete Applied Mathematics，2013，161：2740-2744.

［8］陳錦麗.具有k個懸掛點的仙人掌圖的調(diào)和指標(biāo)［J］.閩南師范大學(xué)學(xué)報：自然科學(xué)版，2014，84（2）：7-11.

［9］Chen J，Lv J.On the harmonic index of cacti［J］. InternationalJournalofAppliedMathematicsand Statistics，2014，52（1）：72-83.

［10］Maffray F，Preissmann M.Linear recognition of pseudo-split graphs［J］.Discrete Applied Mathematics，1994，52（94）：307-312.

（責(zé)任編輯：李堆淑）

The Extremal Graphs for Harmonic Index

WANG Xiao， WANG Xiao-li
（College of Mathematics and Computer Application，Shangluo University，Shangluo726000，Shannxi）

harmonic index；extremal graphs；Split graph

O157.5

A

1674-0033（2015）04-0003-02

10.13440/j.slxy.1674-0033.2015.04.001

2015-04-16

商洛學(xué)院科研基金項目（12SKY011）

王曉，男，河南南陽人，碩士，講師