西南大学学报 (自然科学版)  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
    本文作者相关文章
    刘秀丽
    欢迎关注西南大学期刊社
     

  • 几类特殊图的Mycielski图的(2, 1)全标号    [PDF全文]
    刘秀丽     
    菏泽学院 数学与统计学院, 山东 菏泽 274015
    摘要:研究了与频道分配有关的一种染色问题:(p,1)-全标号.根据Mycielski图的构造特征,利用穷染法,给出了一种标号方法,得到了路、圈、扇和轮的Mycielski图的(2,1)-全标号数.(p,1)-全标号是对图的全染色的一种推广.
    关键词染色    (p, 1)-全标号    (p, 1)-全标号数    Mycielski图    

    图的染色问题是图论的主要研究内容之一,在现实中被广泛地应用,因而逐渐成为众多学者研究的热点.近年来,一些染色问题在频率分配中有很强的应用,如泛宽度染色、L(p,1)-标号[1].特别地,文献[2]给出了G的剖分图S1(G)的L(p,1)-标号,也就是G的(p,1)-全标号[3]. Mycielski图[4-5]是实际应用中一种重要的图,一些学者对一些特殊图的Mycielski图的染色问题进行了研究[5-8].本文讨论了路、圈、扇和轮的Mycielski图的(2,1)-全标号,根据路、圈、扇和轮的Mycielski图的结构特征,给出了一种标号方法,得到了它们的(2,1)-全标号数.

    本文所讨论的图均为简单、有限图.文中未加说明的记号和术语参见文献[4, 9].

    定理1    设Pn表示阶为n(n≥3)的路,则有

    $ \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.

    由图M(P3)的结构知Δ(M(P3))=4,所以由文献[3]的推论4,有

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

    为了证明

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

    只需给出M(P3)的一个5-(2,1)-全标号.为此,构造映射f

    $ 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. $

    由文献[3]的定义知,fM(P3)的一个正常的5-(2,1)-全标号.所以λ2T(M(P3))=5.

    情形2    n=4.

    由图M(P4)的结构知Δ(M(P4))=4,所以由文献[3]的推论4,有

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

    为了证明

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

    只需给出M(P4)的一个5-(2,1)-全标号.为此,构造映射f

    $ 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. $

    由文献[3]的定义知,fM(P4)的一个正常的5-(2,1)-全标号.所以λ2T(M(P4))=5.

    情形3    n≥5.

    由图M(Pn)的结构知Δ(M(Pn))=n,所以由文献[3]的推论4,有

    $ \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 $

    只需给出M(Pn)的一个(n+1)-(2,1)-全标号.为此,构造映射f

    $ 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 $

    由文献[3]的定义知,fM(Pn)的一个正常的(n+1)-(2,1)-全标号.所以λ2T(M(Pn))=n+1.

    定理2    设Cn表示阶为n(n≥3)的圈,则有

    $ \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.

    由图M(C3)的结构知Δ(M(C3))=4,所以由文献[3]的推论4,有

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

    首先证明λ2T(M(C3))=5不成立.反证法,假设存在图M(C3)的一个正常的5-(2,1)-全标号.由文献[10]的引理8知,图M(C3)的最大度点vi只能标0或5.由图M(C3)的结构易知,最大度点vi生成的子图中包含三角形,而三角形的顶点色数为3,所以0和5无法完成对最大度点vi的全标号,矛盾.所以λ2T(M(C3))≥6.

    为了证明λ2T(M(C3))=6,只需给出M(C3)的一个6-(2,1)-全标号.为此,构造映射f

    $ 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. $

    由文献[3]的定义知,fM(C3)的一个正常的6-(2,1)-全标号,所以

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

    情形2    n=4.

    由图M(C4)的结构知Δ(M(C4))=4,所以由文献[3]的推论4,有

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

    首先证明λ2T(M(C4))=5不成立.反证法,假设存在一个映射f是图M(C3)的一个正常的5-(2,1)-全标号.由文献[10]的引理8知,图M(C4)的最大度点v1v2v3v4只能标0或5.不妨令f(v1)=f(v3)=0,f(v2)=f(v4)=5,则边v1v2v2v3v3v4v4v1只能标2和3,不妨令f(v1v2)=f(v3v4)=2,f(v2v3)=f(v4v1)=3.则边v1v2v1v4v3v2v3v4只能标0和1,边v2v1v2v3v4v3v4v1只能标4和5.又因为w也为最大度点,所以f(w)=0或f(w)=5.

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

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

    同理,其他的标号情况也得出矛盾.所以λ2T(M(C4))≥6.

    为了证明λ2T(M(C4))=6,只需给出M(C4)的一个6-(2,1)-全标号.为此,构造映射f

    $ 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. $

    由文献[3]的定义知,fM(C4)的一个正常的6-(2,1)-全标号.所以λ2T(M(P4))=6.

    情形3    n≥5.

    由图M(Cn)的结构知Δ(M(Cn))=n,所以由文献[3]的推论4,有

    $ \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 $

    下面只需给出M(Cn)的一个(n+1)-(2,1)-全标号.为此,构造映射f

    (ⅰ)当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) $

    由文献[3]的定义知,fM(Cn)的一个正常的(n+1)-(2,1)-全标号.所以λ2T(M(Cn))=n+1.

    定理3    设Fn表示阶为n+1(n≥3)的扇,则有

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

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

    情形1    n=3.

    由图M(F3)的结构知Δ(M(F3))=6,所以由文献[3]的推论4,有

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

    为了证明λ2T(M(F3))=7,只需给出M(F3)的一个7-(2,1)-全标号.为此,构造映射f

    $ 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. $

    由文献[3]的定义知,fM(F3)的一个正常的7-(2,1)-全标号.所以λ2T(MF3))=7.

    情形2    n≥4.

    由图M(Fn)的结构知Δ(M(Fn))=2n,所以由文献[3]的推论4,有

    $ \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 $

    只需给出M(Fn)的一个(2n+1)-(2,1)-全标号.为此,构造映射f

    $ \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} $

    由文献[3]的定义知,f是图M(Fn)的一个正常的(2n+1)-(2,1)-全标号.所以λ2T(M(Fn))=2n+1.

    定理4    设Wn表示阶为n+1(n≥4)的轮,则有

    $ \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 $

    只需给出M(Wn)的一个(2n+1)-(2,1)-全标号.为此,构造映射f

    (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 $

    其他点和边的标号同定理3.由文献[3]的定义知,fM(Wn)的一个正常的(2n+1)-(2,1)-全标号.所以

    $ \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    
    X