非边幻和图的若干定理及证明

非边幻和图的若干定理及证明 Some Theorems and Proofs of Non-Edge-Magic Total Labeling Graphs 1 first-author 顾彦波，男，硕士生，现从事图论算法及其应用研究。E-mail：gsgtgyb@163.com 顾彦波，男，硕士生，现从事图论算法及其应用研究。E-mail：gsgtgyb@163.com gsgtgyb@163.com 1 corresp E-mail: lijingwen28@163.com E-mail: lijingwen28@163.com lijingwen28@163.com 1 1 兰州交通大学 电子与信息工程学院，甘肃 兰州 730070 兰州交通大学 电子与信息工程学院，甘肃 兰州 730070 School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, Gansu,China School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, Gansu,China 若 G ( p , q )的点边标号一一映射到 <math id="M1"><mfenced open="{" close="}" separators="|"><mrow><mn mathvariant="normal">1,2</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>p</mi><mo>+</mo><mi>q</mi></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422396&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422395&type= 20.74333382 4.06400013 ,使得任意边与其关联顶点的标号值之和为一个常数，这种标号被称之为边幻和全标号。本文设计了一种算法得到了9个点以内所有简单无向连通图中的非边幻和图,发现其中一些图具有某种相同的特征,因此定义了新的图运算符 <math id="M2"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422398&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422397&type= 11.51466751 3.13266659 和 <math id="M3"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext> </mtext><mo>∆</mo><mtext> </mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422400&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422399&type= 10.92199993 3.38666677 来刻画这两类联图，通过引入西顿序列，证明了在特定条件下，两类联图为非边幻和图。 If the labeling values of edges and vertices for a graph G ( p , q ) are mapped one by one to {1,2，…, p + q }, the sum of the labeling values for the edge and its incident vertices equals to a constant, and this labeling is called edge-magic total labeling. In this paper, an algorithm is designed to find all non-edge-magic total labeling graphs of all simple undirected connected graphs within 9 vertices. And we also find that some of the graphs have the same characteristics, thus define the new graph s operational characters <math id="M4"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422402&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422401&type= 11.51466751 3.13266659 and <math id="M5"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>∆</mo><mtext> </mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422404&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422403&type= 10.24466705 3.38666677 to depict them. Finally, by introducing the Sidon sequence, it is proved that two types of composite graphs are non-edge-magic total labeling graphs under certain conditions. 边幻和全标号 非边幻和图 算法 联图 edge-magic total labeling non-edge-magic total labeling graphs algorithm composite graphs 0　 引 言 1 在图标号发展的50年里，陆续出现了一系列图标号方法，其中边幻和全标号的研究较为广泛,它在编码理论、X射线晶体学、数据库管理等领域 [ 1 1 , 2 2 , 3 3 ] 都有应用。 Shiu等 [ 4 4 ] 证明了：对于 <math id="M6"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">2</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422406&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422405&type= 8.55133343 3.30199981 的 <math id="M7"><mi>m</mi><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi><mo>,</mo><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422408&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422407&type= 8.63599968 3.55599999 ，当且仅当 n 是偶数或 m 和 n 都是奇数时，具有超级边幻和全标号；fans具有边幻和全标号 [ 5 5 , 6 6 , 7 7 ] 。 图是否具有边幻和标号的问题也是备受关注的研究热点之一，然而这方面的研究成果仍相对较少。Craft等于1999年在文献[ 8 8 ]中提出并证明了当且仅当 r 为奇数且 <math id="M8"><mi>p</mi><mo>≡</mo><mn mathvariant="normal">4</mn><mo stretchy="false">(</mo><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi><mtext> </mtext><mn mathvariant="normal">8</mn><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422410&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422409&type= 21.25133324 3.72533321 时， r -正则图为非边幻和图；Chen于2001年在文献[ 9 9 ]中证明了 <math id="M9"><mi>n</mi><msub><mrow><mi>K</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>+</mo><mi>n</mi><msub><mrow><mi>K</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422412&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422411&type= 16.42533302 3.81000018 无超级边幻和全标号;文献[ 10 10 ]已证明：当且仅当 q 为偶数且 <math id="M10"><mi>p</mi><mo>+</mo><mi>q</mi><mo>≡</mo><mn mathvariant="normal">2</mn><mo stretchy="false">(</mo><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi><mtext> </mtext><mn mathvariant="normal">4</mn><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422414&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422413&type= 27.85533333 3.72533321 时，图 <math id="M11"><mi>n</mi><msub><mrow><mi>P</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422416&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422415&type= 5.50333357 3.55599999 为非边幻和图;文献[ 8 8 ]证明了当 <math id="M12"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">7</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422418&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422417&type= 8.55133343 3.30199981 时，所有的 <math id="M13"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422420&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422419&type= 3.97933340 3.55599999 均为非边幻和图。 本文利用算法并结合文献[ 11 11 ]中给出的非同构图生成方法，对有限点的图进行边幻和性判定，并得出其中所有的非边幻和图，通过观察与分析找到具有某种规律的图全为非边幻和图。最后引入西顿序列，证明了当 <math id="M14"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">8</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422422&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422421&type= 8.55133343 3.30199981 且 m 、 n 满足一定关系时， <math id="M15"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422424&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422423&type= 13.12333298 3.64066648 和 <math id="M16"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext> </mtext><mo>∆</mo><mtext> </mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422426&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422425&type= 12.44600010 3.89466667 为非边幻和图。 1　 预备知识 1 本文涉及到的图 G ( p , q )为简单无向连通图，其中 p 表示顶点数， q 表示边数;星图 <math id="M17"><msub><mrow><mi>S</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422428&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422427&type= 3.38666677 3.64066648 的定义为 n <math id="M18"><mo>-</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422430&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422429&type= 3.72533321 2.62466669 1个叶子结点连接到1个中心点，其他未定义的术语和符号参考文献[ 12 12 ]。 定义1 [ 13 13 ] 图 G ( p , q )存在双射 f : <math id="M19"><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422432&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422431&type= 9.65199947 3.55599999 <math id="M20"><mo>⋃</mo><mi>E</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422434&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422433&type= 11.93799973 3.72533321 <math id="M21"><mo>→</mo><mo stretchy="false">[</mo><mn mathvariant="normal">1</mn><mo>,</mo><mi>p</mi><mo>+</mo><mi>q</mi><mo stretchy="false">]</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422436&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422435&type= 19.89666748 3.72533321 ，使对 G 的任意一条边 uv ，总有 <math id="M22"><mi>f</mi><mo stretchy="false">（</mo><mi>u</mi><mo stretchy="false">）</mo><mo>+</mo><mi>f</mi><mo stretchy="false">（</mo><mi>v</mi><mo stretchy="false">）</mo><mo>+</mo><mi>f</mi><mo stretchy="false">（</mo><mi>u</mi><mi>v</mi><mo stretchy="false">）</mo><mo>=</mo><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422438&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422437&type= 37.16866684 3.97933340 ，则称 f 为图 G ( p , q )的一个边幻和全标号(edge-magic total labeling，EMTL)， <math id="M23"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422440&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422439&type= 1.69333339 2.79399991 为幻和常数。若 <math id="M24"><mi>f</mi><mo stretchy="false">（</mo><mi>V</mi><mo stretchy="false">（</mo><mi>G</mi><mo stretchy="false">）</mo><mo stretchy="false">）</mo><mo>→</mo><mo stretchy="false">[</mo><mn mathvariant="normal">1</mn><mo>,</mo><mi>p</mi><mo stretchy="false">]</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422442&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422441&type= 27.34733391 3.97933340 ，则称为图 G 的一个超级边幻和全标号(super edge-magic total labeling，SEMTL)。 定义2 将圈图 <math id="M25"><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422444&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422443&type= 4.23333359 3.64066648 的任意一条边并接到 <math id="M26"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422446&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422445&type= 3.97933340 3.55599999 的任意一条边后得到的联图，记为 <math id="M27"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422448&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422447&type= 13.12333298 3.64066648 ，其顶点 <math display="block" id="M28"><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo><mo>=</mo><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">）</mo><mo>⋃</mo><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo><mo>\</mo><mn mathvariant="normal">2</mn><mi>v</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422450&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422449&type= 54.69466782 4.40266657 即 <math display="block" id="M29"><mfenced open="|" close="|" separators="|"><mrow><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo>=</mo><mfenced open="|" close="|" separators="|"><mrow><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo>+</mo><mfenced open="|" close="|" separators="|"><mrow><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo>-</mo><mn mathvariant="normal">2</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422452&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422451&type= 65.78599548 4.57200003 其边 <math display="block" id="M30"><mi>E</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo><mo>=</mo><mi>E</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">）</mo><mo>⋃</mo><mi>E</mi><mo stretchy="false">（</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo><mo>\</mo><mi>e</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422454&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422453&type= 50.79999924 4.40266657 即 <math id="M31"><mfenced open="|" close="|" separators="|"><mrow><mi>E</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo>=</mo><mfenced open="|" close="|" separators="|"><mrow><mi>E</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo>+</mo><mfenced open="|" close="|" separators="|"><mrow><mi>E</mi><mo stretchy="false">（</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo>-</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422456&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422455&type= 64.09266663 4.57200003 <math id="M32"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422458&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422457&type= 13.12333298 3.64066648 示例如 图1 图1 (a)所示。 定义3 将星图 <math id="M33"><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422471&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422470&type= 3.81000018 3.64066648 的中心点并接到 <math id="M34"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422473&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422472&type= 3.97933340 3.55599999 的任意一顶点之后得到的联图，记为 <math id="M35"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>∆</mo><mtext> </mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422475&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422474&type= 11.59933376 3.89466667 ，其顶点 <math display="block" id="M36"><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext> </mtext><mo>∆</mo><mtext> </mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo><mo>=</mo><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">）</mo><mo>⋃</mo><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo><mo>\</mo><mi>v</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422477&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422476&type= 51.81599808 4.40266657 即 <math display="block" id="M37"><mfenced open="|" close="|" separators="|"><mrow><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext> </mtext><mo>∆</mo><mtext> </mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo>=</mo><mfenced open="|" close="|" separators="|"><mrow><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo>+</mo><mfenced open="|" close="|" separators="|"><mrow><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo>-</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422479&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422478&type= 64.76999664 4.57200003 其边 <math display="block" id="M38"><mi>E</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext> </mtext><mo>∆</mo><mtext> </mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo><mo>=</mo><mi>E</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">）</mo><mo>⋃</mo><mi>E</mi><mo stretchy="false">（</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422481&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422480&type= 46.14333344 4.40266657 <math id="M39"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>∆</mo><mtext> </mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422483&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422482&type= 11.59933376 3.89466667 示例如 图1 图1 (b)所示。 定义4 对于图 G ( p , q ),设三元组（ a , b , c ）表示图中任意相邻顶点及其边的标号，存在整数 k ，满足 <math id="M44"><mi>a</mi><mo>+</mo><mi>b</mi><mo>+</mo><mi>c</mi><mo>=</mo><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422485&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422484&type= 21.08199883 2.96333337 ， <math id="M45"><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo>∈</mo><mo stretchy="false">[</mo><mn mathvariant="normal">1</mn><mo>,</mo><mi>p</mi><mo>+</mo><mi>q</mi><mo stretchy="false">]</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422487&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422486&type= 28.10933304 3.72533321 ， <math id="M46"><mi>p</mi><mo>+</mo><mi>q</mi><mo>+</mo><mn mathvariant="normal">3</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mn mathvariant="normal">2</mn><mi>p</mi><mo>+</mo><mn mathvariant="normal">2</mn><mi>q</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422489&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422488&type= 38.43866730 3.89466667 ，则称三元向量 <math id="M47"><mo stretchy="false">(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422491&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422490&type= 11.93799973 3.55599999 的取值空间为图 G ( p , q )的EMTL解空间，记为 <math id="M48"><mi>φ</mi><mo stretchy="false">(</mo><mi>p</mi><mo>,</mo><mi>q</mi><mo>,</mo><mi>k</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422493&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422492&type= 15.32466698 3.72533321 。如 表1 表1 所示。 k 元组1 元组2 元组3 <math id="M52"><mo>⋯</mo></math> p + q +3 (1,2, p + q ) (1,3, p + q- 1) (1,4, p + q- 2) <math id="M53"><mo>⋯</mo></math> p + q +4 (1,3, p + q ) (1,4, p + q- 1) (1,5, p + q- 2) <math id="M54"><mo>⋯</mo></math> <math id="M55"><mo>⋮</mo></math> <math id="M56"><mo>⋮</mo></math> <math id="M57"><mo>⋮</mo></math> <math id="M58"><mo>⋮</mo></math> <math id="M59"><mo>⋮</mo></math> 2( p + q ) (1, p + q- 1, p + q ) (2, p + q- 2, p + q ) (3, p + q- 3, p + q ) <math id="M60"><mo>⋯</mo></math> 由定义1和定义4知，如下引理显然成立。 引理1 如果 G ( p , q )是EMTL图，设（ a , b , c ）为满足EMTL的相邻点和边标号三元组，则 <math id="M61"><mo>∀</mo><mo stretchy="false">(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo stretchy="false">)</mo><mo>∈</mo><mi>φ</mi><mo stretchy="false">(</mo><mi>p</mi><mo>,</mo><mi>q</mi><mo>,</mo><mi>k</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422503&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422502&type= 33.61266708 3.72533321 。 引理2 如果 G ( p , q )为非边幻和图（no⁃edge⁃magic⁃total⁃labeling，NEMTL），设（ a , b , c ）为图 G （ p , q ）中相邻点和边标号三元组，则不存在整数 k 和 q 组 <math id="M62"><mo stretchy="false">(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422505&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422504&type= 11.93799973 3.55599999 <math display="block" id="M63"><mo>∈</mo><mi>φ</mi><mo stretchy="false">(</mo><mi>p</mi><mo>,</mo><mi>q</mi><mo>,</mo><mi>k</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422507&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422506&type= 18.54199982 3.72533321 ，满足 <math display="block" id="M64"><mi>a</mi><mo>+</mo><mi>b</mi><mo>+</mo><mi>c</mi><mo>=</mo><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422509&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422508&type= 21.08199883 2.96333337 ， <math display="block" id="M65"><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422511&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422510&type= 8.88999939 3.21733332 <math display="block" id="M66"><mo>∈</mo><mo stretchy="false">[</mo><mn mathvariant="normal">1</mn><mo>,</mo><mi>p</mi><mo>+</mo><mi>q</mi><mo stretchy="false">]</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422513&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422512&type= 18.79599953 3.72533321 ， <math display="block" id="M67"><mi>p</mi><mo>+</mo><mi>q</mi><mo>+</mo><mn mathvariant="normal">3</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mn mathvariant="normal">2</mn><mi>p</mi><mo>+</mo><mn mathvariant="normal">2</mn><mi>q</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422515&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422514&type= 38.43866730 3.89466667 。 2　 EMTL算法 1 2.1　基本计算 2 由定义1可知 <math display="block" id="M68"><munder><mo movablelimits="false">∑</mo><mrow><mi>u</mi><mi>v</mi><mo>∈</mo><mi>E</mi></mrow></munder><mrow><mo stretchy="false">(</mo><mi>f</mi><mo stretchy="false">（</mo><mi>u</mi><mo stretchy="false">）</mo><mo>+</mo><mi>f</mi><mo stretchy="false">（</mo><mi>v</mi><mo stretchy="false">）</mo><mo>+</mo><mi>f</mi><mo stretchy="false">(</mo><mi>u</mi><mi>v</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><mo>=</mo><mi>q</mi><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422517&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422516&type= 49.86866760 6.68866634 由于每个边标号只相加一次，点标号需要相加 <math id="M69"><mi>d</mi><mo stretchy="false">（</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">）</mo><mo>-</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422519&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422518&type= 14.30866623 4.40266657 次，故（1）式可化简为： <math display="block" id="M70"><mi>q</mi><mi>k</mi><mo>=</mo><mi>C</mi><mo>+</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn mathvariant="normal">1</mn></mrow><mrow><mi>p</mi></mrow></munderover><mrow><mo stretchy="false">（</mo><mi>d</mi><mo stretchy="false">（</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">）</mo><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">）</mo><mi>f</mi><mo stretchy="false">(</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo></mrow></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422521&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422520&type= 46.31266785 8.72066689 其中 <math id="M71"><mi>d</mi><mo stretchy="false">(</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422523&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422522&type= 8.12800026 4.48733330 表示顶点 <math id="M72"><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422525&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422524&type= 2.62466669 3.55599999 的度，常数 <math id="M73"><mi>C</mi><mo>=</mo><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn mathvariant="normal">1</mn></mrow><mrow><mi>p</mi><mo>+</mo><mi>q</mi></mrow></munderover><mrow><mi>j</mi><mo>=</mo></mrow><mfrac><mrow><mo stretchy="false">（</mo><mi>p</mi><mo>+</mo><mi>q</mi><mo stretchy="false">）</mo><mo stretchy="false">（</mo><mi>p</mi><mo>+</mo><mi>q</mi><mo>+</mo><mn mathvariant="normal">1</mn><mo stretchy="false">）</mo></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422527&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422526&type= 49.53000259 9.31333351 。 为遍历图 G （ p , q ）的解空间，需对边进行标号，故设边系数均为0，由此可得 <math display="block" id="M74"><mi>q</mi><mi>k</mi><mo>=</mo><mi>C</mi><mo>+</mo><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn mathvariant="normal">1</mn></mrow><mrow><mi>p</mi></mrow></munderover><mrow><mo stretchy="false">（</mo><mi>d</mi><mo stretchy="false">（</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">）</mo><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">）</mo><mi>f</mi><mo stretchy="false">(</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo></mrow><mo>+</mo><mn mathvariant="normal">0</mn><mo>⋅</mo><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn mathvariant="normal">1</mn></mrow><mrow><mi>q</mi></mrow></munderover><mrow><mi>f</mi><mo stretchy="false">（</mo><msub><mrow><mi>e</mi></mrow><mrow><mi>j</mi></mrow></msub><mo stretchy="false">）</mo></mrow></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422529&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422528&type= 67.90267181 9.14400005 2.2　算法思想 2 1） 计算图 G （ p , q ）的度序列、常数 C 和点系数 <math id="M75"><mo stretchy="false">(</mo><mi>d</mi><mo stretchy="false">(</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422531&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422530&type= 17.35666656 4.48733330 ； 2） 初始化 <math id="M76"><mi>f</mi><mo stretchy="false">(</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422533&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422532&type= 7.70466709 4.65666676 ： <math id="M77"><mi>f</mi><mo stretchy="false">(</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">）</mo><mo>∈</mo><mo stretchy="false">[</mo><mn mathvariant="normal">1</mn><mo>,</mo><mi>p</mi><mo stretchy="false">]</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422535&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422534&type= 20.40466690 4.91066647 且标号值从小到大排列； 3） 如果存在正整数 k 使（3）式成立，则使用分配函数Allocation分配点和边的标号，若不成立，则对点系数与边系数0组成的序列Coe做一次全排列。 4） 若分配函数Allocation返回true，则表示该图存在EMTL，算法结束；若返回false，则继续对Coe做一次全排列； 5） 若Allocation返回true或全排列结束，则终止算法；若全排列结束时Allocation返回false，则表示该图为NEMTL图。 EMTL算法如 算法1 算法1 。 2 算法1 EMTL算法 输入 图 G （ p , q ）邻接矩阵 输出 图 G （ p , q ）标号矩阵 1 Calculate Coe， C ， <math id="M78"><mi>f</mi><mo stretchy="false">(</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo></math> ; 2 while true 3 Sum=CalculateSum(Coe, <math id="M79"><mi>f</mi><mo stretchy="false">(</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo></math> ); 4 if ((Sum+C)% q ==0) 5 if (Allocation (0,0,matrix)) 6 break; 7 End if 8 End if 9 permutation(Coe); 10 End while Allocation ( n ,start,matrix)函数用来分配点、边的标号。其思想为利用递归算法来分配标号，需遵守以下原则： 1） 若层数 n 超过了矩阵的行数，则分配成功，返回true。 2） 若当前层顶点元素与已填入元素产生冲突，则退回上一层，并且start++； 3） 若顶点元素已被分配，则start++。 4） 若当前层的元素取值start超过当前层元素的个数，则退回上一层。 5） 如第一层的元素取值超过第一层元素个数，则退出，分配失败，返回false。 Allocation ( n ,start,matrix)函数描述如下: 注： T_Matrix表示当前层分配成功后的邻接矩阵 2 Allocation ( n ,start,matrix) 输入 层数 n ，初始位置start，当前层的矩阵matrix； 输出 如果存在则输出EMTL，否则输出NEMTL 1 If ( n > =row) 2 return true; 3 End if 4 While true 5 if (start大于当前行所填元素个数) 6 break; 7 End if 8 if (当前元素填入矩阵产生冲突) 9 start++; 10 else 11 Allocation ( n +1, 0, T_Matrix); 12 End if 13 End while 引理3 EMTL算法搜索图 G （ p , q ）的EMTL解空间 <math id="M80"><mi>φ</mi><mo stretchy="false">(</mo><mi>p</mi><mo>,</mo><mi>q</mi><mo>,</mo><mi>k</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422541&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422540&type= 15.32466698 3.72533321 ，如果有解，则图 G （ p , q ）为EMTL图；否则为NEMTL图。 证 根据引理1和引理2，引理3显然成立。 例1 图2 图2 为图集 G (8,10)中一个EMTL和NEMTL图， 表2 表2 为图集 G (8,10)的解空间。 k 元组1 元组2 元组3 元组4 元组5 <math id="M85"><mo>⋯</mo></math> 21 （1,2,18） （1,3,17） （1,4,16） （1,5,15） （1,6,14） （1,7,13） （1,8,12） （1,9,11） （2,3,16） （2,4,15） （2,5,14） （2,6,13） （2,7,12） （2,8,11） （2,9,10） （3,4,14） （3,5,13） （3,6,12） （3,7,11） （3,8,10） （4,5,12） （4,6,11） （4,7,10） （4,8,9） （5,6,10） （5,7,9） （6,7,8） 22 <math id="M86"><mo>⋯</mo></math> <math id="M87"><mo>⋯</mo></math> <math id="M88"><mo>⋯</mo></math> <math id="M89"><mo>⋯</mo></math> <math id="M90"><mo>⋯</mo></math> <math id="M91"><mo>⋯</mo></math> <math id="M92"><mo>⋮</mo></math> <math id="M93"><mo>⋮</mo></math> <math id="M94"><mo>⋮</mo></math> <math id="M95"><mo>⋮</mo></math> <math id="M96"><mo>⋮</mo></math> <math id="M97"><mo>⋮</mo></math> <math id="M98"><mo>⋮</mo></math> 36 （1,17,18） （2,16,18） （3,15,18） （4,14,18） （5,13,18） <math id="M99"><mo>⋯</mo></math> 表2 表2 中加粗加下划线的标号组合为 图2 图2 (a)的解， 图2 图2 (b)在 <math id="M81"><mi>φ</mi><mo stretchy="false">(</mo><mn mathvariant="normal">8,10</mn><mo>,</mo><mi>k</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422554&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422553&type= 16.67933464 3.72533321 中无解，为NEMTL图。 3　 有关NEMTL图的定理及证明 1 定理1 当 <math id="M100"><mn mathvariant="normal">7</mn><mo>≤</mo><mi>n</mi><mo>≤</mo><mn mathvariant="normal">9</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422556&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422555&type= 15.07066631 3.30199981 时，图 <math id="M101"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>\</mo><mtext> </mtext><mi>e</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422558&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422557&type= 8.12800026 4.14866638 为NEMTL图。 证 1) 图 <math id="M102"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>\</mo><mi>e</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422560&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422559&type= 7.45066643 4.14866638 ，当 <math id="M103"><mn mathvariant="normal">7</mn><mo>≤</mo><mi>n</mi><mo>≤</mo><mn mathvariant="normal">9</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422562&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422561&type= 15.07066631 3.30199981 时，在其对应的解空间 <math id="M104"><mi>φ</mi><mo stretchy="false">（</mo><mn mathvariant="normal">7,20</mn><mo>,</mo><mi>k</mi><mo stretchy="false">）</mo><mi mathvariant="normal">、</mi><mi>φ</mi><mo stretchy="false">(</mo><mn mathvariant="normal">8,27</mn><mo>,</mo><mi>k</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422564&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422563&type= 34.96733475 3.97933340 、 <math id="M105"><mi>φ</mi><mo stretchy="false">(</mo><mn mathvariant="normal">9,35</mn><mo>,</mo><mi>k</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422566&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422565&type= 16.59466553 3.72533321 上执行EMTL算法，得出该类图 G 均为NEMTL,其结果如 表3 表3 所示。 （ p , q ） 图总数 边幻和图个数 非边幻和图个数 （7,20） 1 0 1 （8,27） 1 0 1 （9,35） 1 0 1 2) <math id="M110"><mtext> </mtext><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>\</mo><mtext> </mtext><mi>e</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422578&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422577&type= 8.88999939 4.14866638 的示例图如 图3 图3 所示 猜测 1 当 <math id="M113"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">10</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422587&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422586&type= 10.41399956 3.30199981 时，图 <math id="M114"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>\</mo><mi>e</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422589&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422588&type= 7.45066643 4.14866638 为NEMTL图。 定理2 当 <math id="M115"><mn mathvariant="normal">7</mn><mo>≤</mo><mi>p</mi><mo>≤</mo><mn mathvariant="normal">9</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422591&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422590&type= 14.39333344 3.89466667 ， <math id="M116"><mi>q</mi><mo>≥</mo><mfrac><mrow><mi>p</mi><mo stretchy="false">(</mo><mi>p</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">)</mo></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac><mo>-</mo><mn mathvariant="normal">2</mn><mo stretchy="false">(</mo><mi>p</mi><mo>-</mo><mn mathvariant="normal">6</mn><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422593&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422592&type= 40.30133438 7.36599970 <math id="M117"><mo>+</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422595&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422594&type= 5.67266655 2.96333337 时，图 G （ p , q ）均为NEMTL图。 证 1) 图 G （ p , q ）,当 <math id="M118"><mi>q</mi><mo>≥</mo><mfrac><mrow><mi>p</mi><mo stretchy="false">(</mo><mi>p</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">）</mo></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac><mo>-</mo><mn mathvariant="normal">2</mn><mo stretchy="false">（</mo><mi>p</mi><mo>-</mo><mn mathvariant="normal">6</mn><mo stretchy="false">）</mo><mo>+</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422597&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422596&type= 46.31266785 7.62000036 时，在其对应的解空间 <math id="M119"><mi>φ</mi><mo stretchy="false">（</mo><mn mathvariant="normal">7,20</mn><mo>,</mo><mi>k</mi><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422599&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422598&type= 16.00200081 3.97933340 ， <math id="M120"><mi>φ</mi><mo stretchy="false">(</mo><mn mathvariant="normal">7,21</mn><mo>,</mo><mi>k</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422601&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422600&type= 16.67933464 3.72533321 , …, <math id="M121"><mi>φ</mi><mo stretchy="false">(</mo><mn mathvariant="normal">9,36</mn><mo>,</mo><mi>k</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422603&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422602&type= 16.59466553 3.72533321 上执行EMTL判定算法，得出该类图不存在EMTL,其结果如 表4 表4 所示，故当 <math id="M122"><mi>q</mi><mo>≥</mo><mfrac><mrow><mi>p</mi><mo stretchy="false">(</mo><mi>p</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">)</mo></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac><mo>-</mo><mn mathvariant="normal">2</mn><mo stretchy="false">(</mo><mi>p</mi><mo>-</mo><mn mathvariant="normal">6</mn><mo stretchy="false">)</mo><mo>+</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422605&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422604&type= 47.92133331 7.36599970 且 <math id="M123"><mn mathvariant="normal">7</mn><mo>≤</mo><mi>p</mi><mo>≤</mo><mn mathvariant="normal">9</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422607&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422606&type= 15.07066631 3.89466667 时，图 G （ p , q ）均为NEMTL图成立。 （ p , q ） 图总数 EMTL图个数 NEMTL图个数 （7,20） 1 0 1 （7,21） 1 0 1 （8,25） 5 0 5 （8,26） 2 0 2 （8,27） 1 0 1 （8,28） 1 0 1 （9,31） 25 0 25 （9,32） 11 0 11 （9,33） 5 0 5 （9,34） 2 0 2 （9,35） 1 0 1 （9,36） 1 0 1 2) 图命名规则如下: G ( p ， q )-num，其中 p 为点数， q 为边数，num表示当前( p , q )图集下的第num个图。 图4 图4 给出该图集中当 <math id="M124"><mi>p</mi><mo>=</mo><mn mathvariant="normal">7</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422611&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422610&type= 8.55133343 3.47133350 ， <math id="M125"><mi>p</mi><mo>=</mo><mn mathvariant="normal">8</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422613&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422612&type= 8.55133343 3.55599999 时除 <math id="M126"><msub><mrow><mi>K</mi></mrow><mrow><mi>p</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422615&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422614&type= 3.89466667 3.55599999 和 <math id="M127"><msub><mrow><mi>K</mi></mrow><mrow><mi>p</mi></mrow></msub><mo>\</mo><mi>e</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422617&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422616&type= 7.45066643 4.14866638 外的全部图。由于此图集中当 <math id="M128"><mi>p</mi><mo>=</mo><mn mathvariant="normal">9</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422619&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422618&type= 8.55133343 3.55599999 时，图的数量较多，故仅给出部分示例，如 图5 图5 所示。 证毕。 猜测 2 当 <math id="M135"><mi>p</mi><mo>≥</mo><mn mathvariant="normal">10</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422639&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422638&type= 10.66799927 3.81000018 ， <math id="M136"><mi>q</mi><mo>≥</mo><mfrac><mrow><mi>p</mi><mo stretchy="false">(</mo><mi>p</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">)</mo></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac><mo>-</mo><mn mathvariant="normal">2</mn><mo stretchy="false">(</mo><mi>p</mi><mo>-</mo><mn mathvariant="normal">6</mn><mo stretchy="false">)</mo><mo>+</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422641&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422640&type= 5.67266655 2.96333337 时，图 G （ p , q ）为NEMTL图。 定理3、4的预备知识： 1) 对于图 G ( p , q ),若其存在EMTL，边幻和常数为 k ,且包含一个具有 n 个顶点的完全子图 H , <math id="M138"><msub><mrow><mi>u</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422643&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422642&type= 3.04799986 3.55599999 , <math id="M139"><msub><mrow><mi>u</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422645&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422644&type= 3.04799986 3.55599999 ,…, <math id="M140"><msub><mrow><mi>u</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422647&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422646&type= 3.04799986 3.55599999 分别为 H 的 n 个顶点， <math id="M141"><msub><mrow><mi>a</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>=</mo><mi>f</mi><mo stretchy="false">(</mo><msub><mrow><mi>u</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422649&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422648&type= 15.32466698 4.65666676 ,则 <math display="block" id="M142"><mi>f</mi><mo stretchy="false">（</mo><msub><mrow><mi>u</mi></mrow><mrow><mi>i</mi></mrow></msub><msub><mrow><mi>u</mi></mrow><mrow><mi>j</mi></mrow></msub><mo stretchy="false">）</mo><mo>=</mo><mi>k</mi><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422651&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422650&type= 31.66533279 4.91066647 ， <math display="block" id="M143"><mi>f</mi><mo stretchy="false">（</mo><msub><mrow><mi>u</mi></mrow><mrow><mi>k</mi></mrow></msub><msub><mrow><mi>u</mi></mrow><mrow><mi>l</mi></mrow></msub><mo stretchy="false">）</mo><mo>=</mo><mi>k</mi><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>k</mi></mrow></msub><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>l</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422653&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422652&type= 32.34266663 4.91066647 ， <math display="block" id="M144"><mi>f</mi><mo stretchy="false">（</mo><msub><mrow><mi>u</mi></mrow><mrow><mi>i</mi></mrow></msub><msub><mrow><mi>u</mi></mrow><mrow><mi>j</mi></mrow></msub><mo stretchy="false">）</mo><mo>≠</mo><mi>f</mi><mo stretchy="false">（</mo><msub><mrow><mi>u</mi></mrow><mrow><mi>k</mi></mrow></msub><msub><mrow><mi>u</mi></mrow><mrow><mi>l</mi></mrow></msub><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422655&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422654&type= 25.90799904 4.91066647 ， 故 <math id="M145"><msub><mrow><mi>a</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>+</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>j</mi></mrow></msub><mo>≠</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>k</mi></mrow></msub><mo>+</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>l</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422657&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422656&type= 25.56933403 3.97933340 ,即 H 中的任意两顶点之和均不相同。 2) 若序列 <math id="M146"><mi>A</mi><mo>=</mo><mo stretchy="false">（</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo>,</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422659&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422658&type= 28.61733246 4.48733330 ,且满足以下性质： ① <math id="M147"><mn mathvariant="normal">0</mn><mo><</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo><</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo><</mo><mo>…</mo><mo><</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422661&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422660&type= 34.29000092 3.72533321 ， ② 如果 <math id="M148"><msub><mrow><mi>a</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422663&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422662&type= 2.62466669 3.55599999 ， <math id="M149"><msub><mrow><mi>a</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422665&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422664&type= 2.62466669 3.55599999 ， <math id="M150"><msub><mrow><mi>a</mi></mrow><mrow><mi>k</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422667&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422666&type= 2.96333337 3.55599999 ， <math id="M151"><msub><mrow><mi>a</mi></mrow><mrow><mi>l</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422669&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422668&type= 2.70933342 3.55599999 为 A 中四个不同的元素，则 <math id="M152"><msub><mrow><mi>a</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>+</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>j</mi></mrow></msub><mo>≠</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>k</mi></mrow></msub><mo>+</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>l</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422671&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422670&type= 25.56933403 3.97933340 ， A 叫做西顿(Sidon)序列 [ 14 14 ] 。 若 <math id="M153"><mi>σ</mi><mo stretchy="false">(</mo><mi>A</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422673&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422672&type= 8.38199997 3.55599999 表示Sidon序列的大小，定义： <math display="block" id="M154"><mi>σ</mi><mo stretchy="false">（</mo><mi>A</mi><mo stretchy="false">）</mo><mo>=</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo>+</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422675&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422674&type= 29.97199821 4.40266657 , <math display="block" id="M155"><mtable columnalign="left"><mtr><mtd><mi>ρ</mi><mo stretchy="false">（</mo><mi>A</mi><mo stretchy="false">）</mo><mo>=</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>+</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow></msub><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo>+</mo><mn mathvariant="normal">1</mn><mo>=</mo></mtd></mtr><mtr><mtd><mi>σ</mi><mo stretchy="false">（</mo><mi>A</mi><mo stretchy="false">）</mo><mo>+</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow></msub><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>，</mo></mtd></mtr></mtable></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422677&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422676&type= 53.17066574 10.24466705 <math display="block" id="M156"><msup><mrow><mi>σ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">（</mo><mi>A</mi><mo stretchy="false">）</mo><mo>=</mo><mi mathvariant="normal">m</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>σ</mi><mo stretchy="false">（</mo><mi>A</mi><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422679&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422678&type= 27.94000053 3.72533321 , <math display="block" id="M157"><msup><mrow><mi>ρ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">(</mo><mi>A</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="normal">m</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">n</mi><mtext> </mtext><mi>ρ</mi><mo stretchy="false">(</mo><mi>A</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422681&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422680&type= 28.95599937 3.97933340 3) 对于图 G ( p , q ),若其存在EMTL，边幻和常数为 k ,且包含一个具有 n 个顶点的完全子图 H , <math id="M158"><msub><mrow><mi>u</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422683&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422682&type= 3.04799986 3.55599999 , <math id="M159"><msub><mrow><mi>u</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422685&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422684&type= 3.04799986 3.55599999 ,…, <math id="M160"><msub><mrow><mi>u</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422687&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422686&type= 3.04799986 3.55599999 分别为 H 的 n 个顶点， <math id="M161"><msub><mrow><mi>a</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>=</mo><mi>f</mi><mo stretchy="false">(</mo><msub><mrow><mi>u</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422689&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422688&type= 15.32466698 4.65666676 。假定 <math id="M162"><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo><</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo><</mo><mo>…</mo><mo><</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422691&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422690&type= 27.77066803 3.72533321 ,则 <math id="M163"><mi>A</mi><mo>=</mo><mo stretchy="false">（</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo>,</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422693&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422692&type= 28.61733246 4.48733330 为一个长度为 n 的Sidon序列。 <math display="block" id="M164"><mi>f</mi><mo stretchy="false">（</mo><msub><mrow><mi>u</mi></mrow><mrow><mi>n</mi></mrow></msub><msub><mrow><mi>u</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow></msub><mo stretchy="false">）</mo><mo>=</mo><mi>k</mi><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422695&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422694&type= 40.38600159 4.91066647 又 <math id="M165"><mi>f</mi><mo stretchy="false">（</mo><msub><mrow><mi>u</mi></mrow><mrow><mi>n</mi></mrow></msub><msub><mrow><mi>u</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow></msub><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422697&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422696&type= 14.81666660 4.91066647 为标号 <math display="block" id="M166"><mi>k</mi><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow></msub><mo>≥</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422699&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422698&type= 27.85533333 4.14866638 同理 <math display="block" id="M167"><mi>f</mi><mo stretchy="false">（</mo><msub><mrow><mi>u</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msub><mrow><mi>u</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo stretchy="false">）</mo><mo>=</mo><mi>k</mi><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422701&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422700&type= 33.35866928 4.91066647 又 <math id="M168"><mi>f</mi><mo stretchy="false">（</mo><msub><mrow><mi>u</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><msub><mrow><mi>u</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422703&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422702&type= 11.26066685 4.91066647 为标号 <math display="block" id="M169"><mi>k</mi><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo>≤</mo><mi>p</mi><mo>+</mo><mi>q</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422705&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422704&type= 30.98800087 4.82599974 由（4）和（5）式得 <math display="block" id="M170"><mtable><mtr><mtd><mi>p</mi><mo>+</mo><mi>q</mi><mo>≥</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>+</mo><msub><mrow><mi>a</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow></msub><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>-</mo><msub><mrow><mi>a</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo>+</mo><mn mathvariant="normal">1</mn><mo>=</mo></mtd></mtr><mtr><mtd><mi>ρ</mi><mo stretchy="false">（</mo><mi>A</mi><mo stretchy="false">）</mo><mo>≥</mo><msup><mrow><mi>ρ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">（</mo><mi>A</mi><mo stretchy="false">）</mo></mtd></mtr></mtable></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422707&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422706&type= 54.10200119 9.65199947 从而得出,图 G ( p , q )若包含一个具有 n 个顶点的完全子图，且其具有EMTL,则 p + q 至少为 <math id="M171"><msup><mrow><mi>ρ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">（</mo><mi>n</mi><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422709&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422708&type= 7.95866680 4.23333359 ，即：当 <math id="M172"><mi>p</mi><mo>+</mo><mi>q</mi><mo><</mo><msup><mrow><mi>ρ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">（</mo><mi>n</mi><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422711&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422710&type= 21.16666603 4.23333359 时，图 G 为NEMTL图。 4) 文献[ 14 14 ]已证明： 当 <math id="M173"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">4</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422713&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422712&type= 8.55133343 3.30199981 时, <math id="M174"><msup><mrow><mi>ρ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">（</mo><mi>A</mi><mo stretchy="false">）</mo><mo>≥</mo><mn mathvariant="normal">2</mn><msup><mrow><mi>σ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">(</mo><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422715&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422714&type= 30.64933395 4.23333359 （7） 当 <math id="M175"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">7</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422717&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422716&type= 8.55133343 3.30199981 时， <math id="M176"><msup><mrow><mi>σ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>≥</mo><mn mathvariant="normal">4</mn><mo>+</mo><msubsup><mrow><mi>C</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422719&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422718&type= 27.17800140 4.74133348 （8） 定理3 当 <math id="M177"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">8</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422721&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422720&type= 8.55133343 3.30199981 ， <math id="M178"><mi>m</mi><mo>≤</mo><mfrac><mrow><mn mathvariant="normal">17</mn></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac><mo>+</mo><mfrac><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">4</mn></mrow></mfrac><mo stretchy="false">(</mo><msup><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mo>-</mo><mn mathvariant="normal">11</mn><mi>n</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422723&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422722&type= 37.08399963 7.28133297 ),且 m , n 均为正整数时， <math id="M179"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422725&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422724&type= 13.12333298 3.64066648 为NEMTL图。 证 1) <math id="M180"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422727&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422726&type= 13.12333298 3.64066648 如 图1 图1 (a)。设 <math id="M181"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422729&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422728&type= 3.97933340 3.55599999 的顶点集为 <math id="M182"><mfenced open="{" close="}" separators="|"><mrow><msub><mrow><mi>u</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo>,</mo><msub><mrow><mi>u</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mrow><mi>u</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422731&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422730&type= 21.33599854 4.65666676 , <math id="M183"><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422733&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422732&type= 4.23333359 3.64066648 的顶点集为 <math id="M184"><mfenced open="{" close="}" separators="|"><mrow><msub><mrow><mi>v</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo>,</mo><msub><mrow><mi>v</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>m</mi></mrow></msub></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422735&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422734&type= 21.67466736 4.65666676 。当 <math display="block" id="M185"><mfenced open="|" close="|" separators="|"><mrow><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo>+</mo><mfenced open="|" close="|" separators="|"><mrow><mi>E</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext> </mtext><mo>⊳</mo><mtext> </mtext><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo><</mo><msup><mrow><mi>ρ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">（</mo><mi>n</mi><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422737&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422736&type= 63.07666779 4.57200003 时， <math id="M186"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422739&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422738&type= 13.12333298 3.64066648 为NEMTL图。即 <math display="block" id="M187"><mo stretchy="false">（</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo>-</mo><mn mathvariant="normal">2</mn><mo stretchy="false">）</mo><mo>+</mo><msubsup><mrow><mi>C</mi></mrow><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mo>+</mo><mo stretchy="false">(</mo><mi>m</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">)</mo><mo><</mo><msup><mrow><mi>ρ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">（</mo><mi>n</mi><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422741&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422740&type= 56.72666550 5.07999992 结合（7）和（8）式知： 当 <math id="M188"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">4</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422743&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422742&type= 8.55133343 3.30199981 时, <math display="block" id="M189"><mo stretchy="false">（</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo>-</mo><mn mathvariant="normal">2</mn><mo stretchy="false">）</mo><mo>+</mo><msubsup><mrow><mi>C</mi></mrow><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mo>+</mo><mo stretchy="false">(</mo><mi>m</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">)</mo><mo><</mo><mn mathvariant="normal">2</mn><msup><mrow><mi>σ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">（</mo><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422745&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422744&type= 65.19332886 4.91066647 当 <math id="M190"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">8</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422747&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422746&type= 8.55133343 3.30199981 时， <math display="block" id="M191"><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo>-</mo><mn mathvariant="normal">2</mn><mo stretchy="false">)</mo><mo>+</mo><msubsup><mrow><mi>C</mi></mrow><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mo>+</mo><mo stretchy="false">(</mo><mi>m</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">)</mo><mo><</mo><mn mathvariant="normal">2</mn><mo stretchy="false">(</mo><mn mathvariant="normal">4</mn><mo>+</mo><msubsup><mrow><mi>C</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">2</mn></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422749&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422748&type= 68.91867065 4.91066647 化简得： <math id="M192"><mi>m</mi><mo><</mo><mfrac><mrow><mn mathvariant="normal">17</mn></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac><mo>+</mo><mfrac><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">4</mn></mrow></mfrac><mo stretchy="false">(</mo><msup><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mo>-</mo><mn mathvariant="normal">11</mn><mi>n</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422751&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422750&type= 37.08399963 7.28133297 )。故当 <math id="M193"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">8</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422753&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422752&type= 8.55133343 3.30199981 ， <math id="M194"><mi>m</mi><mo><</mo><mfrac><mrow><mn mathvariant="normal">17</mn></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac><mo>+</mo><mfrac><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">4</mn></mrow></mfrac><mo stretchy="false">(</mo><msup><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mo>-</mo><mn mathvariant="normal">11</mn><mi>n</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422755&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422754&type= 37.08399963 7.28133297 ),且 m , n 均为正整数时, <math id="M195"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422757&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422756&type= 13.12333298 3.64066648 为NEMTL图。 2) 图6 图6 中的零散点表示 m , n 的解， <math id="M196"><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422759&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422758&type= 4.23333359 3.64066648 为圈图，故 <math id="M197"><mi>m</mi><mo>≥</mo><mn mathvariant="normal">3</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422761&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422760&type= 9.56733322 3.30199981 时，函数图像才有意义；当 <math id="M198"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">13</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422763&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422762&type= 10.41399956 3.30199981 时略。 3) 图7 图7 为 <math id="M201"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422772&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422771&type= 13.12333298 3.64066648 满足定理3的部分NEMTL图示例。 证毕。 定理4 当 <math id="M202"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">8</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422781&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422780&type= 8.55133343 3.30199981 ， <math id="M203"><mi>m</mi><mo><</mo><mn mathvariant="normal">8</mn><mo>+</mo><mfrac><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">4</mn></mrow></mfrac><mo stretchy="false">(</mo><msup><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mo>-</mo><mn mathvariant="normal">11</mn><mi>n</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422783&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422782&type= 34.96733475 7.28133297 时， <math id="M204"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>∆</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422785&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422784&type= 10.83733368 3.89466667 为NEMTL图。 证 1) <math id="M205"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext> </mtext><mo>∆</mo><mtext> </mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422787&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422786&type= 12.44600010 3.89466667 如 图1 图1 (b)。设 <math id="M206"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422789&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422788&type= 3.97933340 3.55599999 的顶点集为 <math id="M207"><mfenced open="{" close="}" separators="|"><mrow><msub><mrow><mi>u</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo>,</mo><msub><mrow><mi>u</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mrow><mi>u</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422791&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422790&type= 21.33599854 4.65666676 , <math id="M208"><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422793&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422792&type= 3.81000018 3.64066648 的顶点集为 <math id="M209"><mfenced open="{" close="}" separators="|"><mrow><msub><mrow><mi>v</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo>,</mo><msub><mrow><mi>v</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mrow><mi>v</mi></mrow><mrow><mi>m</mi></mrow></msub></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422795&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422794&type= 21.67466736 4.65666676 。当 <math display="block" id="M210"><mfenced open="|" close="|" separators="|"><mrow><mi>V</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>∆</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo>+</mo><mfenced open="|" close="|" separators="|"><mrow><mi>E</mi><mo stretchy="false">（</mo><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>∆</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub><mo stretchy="false">）</mo></mrow></mfenced><mo><</mo><msup><mrow><mi>ρ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">（</mo><mi>n</mi><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422797&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422796&type= 57.57333374 4.57200003 时， <math id="M211"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>∆</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422799&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422798&type= 10.83733368 3.89466667 为NEMTL图。即 <math display="block" id="M212"><mo stretchy="false">（</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">）</mo><mo>+</mo><mo stretchy="false">(</mo><msubsup><mrow><mi>C</mi></mrow><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mo>+</mo><mi>m</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">)</mo><mo><</mo><msup><mrow><mi>ρ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">（</mo><mi>n</mi><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422801&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422800&type= 56.55733490 5.07999992 又结合（7）和（8）式知： 当 <math id="M215"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">4</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422803&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422802&type= 8.55133343 3.30199981 时, <math display="block" id="M216"><mo stretchy="false">（</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">）</mo><mo>+</mo><mo stretchy="false">（</mo><msubsup><mrow><mi>C</mi></mrow><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mo>+</mo><mi>m</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">）</mo><mo><</mo><mn mathvariant="normal">2</mn><msup><mrow><mi>σ</mi></mrow><mrow><mi mathvariant="normal">*</mi></mrow></msup><mo stretchy="false">（</mo><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">）</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422805&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422804&type= 64.43133545 4.57200003 当 <math id="M217"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">8</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422807&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422806&type= 8.55133343 3.30199981 时， <math display="block" id="M218"><mo stretchy="false">（</mo><mi>n</mi><mo>+</mo><mi>m</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">）</mo><mo>+</mo><mo stretchy="false">(</mo><msubsup><mrow><mi>C</mi></mrow><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mo>+</mo><mi>m</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">)</mo><mo><</mo><mn mathvariant="normal">2</mn><mo stretchy="false">(</mo><mn mathvariant="normal">4</mn><mo>+</mo><msubsup><mrow><mi>C</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">2</mn></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422809&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422808&type= 67.31000519 4.91066647 化简得： <math id="M219"><mi>m</mi><mo><</mo><mn mathvariant="normal">8</mn><mo>+</mo><mfrac><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">4</mn></mrow></mfrac><mo stretchy="false">(</mo><msup><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mo>-</mo><mn mathvariant="normal">11</mn><mi>n</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422811&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422810&type= 33.44333649 7.28133297 )。故当 <math id="M220"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">8</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422813&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422812&type= 8.55133343 3.30199981 ， <math id="M221"><mi>m</mi><mo><</mo><mn mathvariant="normal">8</mn><mo>+</mo><mfrac><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">4</mn></mrow></mfrac><mo stretchy="false">(</mo><msup><mrow><mi>n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mo>-</mo><mn mathvariant="normal">11</mn><mi>n</mi><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422815&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422814&type= 34.96733475 7.28133297 时， <math id="M222"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>∆</mo><mtext> </mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422817&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422816&type= 11.59933376 3.89466667 为NEMTL图成立。 2) 图8 图8 中的零散点表示 m , n 的可能取值， <math id="M223"><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422819&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422818&type= 3.81000018 3.64066648 为星图，故 <math id="M224"><mi>m</mi><mo>≥</mo><mn mathvariant="normal">2</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422821&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422820&type= 9.56733322 3.30199981 时，函数图像才有意义；当 <math id="M225"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">13</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422823&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422822&type= 10.41399956 3.30199981 时略。 3) 图9 图9 为 <math id="M229"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>∆</mo><mtext> </mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422834&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422833&type= 11.59933376 3.89466667 满足定理3的部分NEMTL图示例。 证毕。 从定理3和4可知，当 <math id="M230"><mi>n</mi><mo>≥</mo><mn mathvariant="normal">8</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422843&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422842&type= 8.55133343 3.30199981 时，联图才满足NEMTL的条件表达式，通过对9个点以内的所有图执行EMTL算法，得到了这两种联图当 <math id="M231"><mi>n</mi><mo><</mo><mn mathvariant="normal">8</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422845&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422844&type= 8.55133343 2.79399991 时，部分图也为NEMTL，如 图10 图10 所示。由于其并没有具体规律，故不用定理列出。 4　 结 语 1 本文设计了一种EMTL算法，得到了9个点内所有NEMTL图。通过分析得到了定理1和定理2，同时提出猜测1和猜测2，并发现大部分NEMTL图均为对称图形。最后，通过引入Sidon序列，证明了当 n 和 m 满足某些条件时，联图 <math id="M234"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>⊳</mo><msub><mrow><mi>C</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422850&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422849&type= 13.12333298 3.64066648 和 <math id="M235"><msub><mrow><mi>K</mi></mrow><mrow><mi>n</mi></mrow></msub><mtext> </mtext><mo>∆</mo><mtext> </mtext><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422852&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422851&type= 12.44600010 3.89466667 为非边幻和图，并对 <math id="M236"><mi>n</mi><mo><</mo><mn mathvariant="normal">8</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422854&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422853&type= 8.55133343 2.79399991 时，Sidon序列无法证明的NEMTL联图做了补充。 参考文献 BLOOM G S , GOLOMB S W . Applications of numbered undirected graphs [J]. Proceedings of the IEEE , 1977 , 65 ( 4 ): 562 - 570 . DOI: 10.1109/PROC.1977.10517 http://dx.doi.org/10.1109/PROC.1977.10517 . Applications of numbered undirected graphs BLOOM G S , GOLOMB S W . Numbered complete graphs , unusual rulers , and assorted applications [C]// Theory and Applications of Graphs（LNM 642） . Berlin ： Springer , 1978 : 53 - 65 . DOI: 10.1007/BFb0070364 http://dx.doi.org/10.1007/BFb0070364 . assorted applications ARKUT I C , ARKUT R C , BASAK A . Topology constrained label switching for multicast routing [C]// Proceedings of the 8th IEEE Symposium on Computers and Communications . Washington D C : IEEE Computer Society , 2003 : 453 - 459 . DOI: 10.1109/ISCC.2003.1214160 http://dx.doi.org/10.1109/ISCC.2003.1214160 . Topology constrained label switching for multicast routing SHIU W C , LAM P C B , CHENG H L . Supermagic labeling of an s-duplicate of K <math id="M237"><msub><mrow/><mrow><mi>n</mi><mo>,</mo><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422856&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=3422855&type= 2.96333337 3.30199981 [J]. Congressus Numerantium , 2000 , 146 : 119 - 124 . Supermagic labeling of an s-duplicate of Kn,n LIN Y , MILLER M , SIMANJUNTAK R . Edge-magic total labelings of wheels, fans and friendship graphs [J]. Bulletin of the ICA , 2002 , 35 : 89 - 98 . Edge-magic total labelings of wheels, fans and friendship graphs FIGUEROA-CENTENO R M , ICHISHIMA R , MUNTANER-BATLE F A . The place of super edge-magic labelings among other classes of labelings [J]. Discrete Mathematics , 2001 , 231 ( 1-3 ): 153 - 168 . DOI: 10.1016/S0012-365X(00)00314-9 http://dx.doi.org/10.1016/S0012-365X(00)00314-9 . The place of super edge-magic labelings among other classes of labelings FIGUEROA-CENTENO R M , ICHISHIMA R , MUNTANER-BATLE F A . On super edge-magic graphs [J]. Ars Comb , 2002 , 64 : 81 - 95 . On super edge-magic graphs CRAFT D , TESAR E H . On a question by Erdős about edge-magic graphs [J]. Discrete Mathematics , 1999 , 207 ( 1-3 ): 271 - 276 . DOI: 10.1016/S0012-365X(99)00110-7 http://dx.doi.org/10.1016/S0012-365X(99)00110-7 . On a question by Erdős about edge-magic graphs CHEN Z B . On super edge-magic graphs [J]. Journal of Combinatorial Mathematics and Combinatorial Computing , 2001 , 38 : 55 - 64 . On super edge-magic graphs RINGEL G , LLADO A S , SERRA O . Another tree conjecture [J]. Bull Inst Combin Appl , 1996 , 18 : 83 - 85 . Another tree conjecture MCKAY B D , PIPERNO A . Practical graph isomorphism, Ⅱ [J]. Journal of Symbolic Computation , 2014 , 60 : 94 - 112 . DOI： 10.1016/j.jsc.2013.09.003 http://dx.doi.org/10.1016/j.jsc.2013.09.003 . Practical graph isomorphism, Ⅱ GALLIAN J A . A survey: Recent results, conjectures, and open problems in labeling graphs [J]. Journal of Graph Theory , 1989 , 13 ( 4 ): 491 - 504 . DOI： 10.1002/jgt.3190130410 http://dx.doi.org/10.1002/jgt.3190130410 . A survey: Recent results, conjectures, and open problems in labeling graphs KOTZIG A , ROSA A . Magic valuations of finite graphs [J]. Canadian Mathematical Bulletin , 1970 , 13 ( 4 ): 451 - 461 . DOI： 10.4153/CMB-1970-084-1 http://dx.doi.org/10.4153/CMB-1970-084-1 . Magic valuations of finite graphs MARR A M , WALLIS W D . Magic Graphs [M]. 2nd Ed . Boston ： Birkhäuser , 2012 . Magic Graphs 10.14188/j.1671-8836.2019.0216 O157.5 A 1671-8836（2020）03-0237-07 GU Yanbo,LI Jingwen,SHAO Shuhong, et al .Some Theorems and Proofs of Non-Edge-Magic Total Labeling Graphs [J]. J Wuhan Univ （ Nat Sci Ed ）,2020,66(3):237-243. DOI: 10.14188/j.1671-8836.2019.0216 http://dx.doi.org/10.14188/j.1671-8836.2019.0216 (Ch). GU Yanbo,LI Jingwen,SHAO Shuhong,et al.Some Theorems and Proofs of Non-Edge-Magic Total Labeling Graphs [J].J Wuhan Univ（Nat Sci Ed）,2020,66(3):237-243. DOI:10.14188/j.1671-8836.2019.0216(Ch). 顾彦波,李敬文,邵淑宏, 等.非边幻和图的若干定理及证明[J].武汉大学学报（理学版）,2020,66(3):237-243. DOI:10.14188/j.1671-8836.2019.0216 顾彦波,李敬文,邵淑宏, 等.非边幻和图的若干定理及证明[J].武汉大学学报（理学版）,2020,66(3):237-243. DOI:10.14188/j.1671-8836.2019.0216 国家自然科学基金（11461038） 2019-07-11 2020-06-24 2020-09-30 武汉大学学报（理学版） 3 66