Total graph and its characteristics

Abstract

Graphs constructed by applying some specific rule to any given graph are calledauxiliary graphs. Such graphs are often used to translate one graph problem intoanother. Auxiliary graphs can be viewed as a function from the set of graphs tothe set of graphs. For interesting families of auxiliary graphs, a natural questionis to study the range of the function (i.e. graphs which belong to the family ofauxiliary graphs). Another equally interesting question is computing the originalgraph given such an auxiliary graph.The chromatic number c(G) of graphs minimum number of color needed to colorthe vertices such that no two adjacent vertices get same color. In same way thetotal chromatic number c00(G) of a graph is minimum number of colors needed tocolor the vertices and edges of the graph such that no two adjacent edges-edges,edges-vertices and vertices-vertices get same color. For total coloring consideringedges of graph as vertex then total coloring problem can be as vertex coloringproblem. A natural way to decide the total chromatic number c00(G) is by transformingedges of a graph to vertices without disturbing the original structure andadjacency. The resultant graph is called total graph. Thus total graph is an auxiliarygraph which transforms the total coloring problem to the vertex coloringproblem.This thesis consists of several problems related to degree sequences of total graphs.In this thesis, we have derived some new characteristics of total graphs like relationbetween the number of vertices and edges of total graph with inverse totalgraph, number of mixed clique in total graph etc. We have found some heuristicmethods for verification of whether or not a given degree sequence belongs tosome total graph. If the sequence is of a total graph then we provide a constructionmethod for obtaining the inverse total graph. For total graphs of a specialclass of graphs which we call Havel-Hakimi graphs, we obtain a precise characterisationto recognize their degree sequences. We also develop a method fordirect construction of total graph of complete bipartite graph.