若干运算图的Schultz指数

第２７卷第４期　五邑大学学报（自然科学版）　２０１３年　１　１月　ＪＯＵＲＮＡＬ　ＯＦ　ＷＵＹＩ　ＵＮＩＶＥＲＳＩＴＹ（Ｎａｔｕｒａｌ　Ｖ６１．２７　ＮＯ．４　ＮＯＶ．　２０１３　

文章编号：１００６－７３０２（２０１３）０４—０００１—０５　

若干运算图的Ｓｃｈ　ｕ　ｌｔｚ指数　

林有创，欧见平，秦莹莹　

（五邑大学　数学与计算科学学院，广东　江门　５２９０２０）　

摘要：确定了两个图的联、对称差、复合和析取等运算所得到的图的Ｓｃｈｕｌｔｚ指数．　

关键词：Ｓｅｈｕｌｔｚ指数；联图；对称差；复合图；析取　

中图分类号：０１５７．５　文献标志码：Ａ　

ｏｎ　ｔｈｅ　Ｓｅｈｕｌｔｚ　Ｉｎｄｅｘ　ｏｆ　Ｓｏｍｅ　Ｇｒａｐｈｓ　Ｏｐｅｒａｔｉｏｎｓ　

ＬＩＮ　Ｙｏｕ－ｃｈｕａｎｇ，ＯＵ　Ｊｉａｎ－ｐｉｎｇ，ＱＩＮ　Ｙｉｎｇ—ｙｉｎｇ　（Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｓｃｉｅｎｃｅ，Ｗｕｙｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｊｉａｎｇｍｅｎ　５２９０２０，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｄｅｔｅｒｍｉｎｅｓ　ｔｈｅ　Ｓｃｈｕｈｚ　ｉｎｄｅｘ　ｏｆ　ｇｒａｐｈｓ　ｃｏｎｓｔｒｕｃｔｅｄ　ｂｙ　ｇｒａｐｈ　ｏｐｅｒａｔｉｏｎｓ　ｓｕｃｈ　ａｓ　ｊｏｉｎ，　

ｓｙｍｍｅｔｒｉｃ　ｄｉｆｅｒｅｎｃｅ，ｃｏｍｐｏｓｉｔｉｏｎ　ａｎｄ　ｄｉｓｊｕｎｃｔｉｏｎ．　

Ｋｅｙ　ｗｏｒｄｓ：Ｓｅｈｕｈｚ　ｉｎｄｅｘ；ｊｏｉｎ；ｓｙｍｍｅｔｒｉｃ　ｄｉｆｆｅｒｅｎｃｅ；ｃｏｍｐｏｓｉｔｉｏｎ；ｄｉｓｊｕｎｃｔｉｏｎ　

设Ｇ＝（　，　）是一个简单图，即没有环和重边．记　（　，ｖ）为图Ｇ中两点“和ｖ之间的距离，即连　

接点材和ｖ的最短路径的长度．在不产生混淆的情况下，简记靠（　，ｖ）为ｄ（ｕ，ｖ）．点Ｕ在图Ｇ中的度用　

）表示，图Ｇ的点集和边集分别用　（Ｇ）和Ｅ（Ｇ）表示．对于给定的图Ｇ，其Ｗｉｅｎｅｒ指数　。】定义如　

下：　

（Ｇ）＝∑　（　）．　Ｈ，ｖ∈　（Ｇ）　设Ｇ＝（　，　）的和是两个简单图．它们的联图记为ＧＩ＋Ｇ２，其顶点集合　（Ｇｌ＋Ｇ２）＝　（ＧＩ）Ｕ　Ｖ（Ｇ：），　

边集为Ｅ（Ｇｌ＋Ｇ：）＝Ｅ（Ｇ１）＋Ｅ（Ｇ２）＋｛ｔ，Ｄ２ｌ甜∈　（ＧＩ），　∈Ｖ（Ｇ　）），它们的复合图记为Ｇｌ【Ｇ２】，其点集为　

