蒲公英图的超边优美标号

贾慧羡，张静

（石家庄邮电职业技术学院基础部，河北石家庄050021）

蒲公英图的超边优美标号

贾慧羡，张静

（石家庄邮电职业技术学院基础部，河北石家庄050021）

1994年，Mitchem和Simoson在研究标号图的问题时，提出了超边优美图的概念。在随后的研究中，一些图被证明具有超边优美性质，同时关于超边优美图的一些猜想也被提出。本文利用递归方法构造了蒲公英图的超边优美标号，并证明了蒲公英图是超边优美图。

超边优美；蒲公英图；边符号矩阵

0 引言

1985年，Lo［1］首次提出边优美图（即1-边优美图）的概念，并给出边优美图的必要条件。图G=(V，E)是一个(p，q)图，如果存在一个双射f:E→{1，2，…，q}，使得它的导出映射：也是一个双射，则称图G=(V，E)是边优美的。随后图的边优美标号问题得到广泛研究［2-4］，但至今仍有很多问题尚未解决，其中包括著名的Lee猜想［5］：所有奇数阶的树都是边优美的。有关边优美性的更多结论可参考文献［6］。

1994年，Mitchem和Simoson［7］在证明上述猜想［5］时，提出了超边优美图的概念。超边优美图和边优美图的概念有所不同。Mitchem和Simoson［7］证明阶图C62是超边优美图，但不是边优美图，Shiu［8］指出完全图K4是边优美图，但不是超边优美图。超边优美图的研究还处于起步阶段，研究成果十分有限，文献［6，8-9］给出了一些结论。

本文研究蒲公英图的超边优美性。有关蒲公英图的研究，文献［10］讨论了蒲公英图的k-边优美指标集。

1 基本概念

定义1若令

称(p，q)-图G是超边优美图。如果存在一个双射f：E→Q，使得它的导出映射也是一个双射，则称f为图G的超边优美标号，集合P和Q相应地称为图G的顶点值集和边标号集。

定义2设T是一个含有(m+1)个顶点的星，σi是一个含有(ri+1)个顶点的星，取m个这样的星σ1，σ2，…，σm，它们的中心分别与T的m个悬挂点粘接起来生成的图称为蒲公英图，记作PG(m;r1，r2，…，rm)型图（见图1）。特别地，当r1=r2=…=rm=r时，将PG(m；r1，r2，…，rm)型图记作Trm(m＞0，r≥0)。

图1 蒲公英图PG(m;r1，r2，…，rm)Flg.1Dandelion graphPG(m;r1，r2，…，rm)

图PG(m;r1，r2，…，rm)有个顶点和条边。其中v0称为中心，vi(i=1，2，…，m)称为中间结点，vij(i=1，2，…，m；j=1，2，…，ri)称为悬挂点。它的特例Trm有 ((m+1)r+1)个顶点，有(m+1)r条边。

本文主要研究了蒲公英图的超边优美性。对一般的蒲公英图PG(m;r1，r2，…，rm)，证明r1，r2，…，rm同为奇数或m，r1，r2，…，rm同为偶数时，它为超边优美图，进而，证明r为奇数，或者m，r同为偶数时，图Tmr是超边优美图。

令a，m是整数，m＞0，为方便起见，采用记号：

2 主要结果及其证明

引理1如果PG(m;r1，r2，…，rm)（r1，r2，…，rm同为奇数，或m，r1，r2，…，rm同为偶数）是超边优美图，σ′是一个含有3个顶点的星，将它的中心与PG(m;r1，r2，…，rm)中任意一个中间结点粘接起来，生成的图PG(m;r1，…，ri+2，…，rm)一定是超边优美图。

证明令PG(m;r1，r2，…，rm)顶点值集为P，边标号集为Q。

情形1：r1，r2，…，rm同为奇数。

情形2：m，r1，r2，…，rm同为偶数。

因此，当r1，r2，…，rm同为奇数或m，r1，r2，…，rm同为偶数时，都有顶点数p为奇数，边数q为偶数。因为PG(m;r1，…，ri+2，…，rm)比PG(m;r1，r2，…，rm)多2条边，则其边值集为构造PG(m;r1，…，ri+2，…，rm)中的边映射f′如下：

1）保持PG(m;r1，r2，…，rm)中的边映射f；

定理1Tm1是超边优美图。

