| 标题 | 图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-），女，汉族，甘肃人，博士研究生，研究生方向：是图论及其应用。 |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。