A study on certain types of completion in graphs

Abstract

Addition of a maximum number of bichromatic edges turns the system a more saturated and stable one. This process is called chromatic completion and the upgraded system or graph is called chromatic completion graph. And newlinethe number of edges added to obtain the chromatic completion graph is the chromatic completion number. Motivated by the study of chromatic completion, the research focuses on its equitable coloring variant, a new version of chromatic completion suitable for dominator coloring and a structural completion based on circulant graphs. newlineAn equitable coloring of a graph G is a proper vertex coloring in which the number of vertices in any two color classes is either equal or diand#64256;ers by at most one. Equitable coloring is crucial in scenarios where a system needs to be divided into binary conand#64258;ict-free subsystems, each containing equal or nearly equal numbers of elements. This graph coloring also focuses on the partitioning a set of tasks into subsets that are executed simultaneously. Equitable chromatic completion is the chromatic completion done in equitably colored graphs. newlineThe study discusses about various structural aspects of equitable chromatic completion graphs and gives the equitable chromatic completion number for various graph classes. It also emphasizes the equitable chromatic completion of disconnected graphs. A dominator coloring of a graph G is a coloring in which an entire color class is included in the closed neighbourhood of each vertex in G. The research deals with dominator chromatic completion that focuses on converting the coloring of a given graph into the dominator coloring of its dominator chromatic completion graph. A circulant graph C(n, S) is a graph having its adjacency matrix as a circulant matrix. It can also be interpreted as a graph with vertices v0, v1, . . . , vnand#8722;1 newlinethat are in one to one correspondence with the members of (Zn,+n) and with edge set {vivj : i and#8722; j and#8712; S}, where S known as the connection set or symbol, is a subset of non-identity members of (Zn,+n) that is closed.