On the defining spectrum of kk-regular graphs with k–1k–1 colors

Abstract

In a given graph G=(V;E)G=(V;E), a set of vertices S with an assignment of colors to them is said to be a defining set of the vertex coloring of G, if there exists a unique extension of the colors of S to a c≥χ(G)c≥χ(G) coloring of the vertices of G. A defining set with minimum cardinality is called a minimum defining set and its cardinality is the defining number, denoted by (d(G;c)(d(G;c). If F is a family of graphs then Specc(F)={d|∃G,GϵF,d(G,C)=d}Specc(F)={d|∃G,GϵF,d(G,C)=d}. Here we study the cases where FF is the family of k−k−regular (connected and disconnected) graphs on n vertices and c=k−1c=k−1. Also the Speck−1(F)Speck−1(F) defining spectrum of all k−k−regular (connected and disconnected) graph on n vertices are verified for k=3,4k=3,4 and 55.