（Ｇｌ【Ｇ２］）＝ｖ（ｃ。ｘ　Ｖ（Ｇ：），边集Ｅ（Ｇｌ【ＧＥ】）：｛（（　，ｚｆ：），（Ｖ　，ｖ：））Ｉｚｆ。Ｙｌ∈Ｅ（Ｇ１），或　＝ｙ１且“　１，：∈Ｅ（Ｇｚ）｝，　

它们的析取记为Ｇ１　Ｖ　Ｇ２，其点集为　（ＧＩ　Ｖ　Ｇ２）＝　（Ｇ１）×　（Ｇ２），边集为Ｅ（ＧＩ　ＶＧ２）＝｛（（　，　：），　

（ｖ。，ｖ：））１　１２１ｖ。∈Ｅ（Ｇ。），或缸　ｖ　∈Ｅ（Ｇ　）｝，它们的对称差记为Ｇ　０Ｇ：，其点集为　（Ｇ１　０Ｇ２）＝Ｖ（Ｇ１）ｘ　ｖ（ｃ：），　

边集为Ｅ（Ｇ。０Ｇ　）＝｛（（　。，Ｈ２），（　，Ｖ２））Ｉ　ＨＩＶ。∈Ｅ（Ｇ１）或者　：Ｖｚ∈Ｅ（Ｇ２），但不同时成立｝．　

为了更好地刻画顶点度和距离的关系，定义Ｓｃｈｕｌｔｚ指数如下：　

（Ｇ）＝　（　（　）＋　（Ｖ））　（　，Ｖ）．　“，ｖ∈　（Ｇ）　

关于这种指数的化学背景和数学性质，请参阅文献【２】．在本文的证明中需要用到第一和第￣Ｚａｇｒｅｂ　

收稿日期：２０１３—０４—２５　基金项目：国家自然科学基金资助项目（Ｎｏ．１１１２６３２６）；广东省自然科学基金资助项目（￥２０１２０１００１０８１　５）；　五邑大学青年基金资助项目（２０１２１００４ｌ６５０５０４）　作者简介：林有创（１９８６一），男，广西贺州人，在读硕士生，从事图论连通性及其量子化学应用的研究；欧　见平，教授，博士，硕士生导师，通信作者，主要从事图论连通性的研究．

　２　五邑大学学报（自然科学版）　２０１３年　

指数　。　Ｍ　和Ｍ：，其中Ｍ．（Ｇ）＝∑（　（甜）＋　（ｖ）），Ｍ：（Ｇ）＝∑　（　）　（ｖ）；还有第一ｚａｇｒｅｂ余指　Ｉ￣１１Ｅ，　（（　’　ｍ，ｃＥ（Ｇ　数　＝∑（　（“）＋　（ｖ）），第二ｚａｇｒｅｂ余指数　（Ｇ）＝∑　（　）　（ｖ）．ｚａｇｒｅｂ指数和ｚａｇｒｅｂ余　ｕｖｑ　（Ｇ）　ｕｒｇＥ（Ｇ）　指数有下面的关系【　】：　

。（Ｇ）＝２１Ｅ（Ｇ）Ｉ（ＩＶ（Ｇ）Ｉ—Ｉ）－Ｍ．（Ｇ），Ｍ　（Ｇ）＝２１Ｅ（Ｇ）Ｉ　一Ｍ：（Ｇ）一去　．（Ｇ）．　

二元运算图的拓扑指数的计算已经有很多结果．文献【８】计算了两个图的联、笛卡尔乘积、复合　

等图运算的Ｗｉｅｎｅｒ指数；文献［９】推广了文献【８】的结果，计算了上述图运算的Ｗｉｅｎｅｒ多项式（Ｗｉｅｎｅｒ　

