圖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圖的度距離指標的上界。

關鍵詞： 度距離指標（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 概述

為了尋找一類具有任意大色數但不含三角形的圖類，Mycielski在1955[1]年提出了一種有趣的圖變換，它是根據圖經過一種圖變換得到一個新圖，我們稱之為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的復制點，頂點u叫做圖μ（G）的根點。

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

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

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

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

圖G的Wiener指標被定義W（G）=∑{u，v}v（G）dG（u，v），其中dG（u，v）指圖G中任意兩點的距離之和. 由Ivan Gutman和trinajstic [12] 引入的兩個重要的拓撲指數， 第一個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 指數的加權版本. 圖G的度距離由DD（G）表示， 被定義如下， 并且對于很多重要的圖類都已經被計算 （參見文獻[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的對應點并且X稱之為μ的根點。 為了確定任意圖的Mycielskian圖的度距離指標， 我們需要如下簡單的結果.

結論1.

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

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

結論 2.

根據圖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）

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

引理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.

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

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

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

情況三：{u，v}X；

根據結論一，可得出：

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

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

同樣根據我們的結論二，可得出：對于任意的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，Filomat， 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年度新疆自治區青年科技創新人才培養工程項目（qn2015yx010）

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

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