西南大学学报 (自然科学版)  2018, Vol. 40 Issue (12): 100-104.  DOI: 10.13718/j.cnki.xdzk.2018.12.016 0
 Article Options PDF Abstract Figures References 扩展功能 Email Alert RSS 本文作者相关文章 刘秀丽 欢迎关注西南大学期刊社

 $\lambda _2^T\left( {M\left( {{P_n}} \right)} \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 5\\ n + 1 \end{array}&\begin{array}{l} n = 3\\ n \ge 4 \end{array} \end{array}} \right.$

情形1    n=3.

 $\lambda _2^T\left( {M\left( {{P_n}} \right)} \right) \ge 5$

 $\lambda _2^T\left( {M\left( {{P_3}} \right)} \right) \ge 5$

 $f\left( w \right) = 2,f\left( {{v_1}} \right) = 4,f\left( {{v_2}} \right) = 0,f\left( {{v_3}} \right) = 1,$
 $f\left( {{{v'}_1}} \right) = 1,f\left( {{{v'}_2}} \right) = 5,f\left( {{{v'}_3}} \right) = 1,$
 $f\left( {{v_1}{v_2}} \right) = 2,f\left( {{v_2}{v_3}} \right) = 5,$
 $f\left( {{v_1}{{v'}_2}} \right) = 1,f\left( {{v_2}{{v'}_1}} \right) = 3,f\left( {{v_2}{{v'}_3}} \right) = 4,f\left( {{v_3}{{v'}_2}} \right) = 3,$
 $f\left( {w{{v'}_1}} \right) = 4,f\left( {w{{v'}_2}} \right) = 0,f\left( {w{{v'}_3}} \right) = 5.$

 $\lambda _2^T\left( {M\left( {{P_4}} \right)} \right) \ge 5$

 $\lambda _2^T\left( {M\left( {{P_3}} \right)} \right) = 5$

 $f\left( w \right) = 0,f\left( {{v_1}} \right) = 2,f\left( {{v_2}} \right) = 0,f\left( {{v_3}} \right) = 5,f\left( {{v_4}} \right) = 3,$
 $f\left( {{{v'}_1}} \right) = f\left( {{{v'}_2}} \right) = f\left( {{{v'}_3}} \right) = 1,f\left( {{{v'}_4}} \right) = 4,$
 $f\left( {{v_1}{v_2}} \right) = 5,f\left( {{v_2}{v_3}} \right) = 2,f\left( {{v_3}{v_4}} \right) = 0,$
 $f\left( {{v_1}{{v'}_2}} \right) = f\left( {{v_2}{{v'}_1}} \right) = 4,f\left( {{v_3}{{v'}_4}} \right) = 1,$
 $f\left( {{v_2}{{v'}_3}} \right) = f\left( {{v_3}{{v'}_2}} \right) = 3,f\left( {{v_4}{{v'}_3}} \right) = 5,$
 $f\left( {w{{v'}_1}} \right) = 3,f\left( {w{{v'}_2}} \right) = 5,f\left( {w{{v'}_3}} \right) = 4,f\left( {w{{v'}_4}} \right) = 2.$

 $\lambda _2^T\left( {M\left( {{P_n}} \right)} \right) \ge n + 1$

 $\lambda _2^T\left( {M\left( {{P_n}} \right)} \right) = n + 1$

 $f\left( w \right) = n + 1,f\left( {{v_i}} \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 0\\ 1 \end{array}&\begin{array}{l} i \equiv 1\left( {\bmod 2} \right)\\ i \equiv 0\left( {\bmod 2} \right) \end{array} \end{array}} \right.\;\;\;\;\;\;\;\;\;\;\;i = 1,2, \cdots ,n$
 $f\left( {{{v'}_1}} \right) = 2,f\left( {{{v'}_2}} \right) = 3,f\left( {{{v'}_i}} \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 0\\ 1 \end{array}&\begin{array}{l} i \equiv 1\left( {\bmod 2} \right)\\ i \equiv 0\left( {\bmod 2} \right) \end{array} \end{array}} \right.\;\;\;\;\;\;\;\;\;\;\;i = 3,4, \cdots ,n$
 $f\left( {w{{v'}_i}} \right) = i - 1\;\;\;\;\;\;\;i = 1,2, \cdots ,n$
 $f\left( {{v_i}{v_{i + 1}}} \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 3\\ 4 \end{array}&\begin{array}{l} i \equiv 1\left( {\bmod 2} \right)\\ i \equiv 0\left( {\bmod 2} \right) \end{array} \end{array}} \right.\;\;\;\;\;\;\;\;\;\;\;i = 1,2, \cdots ,n - 1$
 $f\left( {{v_i}{{v'}_{i + 1}}} \right) = n,f\left( {{v_{i + 1}}{{v'}_i}} \right) = n + 1\;\;\;\;\;\;\;\;\;\;\;i = 1,2, \cdots ,n - 1$

 $\lambda _2^T\left( {M\left( {{C_n}} \right)} \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 6\\ n + 1 \end{array}&\begin{array}{l} n = 3,4\\ n \ge 5 \end{array} \end{array}} \right.$

情形1    n=3.

 $\lambda _2^T\left( {M\left( {{C_3}} \right)} \right) \ge 5$

 $f\left( w \right) = 4,f\left( {{v_1}} \right) = 0,f\left( {{v_2}} \right) = 1,f\left( {{v_3}} \right) = 4,f\left( {{{v'}_1}} \right) = 5,f\left( {{{v'}_2}} \right) = 2,f\left( {{{v'}_3}} \right) = 6,$
 $f\left( {{v_1}{v_2}} \right) = 5,f\left( {{v_2}{v_3}} \right) = 6,f\left( {{v_3}{v_1}} \right) = 2,f\left( {{v_1}{{v'}_2}} \right) = 4,f\left( {{v_2}{{v'}_1}} \right) = 3,f\left( {{v_2}{{v'}_3}} \right) = 4,$
 $f\left( {{v_3}{{v'}_2}} \right) = 0,f\left( {{v_3}{{v'}_1}} \right) = 1,f\left( {{v_1}{{v'}_3}} \right) = 3,f\left( {w{{v'}_1}} \right) = 2,f\left( {w{{v'}_2}} \right) = 6,f\left( {w{{v'}_3}} \right) = 0.$

 $\lambda _2^T\left( {M\left( {{P_3}} \right)} \right) = 6$

 $\lambda _2^T\left( {M\left( {{C_4}} \right)} \right) \ge 5$

f(w)=0，则边wv1wv2wv3wv4只能标2，3，4，5，则点v1v2v3v4不能按(2，1)-全标号的定义给出标号，矛盾.

f(w)=5，则边wv1wv2wv3wv4只能标0，1，2，3，则点v1v2v3v4不能按(2，1)-全标号的定义给出标号，矛盾.

 $f\left( w \right) = 6,f\left( {{v_1}} \right) = f\left( {{v_3}} \right) = 0,f\left( {{v_2}} \right) = f\left( {{v_4}} \right) = 1,$
 $f\left( {{{v'}_1}} \right) = f\left( {{{v'}_3}} \right) = 0,f\left( {{{v'}_2}} \right) = 1,f\left( {{{v'}_4}} \right) = 3,$
 $f\left( {{v_1}{v_2}} \right) = f\left( {{v_3}{v_4}} \right) = 3,f\left( {{v_2}{v_3}} \right) = f\left( {{v_4}{v_1}} \right) = 4,$
 $f\left( {{v_1}{{v'}_2}} \right) = f\left( {{v_2}{{v'}_3}} \right) = f\left( {{v_3}{{v'}_4}} \right) = f\left( {{v_4}{{v'}_1}} \right) = 5,$
 $f\left( {{v_2}{{v'}_1}} \right) = f\left( {{v_3}{{v'}_2}} \right) = f\left( {{v_4}{{v'}_3}} \right) = f\left( {{v_1}{{v'}_4}} \right) = 6,$
 $f\left( {w{{v'}_1}} \right) = 2,f\left( {w{{v'}_2}} \right) = 3,f\left( {w{{v'}_3}} \right) = 4,f\left( {w{{v'}_4}} \right) = 1.$

 $\lambda _2^T\left( {M\left( {{C_n}} \right)} \right) \ge n + 1$

 $\lambda _2^T\left( {M\left( {{C_n}} \right)} \right) = n + 1$

(ⅰ)当n≡0(mod 2)时，

 $f\left( w \right) = n + 1,f\left( {{v_i}} \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 0\\ 1 \end{array}&\begin{array}{l} i \equiv 1\left( {\bmod 2} \right)\\ i \equiv 0\left( {\bmod 2} \right) \end{array} \end{array}} \right.\;\;\;\;\;\;\;\;\;\;\;i = 1,2, \cdots ,n$
 $f\left( {{{v'}_1}} \right) = 2,f\left( {{{v'}_2}} \right) = 3,f\left( {{{v'}_i}} \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 0\\ 1 \end{array}&\begin{array}{l} i \equiv 1\left( {\bmod 2} \right)\\ i \equiv 0\left( {\bmod 2} \right) \end{array} \end{array}} \right.\;\;\;\;\;\;\;\;\;\;\;i = 3,4, \cdots ,n$
 $f\left( {w{{v'}_i}} \right) = i - 1\;\;\;\;\;\;\;i = 1,2, \cdots ,n$
 $f\left( {{v_i}{v_{i + 1}}} \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 3\\ 4 \end{array}&\begin{array}{l} i \equiv 1\left( {\bmod 2} \right)\\ i \equiv 0\left( {\bmod 2} \right) \end{array} \end{array}} \right.\;\;\;\;\;\;\;\;\;\;\;i = 1,2, \cdots ,n,i + 1\left( {\bmod n} \right)$
 $f\left( {{v_i}{{v'}_{i + 1}}} \right) = n,f\left( {{v_{i + 1}}{{v'}_i}} \right) = n + 1\;\;\;\;\;\;\;\;\;\;\;i = 1,2, \cdots ,n,i + 1\left( {\bmod n} \right)$

(ⅱ)当n≡1(mod 2)时，

 $f\left( w \right) = n + 1,f\left( {{v_n}} \right) = 2,f\left( {{v_i}} \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 0\\ 1 \end{array}&\begin{array}{l} i \equiv 1\left( {\bmod 2} \right)\\ i \equiv 0\left( {\bmod 2} \right) \end{array} \end{array}} \right.\;\;\;\;\;\;\;\;\;\;\;i = 1,2, \cdots ,n - 1$
 $\begin{array}{*{20}{c}} {f\left( {{{v'}_1}} \right) = 3,f\left( {{{v'}_2}} \right) = 2,f\left( {{{v'}_i}} \right) = i - 3}&{i = 3,4, \cdots ,n} \end{array}$
 $\begin{array}{*{20}{c}} {f\left( {w{{v'}_1}} \right) = 1,f\left( {w{{v'}_2}} \right) = 0,f\left( {w{{v'}_i}} \right) = i - 1}&{i = 3,4, \cdots ,n} \end{array}$
 $f\left( {{v_n}{v_1}} \right) = n + 1,f\left( {{v_i}{v_{i + 1}}} \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 3\\ 4 \end{array}&\begin{array}{l} i \equiv 1\left( {\bmod 2} \right)\\ i \equiv 0\left( {\bmod 2} \right) \end{array} \end{array}} \right.\;\;\;\;\;\;\;\;\;\;\;i = 1,2, \cdots ,n - 1$
 $\begin{array}{*{20}{c}} {f\left( {{v_1}{{v'}_2}} \right) = n - 1,f\left( {{v_n}{{v'}_1}} \right) = 0,f\left( {{v_i}{{v'}_{i + 1}}} \right) = n + 1}&{i = 2,3, \cdots ,n - 1} \end{array}$
 $\begin{array}{*{20}{c}} {f\left( {{v_{i + 1}}{{v'}_i}} \right) = n}&{i = 1,2, \cdots ,n,i + 1} \end{array}\left( {\bmod n} \right)$

 $\lambda _2^T\left( {M\left( {{F_n}} \right)} \right) = 2n + 1.$

不妨设V(Fn)={v0v1v2，…，vn}.

 $\lambda _2^T\left( {M\left( {{F_3}} \right)} \right) \ge 7$

 $f\left( w \right) = 0,f\left( {{v_0}} \right) = 0,f\left( {{v_1}} \right) = 4,f\left( {{v_2}} \right) = 7,f\left( {{v_3}} \right) = 6,$
 $f\left( {{{v'}_0}} \right) = 3,f\left( {{{v'}_1}} \right) = 1,f\left( {{{v'}_2}} \right) = 3,f\left( {{{v'}_3}} \right) = 3,$
 $f\left( {{v_0}{v_1}} \right) = 2,f\left( {{v_0}{v_2}} \right) = 3,f\left( {{v_0}{v_3}} \right) = 4,f\left( {{v_1}{v_2}} \right) = 0,f\left( {{v_2}{v_3}} \right) = 2,$
 $f\left( {{v_0}{{v'}_1}} \right) = 5,f\left( {{v_0}{{v'}_2}} \right) = 6,f\left( {{v_0}{{v'}_3}} \right) = 7,f\left( {{v_1}{{v'}_0}} \right) = 6,f\left( {{v_2}{{v'}_0}} \right) = 1,f\left( {{v_3}{{v'}_0}} \right) = 0,$
 $f\left( {{v_1}{{v'}_2}} \right) = 7,f\left( {{v_2}{{v'}_3}} \right) = 5,f\left( {{v_2}{{v'}_1}} \right) = 4,f\left( {{v_3}{{v'}_2}} \right) = 1,$
 $f\left( {w{{v'}_1}} \right) = 3,f\left( {w{{v'}_2}} \right) = 5,f\left( {w{{v'}_3}} \right) = 6,f\left( {w{{v'}_0}} \right) = 7.$

 $\lambda _2^T\left( {M\left( {{F_n}} \right)} \right) \ge 2n + 1$

 $\lambda _2^T\left( {M\left( {{F_n}} \right)} \right) = 2n + 1$

 $\begin{array}{*{20}{c}} {f\left( {{v_0}} \right) = f\left( {{{v'}_0}} \right) = 0,f\left( w \right) = 2n + 1,f\left( {{v_i}} \right) = f\left( {{{v'}_i}} \right) = i + 3}&{i = 1,2, \cdots ,n} \end{array}$
 $\begin{array}{*{20}{c}} {f\left( {{v_0}{v_i}} \right) = i + 1,f\left( {{v_0}{{v'}_i}} \right) = f\left( {{v_i}{{v'}_0}} \right) = i + n + 1}&{i = 1,2, \cdots ,n} \end{array}$
 $f\left( {{v_i}{v_{i + 1}}} \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 0\\ 1 \end{array}&\begin{array}{l} i \equiv 1\left( {\bmod 2} \right)\\ i \equiv 0\left( {\bmod 2} \right) \end{array} \end{array}} \right.\;\;\;\;\;\;\;\;\;\;i = 1,2, \cdots ,n - 1$
 $\begin{array}{*{20}{c}} {f\left( {{v_1}{{v'}_2}} \right) = f\left( {{v_2}{{v'}_1}} \right) = 2n + 1,f\left( {{v_1}{{v'}_{i + 1}}} \right) = f\left( {{v_{i + 1}}{{v'}_i}} \right) = i}&{i = 2,3, \cdots ,n - 1} \end{array}$
 $\begin{array}{*{20}{c}} {f\left( {w{{v'}_0}} \right) = 2,f\left( {w{{v'}_1}} \right) = 0,f\left( {w{{v'}_i}} \right) = i + 1}&{i = 2,3, \cdots ,n} \end{array}$

 $\lambda _2^T\left( {M\left( {{W_n}} \right)} \right) = 2n + 1$

不妨设V(Wn)={v0v1v2，…，vn}.由图M(Wn)的结构知Δ(M(Wn))=2n，所以由文献[3]的推论4，有

 $\lambda _2^T\left( {M\left( {{W_n}} \right)} \right) \ge 2n + 1$

 $\lambda _2^T\left( {M\left( {{W_n}} \right)} \right) = 2n + 1$

(1) 当n≡0(mod 2)时，

 $f\left( {{v_n}{v_1}} \right) = 1,f\left( {{v_1}{v_2}} \right) = 2n,f\left( {{v_1}{{v'}_n}} \right) = 0,f\left( {{v_n}{{v'}_1}} \right) = 2$

(2) 当n≡1(mod 2)时，

 $f\left( {{v_n}{v_1}} \right) = 0,f\left( {{v_1}{v_2}} \right) = 2n,f\left( {{v_1}{{v'}_n}} \right) = 1,f\left( {{v_n}{{v'}_1}} \right) = 2$

 $\lambda _2^T\left( {M\left( {{W_n}} \right)} \right) = 2n + 1$

 [1] GRIGGS J R, YEH R K. Labelling Graphs with a Condition at Distance Two[J]. SIAM J Discrete Math, 1992, 5(4): 586-595. DOI:10.1137/0405048 [2] WHITTLESEY M A, GEORGES J P, MAURO D W. On the λ-Number of Qn and Related Graphs[J]. SIAM J Discrete Mathematics, 1995, 8(4): 499-506. DOI:10.1137/S0895480192242821 [3] HAVET F, YU M L. (p, 1)-Total Labelling of Graphs[J]. Discrete Math, 2008, 308(4): 496-513. DOI:10.1016/j.disc.2007.03.034 [4] BONDY J A, MURTY U S R. Graph Theory with Applications[M]. London: Macmillan Press Ltd, 1976. [5] CHANG G J, HUANG L L, ZHU X D. Circular Chromatic Number of Mycielski's Graphs[J]. Discrete Math, 1999, 205(1-3): 23-37. DOI:10.1016/S0012-365X(99)00033-3 [6] LIU H M. Circular Chromatic Number for Mycielski Graphs[J]. J of Math (PRC), 2006, 26(3): 255-260. [7] CHEN X E, ZHANG Z F, YAN J Z, et al. Adjacent-Vertex-Distinguishing Total Chromatic Numbers on Mycielski's Graphs of Several Kinds of Particular Graphs[J]. Jorunal of Lanzhou University (Natural Science), 2005, 41(2): 117-122. [8] 刘秀丽. 若干Mycielski图的邻点可区别V-全染色[J]. 西南师范大学学报(自然科学版), 2015, 40(12): 12-16. [9] BOLLOBAS B. Modern Graph Theory[M]. New York: Spring-Verlag, 1998. [10] CHEN D, WANG W F. (2, 1)-Total Labelling of Outerplanar Graphs[J]. Discrete Applied Math, 2007, 155(18): 2585-2593. DOI:10.1016/j.dam.2007.07.016
(2, 1)-Total Labelling on Mycielski's Graphs of Several Kinds of Particular Graphs
LIU Xiu-li
School of Mathematics and Statistics, Heze University, Heze Shandong 274015, China
Abstract: A coloring problem (p, 1)-total labelling of some graphs, which is related to frequency assignment, is studied. By using the eternal coloring method, a new labelling method is given according to the feature of Mycielski's graphs, and the (2, 1)-total numbers of path, cycle, fan and wheel of the graphs are obtained. And the (p, 1)-total labelling of graphs extends the total coloring of graphs.
Key words: coloring    (p, 1)-total coloring    (p, 1)-total number    Mycielski's graph