指数和超Ｗｉｅｎｅｒ指数）；在文献［１０】中，作者计算了上述图运算的超Ｗｉｅｎｅｒ指数；在文献［１１，１２】中，　

作者计算了广义笛卡尔乘积图的Ｗｉｅｎｅｒ指数和超Ｗｉｅｎｅｒ指数．本文我们将计算联图、对称差、复合　

网和析取图的Ｓｃｈｕｌｔｚ指数．　

记　为图Ｇ的补图，则Ｉ　（Ｇ）ｌ＝Ｉ　（　）ｌ，ＲＩ　的两个点相连当日．仅当这两个点在图Ｇ中不相连．其　

他未作说明的符号与文献［１３］相同．　

１　联图的Ｓｃｈｕｌｔｚ指数　

为了计算方便，令Ｉ　（Ｇ）ｌ＝　，ＪＥ（Ｇ）Ｉ＝ｇ。，Ｉ　（　）Ｉ＝　，ＩＥ（　）ｌ：　．　

引理１【ｌ。】Ｈ。　假设图Ｇ和　是两个连通图，如果点“和点ｖ是联网Ｇ＋Ｈ的两个不同的点，则　

‰　ｖ）＝　减　减　只‘　．　

如果　是Ｇ的一个点，则　＋　（　）：　（　）＋　：；如果ｖ是　ｌｊ勺一个点，则　（Ｖ）＝　（ｖ）＋　。．　

定理１　如果Ｇ和　是两个连通图，则　

ｓ（Ｇ＋ｔ－ｔ）＝寺（Ｍｌ（Ｇ）＋Ｍｌ（Ｈ））＋（　＋ｎ２—１）（ｅｌ＋ｅ２）＋　１　２（３　＋３ｎ２—２）＋２ｎ２　ｅＩ＋２　ｅ２．　

证明　对于任意两点“，Ｖ∈　（Ｇ＋　），记：　

４＝｛ｚｆ∈　（Ｇ），Ｖ∈　（　）｝，　＝｛　，ｖ∈　（Ｇ）｝，　Ａ３＝｛材，’，∈　（　）｝．　

若（　，ｖ）∈Ａ。，记Ｓｔ（Ｇ＋Ⅳ）＝∑　∑（　）＋　：十　（ｖ）＋　），南引理ｌ得：　

ＳＩ（Ｇ＋Ｈ）＝ＥｌＩ　２（ｈｉ＋　）＋２ｎ２ｅＩ＋２ｎｌｅ２；　

记　

ｓ２（Ｇ＋Ⅳ）＝∑（　（　）＋门２十　（Ｖ）＋ｎ２）＝　

∑（　（材）＋　（Ｖ）＋２　）＋２∑（　（“）＋　（Ｖ）＋２　）＝　

Ｍｌ（Ｇ）＋２　＋４ｎｚｅｌ＋Ｍｌ（Ｇ）；　

（Ｇ＋　）＝　∑（　Ｈ（　）＋，２１＋　Ｈ（Ｖ）＋　）＝Ｍ１（Ｈ）＋２ｎａｅ２＋４ｎ￣ｅｚ＋Ｍ１（Ｈ）．　

则：　

Ｓ（Ｇ＋Ｈ）；Ｓｌ＋Ｓ２＋　＝　

（　Ｇ）＋Ｍ　））＋（ｎ￣＋ｎｚ－１）（　＋　（３　３ｎｚ－２）＋２　＋２

　第２７卷第４期　林有创等：若干运算图的Ｓｃｈｕｈｚ指数　３　

２对称差的Ｓｃｈｕｌｔｚ指数　

引理２【　。】　。　假设图Ｇ和　是两个连通图，对任意的（　，　），（材。，ｖ２）∈　（Ｇ０　），有：　

），（　或者ｖＩｖ２∈　，但不是同时满足　喇　

２４；（　）　（　）．　

定理２假设Ｇ和Ｈ是两个连通图，则　

