IJPAM: Volume 41, No. 6 (2007)

ADJACENT VERTEX DISTINGUISHING TOTAL
COLORING OF $P_{n}$ AND $C_{n}$ DOUBLE GRAPH

Ting Zhang$^1$, Muchun Li$^2$, Baogeng Xu$^3$, Ergeng Liu$^4$, Chao Zuo$^5$
$^{1,2,5}$School of Mathematics, Physics and Software Engineering
Lanzhou Jiaotong University
Lanzhou, 730070, P.R CHINA
e-mail: zhangting1389@126.com
$^{3,4}$Department of Mathematics
East China Jiaotong University
Jiaotong, P.R. CHINA


Abstract.A total coloring is called adjacent vertex distinguishing if every two adjacent vertices are incident to different sets of colored vertex and incident edge with vertex. The minimum number of colors required for a adjacent vertex distinguishing proper total coloring, a simple graph $G$ is denoted by $\chi_{at}(G)$.

Let $G(V,E)$ be a simple graph. If $V(D(G))=V(G)\cup V(G^{\prime})$, $E(D(G))=E(G)\cup E(G^{\prime})\cup \{v_{i}v^{\prime}_{j}\vert v_{i}\in V(G),v^{\prime}_{j}\in V(G^{\prime}) $ and $v_{i}v_{j}\in E(G)\}$, then we call $D(G)$ is the double graph of $G$ graph,where $G^{\prime}$ is the copy of $G$. The paper studies the adjacent vetex distinguishing total chromatic number of $C_{n}$ of $D(G)$.

Received: May 28, 2007

AMS Subject Classification: 05C15, 68R10, 94C15

Key Words and Phrases: double graph, Adjacent vetex distinguishing total coloring, adjacent vetex distinguishing total chromatic number

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2007
Volume: 41
Issue: 6