蒲公英圖的超邊優(yōu)美標(biāo)號

賈慧羨，張靜

（石家莊郵電職業(yè)技術(shù)學(xué)院基礎(chǔ)部，河北石家莊050021）

蒲公英圖的超邊優(yōu)美標(biāo)號

賈慧羨，張靜

（石家莊郵電職業(yè)技術(shù)學(xué)院基礎(chǔ)部，河北石家莊050021）

1994年，Mitchem和Simoson在研究標(biāo)號圖的問題時(shí)，提出了超邊優(yōu)美圖的概念。在隨后的研究中，一些圖被證明具有超邊優(yōu)美性質(zhì)，同時(shí)關(guān)于超邊優(yōu)美圖的一些猜想也被提出。本文利用遞歸方法構(gòu)造了蒲公英圖的超邊優(yōu)美標(biāo)號，并證明了蒲公英圖是超邊優(yōu)美圖。

超邊優(yōu)美；蒲公英圖；邊符號矩陣

0 引言

1985年，Lo［1］首次提出邊優(yōu)美圖（即1-邊優(yōu)美圖）的概念，并給出邊優(yōu)美圖的必要條件。圖G=(V，E)是一個(gè)(p，q)圖，如果存在一個(gè)雙射f:E→{1，2，…，q}，使得它的導(dǎo)出映射：也是一個(gè)雙射，則稱圖G=(V，E)是邊優(yōu)美的。隨后圖的邊優(yōu)美標(biāo)號問題得到廣泛研究［2-4］，但至今仍有很多問題尚未解決，其中包括著名的Lee猜想［5］：所有奇數(shù)階的樹都是邊優(yōu)美的。有關(guān)邊優(yōu)美性的更多結(jié)論可參考文獻(xiàn)［6］。

1994年，Mitchem和Simoson［7］在證明上述猜想［5］時(shí)，提出了超邊優(yōu)美圖的概念。超邊優(yōu)美圖和邊優(yōu)美圖的概念有所不同。Mitchem和Simoson［7］證明階圖C62是超邊優(yōu)美圖，但不是邊優(yōu)美圖，Shiu［8］指出完全圖K4是邊優(yōu)美圖，但不是超邊優(yōu)美圖。超邊優(yōu)美圖的研究還處于起步階段，研究成果十分有限，文獻(xiàn)［6，8-9］給出了一些結(jié)論。

本文研究蒲公英圖的超邊優(yōu)美性。有關(guān)蒲公英圖的研究，文獻(xiàn)［10］討論了蒲公英圖的k-邊優(yōu)美指標(biāo)集。

1 基本概念

定義1若令

稱(p，q)-圖G是超邊優(yōu)美圖。如果存在一個(gè)雙射f：E→Q，使得它的導(dǎo)出映射也是一個(gè)雙射，則稱f為圖G的超邊優(yōu)美標(biāo)號，集合P和Q相應(yīng)地稱為圖G的頂點(diǎn)值集和邊標(biāo)號集。

定義2設(shè)T是一個(gè)含有(m+1)個(gè)頂點(diǎn)的星，σi是一個(gè)含有(ri+1)個(gè)頂點(diǎn)的星，取m個(gè)這樣的星σ1，σ2，…，σm，它們的中心分別與T的m個(gè)懸掛點(diǎn)粘接起來生成的圖稱為蒲公英圖，記作PG(m;r1，r2，…，rm)型圖（見圖1）。特別地，當(dāng)r1=r2=…=rm=r時(shí)，將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)有個(gè)頂點(diǎn)和條邊。其中v0稱為中心，vi(i=1，2，…，m)稱為中間結(jié)點(diǎn)，vij(i=1，2，…，m；j=1，2，…，ri)稱為懸掛點(diǎn)。它的特例Trm有 ((m+1)r+1)個(gè)頂點(diǎn)，有(m+1)r條邊。

本文主要研究了蒲公英圖的超邊優(yōu)美性。對一般的蒲公英圖PG(m;r1，r2，…，rm)，證明r1，r2，…，rm同為奇數(shù)或m，r1，r2，…，rm同為偶數(shù)時(shí)，它為超邊優(yōu)美圖，進(jìn)而，證明r為奇數(shù)，或者m，r同為偶數(shù)時(shí)，圖Tmr是超邊優(yōu)美圖。