（Ｇ０　Ｈ）＝（　－４ｅ２ｎ２）　ｌ（Ｇ）＋（ｎ　一４　）　１（Ｈ）＋８ｎｊｎ２ｅｌｅ２＋８ｎｊｅ：ｅｊ＋８ｎ２ｅｊｅ２＋　

２［（２ｎ：　＋ｎ　２—４ｅ：）　（Ｇ）＋（２　＋　一４ｅ　）　（Ｈ）一２　（Ｇ）　（Ｈ）］．　

证明　根据引理２和Ｓｃｈｕｌｔｚ指数定义得：　

Ｓ．＝∑　∑｛（　。　Ｕｌ　）＋　（“：，ｖ：））　：∈Ｅ（Ｇ），ｖ．Ｖ：星Ｅ（　）｝＝　

，ｕ２∈　（（　）ｖＩ，’　∈　（　）　∑　∑｛　。　（（“．，Ｖ。））＋　。　（（　：，ｖ：））１Ｖ。≠Ｖ：｝＋　

∑∑（（　：一２ｄＨ（ｖ））（ｄｃ；（ｕ。）＋　（“：））＋２　（Ｖ））＝　

因此：　（　ｉ一６ｅｚｎ２）　ｌ（Ｇ）＋４ｎｌｒｔ２　Ｐ２—２ｎｌｅｌＭｌ（　）＋２Ｍｌ（Ｇ）　Ｉ（Ⅳ）．　

＝　∑　∑　｛（　。　１＇／１￣Ｙ１）＋　。　（材：，Ｖ：））ｆ　。　蓝Ｅ（Ｇ），Ｖ１Ｖ２∈Ｅ（　）｝＝　

ＨＩ，ｕ２∈　（（　）’　ｌ，’　Ｅ　ＩＨ）　∑　∑｛　。　（（甜．，ｖ１））十　洲（（　，Ｖ：））ｆ甜。≠　：｝＋　

∑　∑（（　一２　（　））（　（　）＋　（ｖ２））＋２　（　））＝　

（　－６ｅｌｎ１）Ｍｌ（Ｊ【，）＋４　ｌｎ２　－２ｎ２Ｐ２Ｍｌ（Ｇ）＋２　ｌ（Ｇ）ＭＩ（Ⅳ）　

＝２　∑　∑　｛（靠。　（　，ｖｆ）＋　。　／＇／２　ｖ２））Ｉ　ｖＩ　∈Ｅ（Ｈ），ｕｌｕ　∈Ｅ（Ｇ）｝：　

，“２　Ｅ　（Ｇ）　。ｖ２ａＶ（Ｈ）　

４ｎｌｅｌＭＩ（　）＋４ｎ２ｅ２ＭＩ（Ｇ）一４ＭＩ（Ｇ）　ｌ（Ｈ），　

＝２∑　∑　｛（　。　（Ｕｌ￣Ｙ１）＋　。　Ｕ　ｖ２））Ｊ　Ｅ（Ⅳ），　甜：芒￡（Ｇ））＝　

”ｌ，Ｕ２∈　（（　）　，ｌＪ２∈　（月）　２∑　∑｛　。　（（　。，ｖ．））＋　。　（（材：，　））Ｊ　。≠Ｕ２　Ｖ　≠Ｙ２｝＋　

２∑∑（（ｎ　－２ａｎ（ｖ））（ｄ￣　（　）＋ｄｏ（ｕ：））＋２　（ｖ））＋　

２∑∑（（　－２４；（ｕ））（ｄｎ（ｖ　）＋　（Ｖ　））＋２　：　（　））＝　１　ｔｖ２　（　）¨∈ｐ　（Ｇ）　

２Ｉ（２ｎ２ｅ２＋’，？；一４ｅ２）Ｍｌ（Ｇ）＋（２ｎＩ　ｅＩ＋　一４　）ＭＩ（Ｈ）一２　ｌ（Ｇ）Ｍｌ（Ｈ）Ｉ＋８ｎｌｅ２ｅＩ＋８ｎ２　８２　

