Sigma Chromatic Number of the Middle Graph of Some Families of Graphs

Date of Award

6-2021

Document Type

Thesis

Degree Name

Master of Science in Mathematics

Department

Mathematics

First Advisor

Agnes D. Garciano, PhD; Mark Anthony C. Tolentino, PhD

Abstract

One of the research topics involving vertex coloring of graphs that has become of inter- est to mathematicians in recent years is that of the sigma coloring. Introduced by Chartrand, Okamoto and Zhang in 2010, it is a type of vertex coloring that is neighbor-distinguishing; that is, it induces a coloring on the vertices of a graph. Let G be a nontrivial connected graph and let c : V (G) → N be a vertex coloring of G, where adjacent vertices may have the same color. For a vertex v of G, the color sum σ(v) of v is the sum of the colors of the vertices adjacent to v. The coloring c is said to be a sigma coloring of G if σ(u) 6= σ(v) whenever u and v are adjacent vertices in G. The minimum number of colors that can be used in a sigma coloring of G is called the sigma chromatic number of G and is denoted by σ(G). On the other hand, the middle graph of a graph was introduced by T. Hamada and I. Yoshimura in 1976. In this study, we will study sigma coloring in relation to a unary graph operation called middle graph. We will show that the sigma chromatic number of the middle graph of paths, cycles, sunlet graphs, tadpole graphs, ladder graphs, and trian- gular snake graphs is 2. We also establish a lower bound for the sigma chromatic number of graphs containing an induced subgraph isomorphic to a complete graph appended with pendant vertices. Then, with this lower bound, we determine the sigma chromatic number of the middle graph of some general families of trees of height 2 such as star graphs, bistar graphs, and full m-ary trees.

Key Words: vertex coloring, sigma coloring, sigma chromatic number

Link to Full Text

Share

COinS