Segregated extension of graphs

Abstract

A graph in which any two adjacent vertices have distinct degrees is totally segregated. In this article segregating sequence, which is a new tool for finding segregated extension of given graph is introduced. If G is an undirected graph which contains a vertex v, then the graph G◦v is obtained from G by adding a new vertex v’ which is connected to all the neighbors of v. More generally, if v₁, v₂,··· , v_n are the vertices of G and t = (t₁,t₂,··· ,t_n) is a vector of positive integers then H = G◦t is constructed by substituting for each v_i an independent set of t_i vertices v¹_i , v²_i ,··· , v^ti_i and joining v^s_i with v^t_j if and only if v_i and v_j are adjacent in G. If G is not totally segregated and G◦t is totally segregated, then the sequence t is a segregating sequence of G. Here it is proved that any graph can be embedded as an induced subgraph in a totally segregated graph. Further, segregating sequence for many classes of graphs are determined.