Fraughnaugh, Kathryn F.; Lundgren, J. Richard; Merz, Sarah K.; Maybee, John S.; Pullman, Norman J. Competition graphs of strongly connected and Hamiltonian digraphs. (English) Zbl 0830.05035 SIAM J. Discrete Math. 8, No. 2, 179-185 (1995). Authors’ abstract: A radio communication network can be modeled by a digraph, \(D\), where there is an arc 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 same 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 connected, 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, including chordal, interval, and some triangle-free graphs, which are competition graphs of loopless Hamiltonian digraphs. Reviewer: G.Chaty (Paris) Cited in 6 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 90B18 Communication networks in operations research 05C45 Eulerian and Hamiltonian graphs 05C75 Structural characterization of families of graphs Keywords:conflict graph; edge clique cover; chordal graph; interval graph; cycle; communication network; digraph; competition graph; strongly connected digraphs; Hamiltonian digraphs PDFBibTeX XMLCite \textit{K. F. Fraughnaugh} et al., SIAM J. Discrete Math. 8, No. 2, 179--185 (1995; Zbl 0830.05035) Full Text: DOI