圖G的Mycielskian圖的度距離指標

馬雪嬌 邊紅

摘 要：圖G是有限連通簡單圖， 圖G的度距離指標用DD（G）來表示， 其定義為

∑{u，v}V（G）dG（u，v）（degG（u）+degG（v））

其中degG（u）指圖G中點u的度，dG（u，v）指圖G中任意兩點u和v之間的距離。 在本篇文章中， 我們確定了任意圖的Mycielskian圖的度距離指標的上界。

關(guān)鍵詞： 度距離指標（degreedistanceindex）； Zagreb 指標；Mycielkian圖

Degree Distance Index of Mycielskian Graph

Ma Xuejiao Bian hong*

School of Mathematical Sciences Xinjiang Normal University Xinjiang Urumqi 830017

Abstract：let be a finite connected simple graph. The degree distance index of G is defined as

{u，v}v（G）dG（u，v）（degG（u）+degG（v））， where degG（U） is the degree of vertex in and （dG（u，v）） is the distance between two verticesuand Vin G . In this paper， we determine the degree distance index DDG of the graph G of Mycielskian graph.

Key words：Degree distance index； Zagreb indices； Mycielskian graph

1 概述

為了尋找一類具有任意大色數(shù)但不含三角形的圖類，Mycielski在1955[1]年提出了一種有趣的圖變換，它是根據(jù)圖經(jīng)過一種圖變換得到一個新圖，我們稱之為Mycielskian圖，記為μ（G）.其定義如下：對于一個圖G=（V，E），頂點集V（G）={v1，v2，…，vn}.那么圖G的Mycielskian圖的頂點集為V（G）∪V′（G）∪{u}，其中V′（G）={x1，x2，…，xn}，μ（G）的邊集E（μ（G））=E（G）∪{vixj∶vivj∈}∪{xiu∶xi∈V′（G）}，其中i，j∈{1，2，…，n}.頂點xi叫做vi的復(fù)制點，頂點u叫做圖μ（G）的根點。

本篇論文中所考慮的圖都是非平凡的簡單連通圖. 令G=（V（G），E（G））表示一個圖， 其中點的數(shù)量為n=V（G）， 而邊的數(shù)量為m=E（G）.u和v兩點之間的距離用dG（u，v）來表示，它指的是圖G中任意兩點u和v之間最短路的長度。 圖G的直徑是指dG（u，v）的最大值，即圖G中任意兩點距離的最大值。 圖G中任意一點u的度是指在圖G中與點u相連接的邊的個數(shù)，用符號來degG（u）表示。

以化學分子結(jié)構(gòu)為基礎(chǔ)的圖叫做化學圖，它的點可以表示原子，邊可以表示為原子之間的連接紐帶。一個化學圖G的拓撲指標是圖G的一種數(shù)值不變量并且它并不依賴于圖的改變而變化。 而基于圖的頂點之間的距離或頂點度的拓撲，

指數(shù)和圖不變量被廣泛用于表征分子圖，建立分子的結(jié)構(gòu)和性質(zhì)之間的關(guān)系，預(yù)測化合物的生物活性，以及使它們的化學應(yīng)用. 各類拓撲指標（topological index）的持續(xù)發(fā)展已經(jīng)將理論化學中的所謂的“量子結(jié)構(gòu)性質(zhì)關(guān)系（QSPR）”和“量子結(jié)構(gòu)活性關(guān)系（QSAR）”轉(zhuǎn)化成強有力的和被廣泛應(yīng)用的模型，這些模型可以預(yù)測他們被廣泛地應(yīng)用于建立分子結(jié)構(gòu)與他們的物理化學特性之間關(guān)系.在過去二十年隨著它們在物理、有機化學、分析化學、藥理化學、物理化學、生物化學、理論科學等學科上的應(yīng)用被廣泛接受. 拓撲指標如雨后春筍般涌現(xiàn)出來.有關(guān)圖的各種指標的研究已有多年的歷史，據(jù)不完全統(tǒng)計，至今已有400多個拓撲指標。

在1947年， 拓撲指標的概念來自Harold Wiener工作中， 而他正在研究石蠟的沸點，此后各項拓撲指標如雨后春筍般涌現(xiàn)出來，有關(guān)圖的各種指標的研究已有多年的歷史，據(jù)不完全統(tǒng)計，至今已有400多個拓撲指標. 而關(guān)Mycielskian圖的很多性質(zhì)與拓撲指標，F(xiàn)isher等人在文獻[2]中說明了Mycielskian圖的哈密頓性、直徑、控制集、packing集和雙團劃分數(shù)，有關(guān)Mycielskian圖的團數(shù)和色數(shù)的相關(guān)結(jié)果，讀者可以參閱文獻[311]. 而在本篇論文中，我們所研究的就是有關(guān)Mycielskian圖的度距離指標，有關(guān)文獻[1214]中研究到的Wiener指標和Zagreb指標，在本篇論文中都需要用到。