证明Tm1含有(2m+1)个顶点，2m条边。顶点值集P=[-m，m]，边标号集Q=[-m，-1]∪[1，m]。定义边符号矩阵

情形1：m为偶数。

定义边映射

从边符号矩阵可以看出，所有边的f值恰充满集合[-m，-1]∪[1，m]，f:E→Q是一个双射。

现在讨论各顶点标号，各点的f+值如下：

由（2）式，i∈[1，m]，f+(vi)∈{-(m-1)，-(m-3)，…，-3，-1，1，3，…，m-3，m-1}=[-(m-1)，-1]2∪[1，m-1]2，又由（3）式，f+(vi1)∈[-m，-2]2∪[2，m]2，故所有点的f+值恰充满集合[-m，m]，f+:V→P是一个双射。

情形2：m为奇数。

定义边映射

对于剩余的边，标号规则为

故f确是Tm1的超边优美双射。

定理3蒲公英图PG(m;r1，r2，…，rm)（r1，r2，…，rm同为奇数）是超边优美图。

证明由定理2知，Tm1是超边优美图，在它的悬挂点上成对地添加边，进而重复运用引理1，即可得结论。

定理4r＞0为奇数时，蒲公英图Tmr是超边优美图。

证明此定理为定理3的推论，故得证。

定理5m为偶数时，Tm0是超边优美图。

证明T0m即为星图st(m)，它有(m+1)个顶点，有m条边。顶点值集，边标号集

定义边映射如下：

下面讨论各顶点标号。

所有点的f+值恰充满集合，故f确是T0m的超边优美双射。

定理6蒲公英图PG(m;r1，r2，…，rm)（m，r1，r2，…，rm同为偶数）是超边优美图。

证明由定理5知，T0m是超边优美图，在它的悬挂点上成对地添加边，进而重复运用引理1，可得结论。

定理7m＞0，r≥0同为偶数时，蒲公英图Trm是超边优美图。

证明此定理为定理6的推论，故得证。

（References）

［1］LO S P.On edge-graceful labelings of graphs［J］.Congressus Numerantium，1985，50：231-241.

［2］LEE S M，MURTY G.On edge-graceful labelings of complete graphs-solutions of Lo's conjecture［J］.Congressum Numer⁃antum，1988，62：225-233.

［3］LEE S M，Seah E.On the edge-graceful（n，kn）-multigraphs conjecture［J］.Journal of Combinatorial Mathematics and Combinatorial Computing，1991，9：141-147.

［4］LEE S M，SEAH E，LO S P.On edge-graceful 2-regular graphs［J］.Journal of Combinatoric Mathematics and Combinator⁃ic Computing，1992，12：109-117.

［5］LEE S M.A conjecture on edge-graceful trees［J］.Scientia，1989，3：45-47.

［6］GALLIAN J A.A dynamic survey of graph labeling［J］.The Electronic Journal of Combinatorics，2011，16：1-219.

［7］MITCHEM J，SIMOSON A.On edge-graceful and super-edge-graceful graphs［J］.Ars Combinatoria，1994，37：97-111.

［8］SHIU W C.Super-edge-graceful labelings of some cubic graphs［J］.Acta Mathematica Sinica，2006，22：1621-1628.

［9］SHIU W C，LAM P B C.Super-edge-graceful labelings of multi-level wheel graphs，fan graphs and actinia graphs［J］.Con⁃gressus Numerantium，2005，174：49-63.

［10］贾慧羡，康庆德.蒲公英图Trm的k-边优美指标集［J］.河北师范大学学报：自然科学版，2012，36（2）：16-18.

（责任编辑：强士端）

Super-edge-graceful Labelings of Dandelion Graph

JIA Huixian，ZHANG Jing
（Basical Department，Shijiazhuang Post and Telecommunication Technical College，Shijiazhuang 050021，Hebei，China）

In 1994，Mitchem and Simoson introduced the notion of super edge-graceful graphs when they studied the problem of labeling graph.In the course of subsequent study，it was proven that some graphs were super edge-graceful and some conjections on super edge-graceful graphs were introduced.The super edge-graceful labelings of the dandelion graphs are constructed by recur⁃sion，and it is proven that dandelion graphs are super edge-graceful graphs.

super-edge-graceful；dandelion graph；edge sign matrix

O157

A

1673-0143（2014）04-0025-05

2014-05-08

河北省教育厅资助科研项目（Z2013057）

贾慧羡（1979—），女，讲师，硕士，研究方向：组合数学。