Let G be a simple undirected uniquely vertex kcolorable graph, or a kUCG for short. M. Truszczynski [some results on uniquely colorable graphs, in Finite and Infinite Sets, NorthHolland, Amsterdam, 1984, pp. 733748] introduced e^{*}(G)=V(G)(k−1)−((k)  2) as the minimum number of edges for a kUCG contains a K_{k} as a subgraph. In this paper, first we introduce a technique called forcing. Then by applying this technique in conjunction with a feedback structure we construct a kUCG with clique number k−t, for each t ≥ 1 and each k, when k is large enough. This also improves some known results for the case t=1.
Second, we analyze the parameter Λ (G)=E(G)−e^{*}(G) for our constructions, and we obtain some bounds for the functions
λ_{t}(k)= 
min
 {Λ(G): Gis a k−UCG and cl(G)=k−t}, 

ν_{t}(k)= 
min
 {V(G): Gis a k−UCG and cl(G)=k−t}. 

Also, we introduce some possible applications of the technique in cryptography and data compression.
Download TeX format
