COMPETITION GRAPHS OF STRONGLY CONNECTED AND HAMILTONIAN DIGRAPHS

A radio communication network can be modeled by a digraph, D, where th ere is an are from vertex x to vertex y if a signal sent from x can be received at y. The competition graph, C(D), of this network has the s ame vertex set as D, and (x,y) is an edge in C(D) if there is a vertex z such that (x,z) and (y,z) are arcs in D. The competition graph can be used to assist in assigning frequencies to the transmitters in the network. Usually the digraphs for these networks are strongly connecte d, but the power of transmitters may vary, so they are not necessarily symmetric. Therefore it is of interest to determine which graphs are the competition graphs of strongly connected digraphs. We characterize these graphs as well as establish several large classes of graphs, in cluding chordal, interval, and some triangle-free graphs, which are co mpetition graphs of loopless Hamiltonian digraphs.