research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleThe chromatic and clique numbers of random scaled sector graphs
Bibtex cite IDRACTI-RU1-2005-32
Journal Theoretical Computer Science (TCS)
Year published 2005
Month December
Volume 349
Number 1
Pages 40-51
ISSN 0304-3975
DOI 10.1016/j.tcs.2005.09.050
Keywords Random scaled sector graphs; Random geometric graphs; Chromatic number; Clique number; TalagrandΆs inequality
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 ái, in a circle of radius ri (with vertex i as the origin). An arc is present from vertex i to any vertex j, if j falls in Si. In this work, we study the value of the chromatic number Ô(Gn), directed clique number ù(Gn), and undirected clique number ù2 (Gn) for random scaled sector graphs with n vertices, where each vertex spans a sector of á degrees with radius rn = ãln n/n. We prove that for values á < Î, as n w.h.p., Ô(Gn) and ù2 (Gn) are È(ln n/ln ln n), while ù(Gn) is O(1), showing a clear difference with the random geometric graph model. For á > Î w.h.p., Ô(Gn) and ù2 (Gn) are È (ln n), being the same for random scaled sector and random geometric graphs, while ù(Gn) is È(ln n/ln ln n).
Diaz, Josep
Sanwalani, Vishal
Serna, Maria
Spirakis, Paul
fulltext.pdf (main file)
Publication ID346