圖G的Wiener指標被定義W（G）=∑{u，v}v（G）dG（u，v），其中dG（u，v）指圖G中任意兩點的距離之和. 由Ivan Gutman和trinajstic [12] 引入的兩個重要的拓撲指數(shù)， 第一個Zagreb指標 M1（G） [13] ，第二個Zagreb指標 M2（G） [14]，兩者別被定義為：

M1（G）=Σuv∈E（G）（degG（u）+degG（V））=Σu∈V（G）（degG（u））2

M2（G）=ΣuvE（G）degG（u）degG（v）

度距離是由 Dobrynin，Kochetova [14] 和 Gutman 引入作為 Wiener 指數(shù)的加權(quán)版本. 圖G的度距離由DD（G）表示， 被定義如下， 并且對于很多重要的圖類都已經(jīng)被計算 （參見文獻[13]和[14] ）：

DD（G）=∑{u，v}V（G）dG（u，v）（degG（u）+degG（v））

在本文中， 我們分別討論Mycielskian圖在每個點對的位置不同的情況下的度距離指標， 進而給出任意圖的Mycielskian圖的度距離指標的上界。

2 Mycielskian圖的度距離指標

V（G）={v1，v2，…，vn}，X={x1，x2，…，xn}，V（G）∩X=，xV（G）∪X，令μ來表示圖G的Mycielskian圖。頂點集為V（μ）=V（G）∪X∪{x}，邊集為E（μ）=E（G）∪{vi，xj∶vivj∈E（G）}∪{xxi∶1≤i≤n}這里我們把xi稱為點vi的對應(yīng)點并且X稱之為μ的根點。 為了確定任意圖的Mycielskian圖的度距離指標， 我們需要如下簡單的結(jié)果.

結(jié)論1.

μ表示圖G的Mycielskian 圖，對于任意v∈V（μ）很容易得出結(jié)論：

degμ（v）=nv=x1+degG（vi）v=xi2degG（vi）v=vi

結(jié)論 2.

根據(jù)圖G的Mycielskian圖的定義，對于任意u，v∈V（μ），容易看出任意兩點u，v之間的距離公式：

dμ（u，v）=

1u=x，v=xi2u=x，v=vi2u=xi，v=xjdG（vi，vj）u=vi，v=vj，dG（vi，vj）≤34u=vi，v=vj，dG（vi，vj）≥32u=vi，v=xj，i=jdG（vi，vj）u=vi，v=xj，i≠j，dG（vi，vj）≤23u=vi，v=xj，i≠j，dG（vi，vj）≥3

由此可以看出， 任意圖的 Mycielskian圖點對之間的距離至多是4，因此我們可以得出任意圖的 Mycielskian圖的直徑是 4。

顯然在一個圖V=V（G）中，有E（G）個距離為1的無序點對，并且可以得出

∑（u，v）∈V×VdG（u，v）=1（degG（u）+degG（v））=

2∑uv∈E（G）（degG（u）+degG（v））=2M1（G）

下面我們給出主要結(jié)果的證明需要用到的兩有用引理。

引理1： 令圖G是一個有m條邊n個頂點的圖， 其中頂點集為

V={v1，v2，…，vn}. 則有：

∑{vi，vj}V（G）（degG（u）+degG（v））=（n-1）2m

引理2： 對于每一個有m條邊的圖， 我們有

∑{vi，vj}∈E（G）（degG（vi）+degG（vj））=（n-1）2m-M1（G）

定理1：圖G是一個有n個頂點，m條邊的簡單圖，且其直徑為d，如果μ是圖G的Mycielskian圖，那么我們有：

DD（μ）≤4DD（G）+（1-d）M1（G）+dn（n-1）+5n2+n+20m+4mn+2dmn-4dm，

特別的，如果圖G的直徑為2，則上述不等式取等號，即（μ）=4DD（G）-M1（G）+7n2-n+12m+8mn.

證明：根據(jù)任意兩個點對所在的位置不同，我們分如下的六種情況來討論.

情況一：u=x，v∈X；

情況二：u=x，v∈v（G）；

情況三：{u，v}X；

根據(jù)結(jié)論一，可得出：

情況四：{u，v}V（G）；

根據(jù)我們的結(jié)論二，可得出dμ（vi，vj）=dG（vi，vj），dG（vi，vj）≤3；4 dG（vi，vj）≥4.，顯然dμ（vi，vj）≤4≤dG（vi，vj），因此，我們有：

同樣根據(jù)我們的結(jié)論二，可得出：對于任意的i≠j，dμ（vi，vj）=dG（vi，vj），dG（vi，vj）≤2；3 dG（vi，vj）≥3，顯然dμ（vi，vj）≤3≤dG（vi，vj）≤d，因此，我們有：

綜合其它幾種情況，我們有DD（μ）=4DD（G）-M1（G）+7n2-n+12m+8mn.

參考文獻：

[1]J. Mycielski， Sur le colouriage des Graphes. Colloq. Math. 3 （1955） 161162.

[2]D. C. Fisher， P. A. McKenna， E. D. Boyer， Hamiltionicity， diameter， domination， packing， and biclique partitions of Mycielskis graphs， Discrete Appl Math. 84 （1998） 93105.

[3]P. Rudnicki， L. Stewart， The Mycielskian of a graph， Formalized mathematics. 19 （2011） 2734.

[4]M. Larsen， J. Propp， D. Ullman， The fractional chromatic number of Mycielskis graphs， J. Graph. Theory. 19 （1995） 411416.

[5]G. J. Chang， L. Huang， X. Zhu， Circular chromatic number of Mycielskis graphs， Discret Math. 205 （1999）2337.

[6]M. Caramia， DellOlmo， P， A lower bound on the chromatic number of Mycielski graphs， Discret Math. 235 （2001） 7986.

[7]G. J. Chang， L. Huang， X. Zhu， Circular chromatic numbers of Mycielskis graphs， Discrete Math. 205 （1999） 2337.

[8]D. Hajibolhassan， X. Zhu， The circular chromatic number and Mycielski construction， J. Graph Theory. 44 （2003） 106115.

[9]P. C. B. Lam， W. Lin， G. Gu， Z. Song， Circular chromatic number and a generalization of the construction of Mycielski， J. Combin Theory. 89 （2003） 195205.

[10]G. Fan， Circular chromatic number and Mycielski graphs， Combinatorica. 24 （2004） 127135

[11]L. Huang， G. J. Chang， The circular chromatic number of the Mycielskian of Gdk ， J. Graph Theory. 32 （1999） 6371.

[12]M. Eliasi， G. Raeisi， B. Taeri， Wiener index of some graph operations， Discrete. Appl Math. 160 （2012） 13331344.

[13]H. Hua， A. R. Ashrafi， L. Zhang， More on Zagreb coindices of graphs， Filomat. 26 （2012） 12151225.

[14]AliBehtoei， MahAnbarloei， Degree distance index of the Mycielskian and its complement， Iranian Journal of Mathematical Chemistry. 7 （2016） 19.

[15]A. A. Dobrynin and A. A. Kochetova， Degree distance index of a Graph： A Degree Analogue of the Wiener index， J. Chem. Inf. Sci. 34 （1994） 10821086.

[16]I. Gutman， Selected Properties of the Schultz Molecular Topological Index， J. Chem. Inf. Comput. Sci. 34 （1994） 10871089.

[17]I. Gutman， N. Trinajstic， Graph theory and molecular orbitals. Totalelectron energy of alternant hydrocarbons， Chem. Phys. Lett. 17（1972） 535538.

[18]H. Hua， A. R. Ashrafi， L. Zhang， More on Zagreb coindices of graphs，F(xiàn)ilomat， 26 （2012） 12151225.

[19]M. H. Khalifeh， H. Yousefi Azari， A. R. Ashrafi， S. Wagner， Some new results on distance based graph invariants， Eur. J. Comb. 30 （2009）11491163.

[20]A. Ilic， S. Klavzar， D. Stevanovic， Calculating the degree distance of partial Hamming graphs， MATCH Commun. Math. Comput. Chem.63 （2010） 411424.

[21]J. Mycielski， Sur le colouriage des graphes， Colloq. Math. 3 （1955）161162.

[22]M. Tavakoli， F. Rahbarnia， Applications of some graph operations in computing some invariants of chemical graphs， Iranian J. Math.Chem. 4 （2013） 221230.

[23]K. Xu， M. Liu， K. C. Das， I. Gutman and B. Furtula， A survey on graphs extremal with respect to distancebased topological indices，MATCH Commun. Math. Comput. Chem. 71（2014） 461508.

[24]Z. Yarahmadi， Computing some topological indices of tensor product of graphs， Iranian J. Math. Chem. 2 （2011） 109118.

基金項目：國家自然科學基金項目（11361062，61662079）；2015年度新疆自治區(qū)青年科技創(chuàng)新人才培養(yǎng)工程項目（qn2015yx010）

作者簡介：馬雪嬌（1992-），女，漢族，新疆人，碩士，研究生方向：圖論與組合數(shù)學 。

*通訊作者：邊紅（1974-），女，漢族，甘肅人，博士研究生，研究生方向：是圖論及其應(yīng)用。