The chromatic and clique numbers of random scaled sector graphs

Random scaled sector graphs were introduced as a generalization of random geometric graphs to model networks of sensors using optical communication. In the random scaled sector graph model vertices are placed uniformly at random into the [0, 1](2) unit square. Each vertex i is assigned uniformly at random sector Si, of central angle alpha(i), in a circle of radius r(i) (with vertex i as the origin). An arc is present from vertex i to any vertex j, if j falls in S-i. In this work, we study the value of the chromatic number chi(G(n)), directed clique number omega(G(n)), and undirected clique number (omega(2)) over cap (G(n)) for random scaled sector graphs with n vertices, where each vertex spans a sector of alpha degrees with radius r(n) = root ln n/n.We prove that for values alpha < pi, as n -> infinity w.h.p., chi(G(n)) and <(omega(2))over cap>(G(n)) are Theta(ln n/ln ln n),while omega(G(n)) is O(1), showing a clear difference with the random geometric graph model. For alpha > pi w.h.p., chi(G(n)) and (omega(2)) over cap (G(n)) are Theta(ln n), being the same for random scaled sector and random geometric graphs, while omega(G(n)) is Theta(ln n/ln ln n). (c) 2005 Elsevier B.V. All rights reserved.