Ｓ（Ｇ　０　Ｈ）＝Ｓｌ＋Ｓ２＋　＋　＝　

（　一４ｅ２ｎ２）Ｍ。（Ｇ）＋（　一４　Ｉ）Ｍ１（Ⅳ）＋８　＋８　＋８ｎ２ｅｌｅ２＋　

２［（２ｎｚ￣＋　２—４　）　（Ｇ）＋（２　＋　一４　）　（　）一２　（Ｇ）　（Ⅳ）］

　４　五邑大学学报（自然科学版）　２０１３扯　

３析取的Ｓｃｈｕｌｔｚ指数　

引理３　。】　。　假设Ｇ和　是两个连通图，如果点“和点ｖ是Ｇ　Ｖ　Ｈ的两个不同的点，则：　

ｌ，ｖ１），　’ｖ２　或者　

，析取图的点度为　，ｖ）　（ｖ）一　

（　）　（ｖ）．　

定理３假设Ｇ和Ⅳ是两个连通图，则：　

Ｓ（Ｇ　Ｖ　）＝（　一４ｎ２ｅ２）Ｍｊ（Ｇ）＋（　一４ｒ￣ｅ１）Ｍｉ（　）＋Ｍｌ（Ｇ）　ｌ（　）＋　

２Ｉ（２ｎ２ｅ２＋　２—２ｅ２）Ｍｌ（Ｇ）＋（２ｒ６ｑ＋　一２　）Ｍ１（Ⅳ）一Ｍｌ（Ｇ）　ｌ（　）ｌ＋　

８（ｎ，ｎ２ｅ１ｅ２＋／￣ｅ２ｅＩ＋；７２ｅ１ｅ２）．　

证明　根据引理３和Ｓｃｈｕｌｔｚ指数定义得：　

Ｓ（ＧＶＨ）＝∑　∑（　（　，　）＋　（　：，ｖ２）　（（　，　），（　：，ｙ２））＝　

∑　∑（　：（　（　）＋　（　：））＋　（　（ｖ。）＋　（ｖ：））　（（　，ｖ】），（￣／２＇Ｖ２））一　

∑　∑（Ｇ（ｕ　）　（ｖ。）＋　（　：）　（ｖ：））　（（　．，　），（甜　，　））．　

析取图￣９Ｓｃｈｕｌｔｚ指数的计算可拆分为４个子式Ｓ　、Ｓ　、Ｓ、　．　

＝　∑　∑　｛（　Ｕｌ　Ｖ】）十　（　，　））ｊ　ｖ】ｙ２∈Ｅ（Ⅳ）｝＝　

，？　∑（　（“。）＋Ｇ（ｖ。））＋　∑Ｍ　（Ｈ）－２ｎｌｅｉＭ。（　）＝　

４ｔｈｎ２　ｅ２＋　Ｍｌ（Ｈ）一２　ｅｌＭ１（Ｈ），　

Ｓ：＝∑　∑｛（ｄｏ　（　ｖ１）＋　洲（　：，ｖ：））　∈Ｅ（Ｇ）｝＝　

８。∑（　（“。）＋ｄｅ；（ｖ。））Ｊｒ－Ｉ，＇１２∑Ｍ　（Ｇ）一２ｎ　ｅ：Ｍ。（Ｇ）＝　１４２，　ｅＶ（Ｈ）　ＩＩ２，　ｅＶ（Ｈ）　４ｎｌｎ２ｅｌｅ２十，２　ｌ（Ｇ）一２ｎ２ｅｚＭ　Ｊ（Ｇ），　

Ｓ　＝　∑　∑　｛（　（　，　）＋　。　（”：，ｖ２））ｌｖ。ｖ：∈Ｅ（Ｈ），　。　∈￡（Ｇ）｝＝