A study on upper domatic number and its variants in graphs

Abstract

For a graph G = (V, E), a vertex partition and#8673; = {V1, V2, . . . , Vk} is an upper domatic partition if Vi dominates Vj or Vj dominates Vi or both, for every Vi, Vj 2 and#8673;, whenever i 6= j. The upper domatic number D(G) is the maximum order of an upper domatic partition of G. This thesis consists of studies on upper domatic number and its variants in graphs. The bounds of D(G) in terms of order, size, !(G) and #(G) are established. The class of graphs with equal upper domatic newlinenumber and clique number is characterised. The relation between upper domatic number and minimum degree of the graph is explored. The case when the upper domatic number and domatic number are equal is investigated and the graphs for which D(G) and the domatic number d(G) coincide are characterised. Apart from the relation between the D(G) and other graph parameters, the upper domatic number of some special classes of graphs including unicyclic graphs, complement of cycles and powers of graphs is determined. Transitivity, Tr(G), a variant of upper domatic number is defined as the maximum number of sets in a vertex partition {V1, V2, . . . , Vk} such that Vi dominates Vj where 1 i lt j k. The results from the study on this concept include characterisation of graphs with transitivity at least k, exact values of transitivity of few classes of graphs, few upper bounds of transitivity of graphs, the transitivity of trees and an algorithm to determine the same. Along with this, the concept of total upper domatic number is introduced as a new variant of upper domatic number. The total upper domatic number is the maximum order of a total upper domatic partition of G which is an upper domatic partition such that the graph induced by each partite set does not contain any vertex of degree zero. Basic properties and bounds of upper domatic number in terms of order and maximum degree are discussed. Further, the total upper domatic number of some special classes of graphs is determined.