徐美進，劉春峰，高 洋

一類圖的優(yōu)美標號與序列標號

徐美進1，劉春峰2，高 洋3

（1.遼寧工業(yè)大學 理學院，遼寧 錦州 121001；2.中國人民政治協(xié)商會議遼寧省錦州市委員會，遼寧 錦州 121001；3.沈陽城市建設(shè)學院 基礎(chǔ)教研部，遼寧 沈陽 110167）

研究了圖的標號問題，通過圖的運算以及關(guān)聯(lián)關(guān)系構(gòu)造出一個新的圖類P()()，利用函數(shù)對應(yīng)關(guān)系給出了該類圖P()()對應(yīng)的優(yōu)美標號和序列標號，并分多種情況加以討論說明，從而證明了該類圖是優(yōu)美圖和序列圖。

優(yōu)美圖；序列圖；頂點標號

1 預備知識

圖P(s)()如圖1所示。

圖1 圖Pm(s)(n)

2 定理及證明

證明 分兩種情況證明定理1。

情況1≡0(mod2)

定義圖P(s)()的頂點標號如式(1)所示。

下面驗證是圖P(s)()的優(yōu)美標號。

(1)圖P(s)()中不同的點，其標號不同。設(shè)

(2)最大最小為

(3)圖P(s)()中若邊不同，則其標號不同。

由(1)式，有

假設(shè)

由上述可知是圖P(s)()的一個優(yōu)美標號，圖P(s)()是優(yōu)美圖。

情況2≡1(mod2)

定義圖P(s)()的頂點標號如式(2)所示。

在情況2中，可與情況1同樣驗證是圖P(s)()的一個優(yōu)美標號，圖P(s)()是優(yōu)美圖。

定理1證畢。

圖2和圖3給出了圖3(2)(4)和圖4(2)(3)的優(yōu)美標號。

圖2 圖P3(2)(4)的優(yōu)美標號

圖3 圖P4(2)(3)的優(yōu)美標號

定理2 若(＞1)、和是正整數(shù)，則圖P(s)()是序列圖。

證明 分兩種情況證明定理2。

情況1≡0(mod2)

(1)圖P(s)()中若點不同，其則標號亦不相同。設(shè)

(3)圖P(s)()中若邊不同，其則標號亦不相同。

根據(jù)式(3)，有

假設(shè)

于是，有

由上述可知是圖P(s)()的一個序列標號，圖P(s)()是序列圖。

情況2≡1(mod2)

在情況2中，可與情況1同樣驗證是圖P(s)()的一個序列標號，圖P(s)()是序列圖。

定理2證畢。

圖4和圖5給出了圖4(1)(4)和2(3)(3)圖的序列標號。

圖4 圖P4(1)(4)的序列標號

圖5 圖P2(3)(3)的序列標號

由定理1及定理2，有如下推論。

推論1[10]完全二分圖K,n是優(yōu)美圖。

推論2[10]路、星圖和扇圖是優(yōu)美圖和序列圖。

推論3 若(＞1)、和是正整數(shù)，則圖P(s)()是調(diào)和圖。

3 結(jié)束語

本文討論了圖的優(yōu)美標號及序列標號問題。通過圖的運算關(guān)系構(gòu)造出一類新的圖P(s)()，給出其具體的優(yōu)美標號及序列標號，并給出嚴格證明。

[1] RINGEL G. Problem 25 in theory of Graph of Graph and its application[C]. Smolenice : Proc. Symposium Smolenice, 1963: 162-167.

[2] ROSA A. On certain Valuations of the Vertices of graphs[J]. Theory of Graphs, 1966, 7(3): 349-355.

[3] GOLOMB S W. How to Numbe a Graph[M]. New York: Graph Theory and Computing, Academic Press, 1972.

[4]GALLIAN J A. A dynamic surverv of graph labeling[J]. The electronic journal of combinatorics, 2013, 16: 33-69.

[5] 梁懷學, 劉春峰. 關(guān)于圖的K-優(yōu)美性[J]. 東北師大學報, 1991, 23(1): 41-44.

[6] 劉春峰, 趙連昌.重四角鮮人掌圖的優(yōu)美性和序列性[J]. 吉林師范大學學報, 2006, 27(2): 4-6.

[7] 劉春峰, 林躍進, 趙連昌. 路及其相關(guān)圖的序列性[J]. 數(shù)學理論與應(yīng)用, 2006, 26(4): 17-20.

[8] 劉春峰, 朱振廣. 圖P×C和(,)的序列性[J]. 數(shù)學的實踐與認識, 2007, 10(37): 162-165.

[9] 劉春峰. 鏈路P()的優(yōu)美性和序列性[J]. 理論數(shù)學, 2018, 8(2): 723-729.

[10] 馬克杰. 優(yōu)美圖[M]. 北京: 北京大學出版社, 1991.

A Class of Graceful and Sequential Graph Labeling

XU Mei-jin1, LIU Chun-feng2, GAO Yang3

（1. College of Science, Liaoning University of Technology, Jinzhou 121001, China;2. Jinzhou Municipal Committee of the Political Consultative Conference, Jinzhou 121001, China;3. Basic Teaching and Research Department, Shenyang Urban Construction University, Shenyang, 110167, China）

In this paper, the graph labeling is studied. A new class of graphP(s)()is constructed by graph operations and association relations. The corresponding graceful labeling and sequential labeling are determined by the functional correspondence relation and considered different scenario, which proved that this class of graphP(s)()is indeed a graceful and sequential graph.

graceful graph; sequential graph; vertex labeling

O157.5

A

1674-3261(2021)04-0269-05

10.15916/j.issn1674-3261.2021.04.013

2020-03-13

遼寧省聯(lián)合基金項目(SY2016012)

徐美進(1965-)，女，山東文登人，教授，碩士。

責任編校：陳 明