Let G be a simple undirected uniquely vertex k-colorable graph, or a k-UCG for short. M. Truszczynski [some results on uniquely colorable graphs, in Finite and Infinite Sets, North-Holland, Amsterdam, 1984, pp. 733-748] introduced e*(G)=|V(G)|(k−1)−((k) || 2) as the minimum number of edges for a k-UCG contains a Kk 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 k-UCG 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
|
