The Sigma Chromatic Number of the Circulant Graphs Cn(1,2) , Cn(1,3) , and C2n(1,n)
Document Type
Article
Publication Date
11-2016
Abstract
For a non-trivial connected graph G, let c:V(G)→N" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">c:V(G)→Nc:V(G)→N be a vertex coloring of G. For each v∈V(G)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">v∈V(G)v∈V(G), the color sum of v, denoted by σ(v)," role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">σ(v),σ(v), is defined to be the sum of the colors of the vertices adjacent to v. If σ(u)≠σ(v)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">σ(u)≠σ(v)σ(u)≠σ(v) for every two adjacent u,v∈V(G)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">u,v∈V(G)u,v∈V(G), then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of G is called its sigma chromatic number and is denoted by σ(G)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">σ(G)σ(G). In this paper, we determine the sigma chromatic numbers of three families of circulant graphs: Cn(1,2)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">Cn(1,2)Cn(1,2), Cn(1,3)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">Cn(1,3)Cn(1,3), and C2n(1,n)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">C2n(1,n)C2n(1,n).
Recommended Citation
Luzon P.A.D., Ruiz MJ.P., Tolentino M.A.C. (2016) The Sigma Chromatic Number of the Circulant Graphs Cn(1,2), Cn(1,3), and C2n(1,n). In: Akiyama J., Ito H., Sakai T., Uno Y. (eds) Discrete and Computational Geometry and Graphs. JCDCGG 2015. Lecture Notes in Computer Science, vol 9943. Springer, Cham
