×

Competition graphs of strongly connected and Hamiltonian digraphs. (English) Zbl 0830.05035

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)

MSC:

05C20 Directed graphs (digraphs), tournaments
90B18 Communication networks in operations research
05C45 Eulerian and Hamiltonian graphs
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI