Coloring the Square of Sierpiński Graphs

被引:0
作者
Bing Xue
Liancui Zuo
Guojun Li
机构
[1] Linyi University,School of Science
[2] Tianjin Normal University,College of Mathematical Science
[3] Shandong University,Department of Mathematics
来源
Graphs and Combinatorics | 2015年 / 31卷
关键词
Chromatic number; Equitable chromatic number; Square of graph; Sierpiński graph;
D O I
暂无
中图分类号
学科分类号
摘要
The square G2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G^2$$\end{document} of a graph G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} is defined on the vertex set V(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V(G)$$\end{document} of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} such that any two vertices with distance at most two in G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} are linked by an edge. In this paper, the chromatic number and equitable chromatic number of the square S2(n,k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S^2(n,k)$$\end{document} of Sierpiński graph S(n,k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S(n,k)$$\end{document} are studied. It is obtained that χ(S2(n,k))=χ=(S2(n,k))=k+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi (S^2(n,k))=\chi _{=}(S^2(n,k))=k+1$$\end{document} for n≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 2$$\end{document} and k≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 2$$\end{document}.
引用
收藏
页码:1795 / 1805
页数:10
相关论文
共 78 条
  • [1] Beaudou L(2010)Covering codes in Sierpiński graphs Discrete Math. Theor. Comput. Sci 12 63-74
  • [2] Gravier S(1999)Results and open problems on the Tower of Hanoi Congr. Numer. 139 113-122
  • [3] Klavžar S(1989)A statistical analysis of the Towers of Hanoi problem Int. J. Comput. Math. 28 57-65
  • [4] Kovše M(2009)Coloring the square of the Kneser graph KG(2k+1, k) and the Schrijver graph SG(2k+2, k) Discrete Appl. Math. 157 170-176
  • [5] Mollard M(2008)On Discrete Appl. Math. 156 2867-2881
  • [6] Bode JP(1999)-labeling of Cartesian product a cycle and a path Discrete Math. 208–209 157-175
  • [7] Hinz AM(2008)Error-correcting codes on the Towers of Hanoi graphs Eur. J. Combin. 29 838-849
  • [8] Chan TH(2010)Coloring squares of planar graphs with girth six Australas. J. Combin. 46 147-156
  • [9] Chen JY(2012)Equitable Ars Combin. 105 513-524
  • [10] Lih KW(2005)-labelings of Sierpiński graphs Taiwan. J. Math. 9 671-681