“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 735
School of Mathematics
  Title:   Forcing structures and cliques in uniquely vertex colorable graphs
  Author(s):  A. Daneshgar
  Status:   Published
  Journal: SIAM J. Discrete Math.
  No.:  4
  Vol.:  14
  Year:  2001
  Pages:   433-445
  Supported by:  IPM
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 kt, 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 kUCG  and cl(G)=kt},

νt(k)= min
{|V(G)|: Gis  a kUCG  and cl(G)=kt}.
Also, we introduce some possible applications of the technique in cryptography and data compression.

Download TeX format
back to top
scroll left or right