QA213 : Chromatic Sum Of Graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2013
Authors:
Mahmoud Tardasty [Author], Sadegh Rahimi Shearbaf Moghaddas[Supervisor], Meysam Alishahi[Supervisor]
Abstarct: For graph G, a function c : V (G) −→ ℵ is called a proper coloring, if for every uv ∈ E(G) we have c(u) ̸= c(v). Chromatic sum corresponding with c coloring is defined as equal to Σu∈V (G)c(u), and chromatic sum Σ(G) of G, is the minimum possible value for chromatic sum, among all proper colorings of G. Also, the minimum number of colors for which a coloring with chromatic sum of graph G can be found, is called vertex strength s(G) of G. In this thesis, in the first chapter, we review the previous literature and become familiar with the topic of chromatic sum and its concept, then we show its applications in the engineering and electronics known as ”VLSI design”. In the second chapter, we review the basic definitions and general theorems used in the next chapters. Concepts of minimal coloring, chromatic sum and vertex strength of a graph are expressed in chapter three; we also investigate some bounds for these concepts. Finally, in chapter four, with the use of the concept of homomorphism of graphs, we mention some bounds for chromatic sum. Chapter four will be ended by expressing two algorithms for approximate calculation of chromatic sum values and vertex strength.
Keywords:
#Chromatic Sum #Vertex Strength #Minimal Coloring Link
Keeping place: Central Library of Shahrood University
Visitor: