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

Date of Award

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.

This document is currently not available here.

Share

COinS