令a，m是整數(shù)，m＞0，為方便起見，采用記號：

2 主要結(jié)果及其證明

引理1如果PG(m;r1，r2，…，rm)（r1，r2，…，rm同為奇數(shù)，或m，r1，r2，…，rm同為偶數(shù)）是超邊優(yōu)美圖，σ′是一個(gè)含有3個(gè)頂點(diǎn)的星，將它的中心與PG(m;r1，r2，…，rm)中任意一個(gè)中間結(jié)點(diǎn)粘接起來，生成的圖PG(m;r1，…，ri+2，…，rm)一定是超邊優(yōu)美圖。

證明令PG(m;r1，r2，…，rm)頂點(diǎn)值集為P，邊標(biāo)號集為Q。

情形1：r1，r2，…，rm同為奇數(shù)。

情形2：m，r1，r2，…，rm同為偶數(shù)。

因此，當(dāng)r1，r2，…，rm同為奇數(shù)或m，r1，r2，…，rm同為偶數(shù)時(shí)，都有頂點(diǎn)數(shù)p為奇數(shù)，邊數(shù)q為偶數(shù)。因?yàn)镻G(m;r1，…，ri+2，…，rm)比PG(m;r1，r2，…，rm)多2條邊，則其邊值集為構(gòu)造PG(m;r1，…，ri+2，…，rm)中的邊映射f′如下：

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

定理1Tm1是超邊優(yōu)美圖。

證明Tm1含有(2m+1)個(gè)頂點(diǎn)，2m條邊。頂點(diǎn)值集P=[-m，m]，邊標(biāo)號集Q=[-m，-1]∪[1，m]。定義邊符號矩陣

情形1：m為偶數(shù)。

定義邊映射

從邊符號矩陣可以看出，所有邊的f值恰充滿集合[-m，-1]∪[1，m]，f:E→Q是一個(gè)雙射。

現(xiàn)在討論各頂點(diǎn)標(biāo)號，各點(diǎn)的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，故所有點(diǎn)的f+值恰充滿集合[-m，m]，f+:V→P是一個(gè)雙射。

情形2：m為奇數(shù)。

定義邊映射

對于剩余的邊，標(biāo)號規(guī)則為

故f確是Tm1的超邊優(yōu)美雙射。

定理3蒲公英圖PG(m;r1，r2，…，rm)（r1，r2，…，rm同為奇數(shù)）是超邊優(yōu)美圖。

證明由定理2知，Tm1是超邊優(yōu)美圖，在它的懸掛點(diǎn)上成對地添加邊，進(jìn)而重復(fù)運(yùn)用引理1，即可得結(jié)論。

定理4r＞0為奇數(shù)時(shí)，蒲公英圖Tmr是超邊優(yōu)美圖。

證明此定理為定理3的推論，故得證。

定理5m為偶數(shù)時(shí)，Tm0是超邊優(yōu)美圖。

證明T0m即為星圖st(m)，它有(m+1)個(gè)頂點(diǎn)，有m條邊。頂點(diǎn)值集，邊標(biāo)號集

定義邊映射如下：

下面討論各頂點(diǎn)標(biāo)號。

所有點(diǎn)的f+值恰充滿集合，故f確是T0m的超邊優(yōu)美雙射。

定理6蒲公英圖PG(m;r1，r2，…，rm)（m，r1，r2，…，rm同為偶數(shù)）是超邊優(yōu)美圖。

證明由定理5知，T0m是超邊優(yōu)美圖，在它的懸掛點(diǎn)上成對地添加邊，進(jìn)而重復(fù)運(yùn)用引理1，可得結(jié)論。

定理7m＞0，r≥0同為偶數(shù)時(shí)，蒲公英圖Trm是超邊優(yōu)美圖。

證明此定理為定理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-邊優(yōu)美指標(biāo)集［J］.河北師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，36（2）：16-18.

（責(zé)任編輯：強(qiáng)士端）

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

河北省教育廳資助科研項(xiàng)目（Z2013057）

賈慧羨（1979—），女，講師，碩士，研究方向：組合數(shù)學(xué)。