scientific article; zbMATH DE number 3889550

From MaRDI portal
Publication:3222864





[For the entire collection see Zbl 0547.00012.]. A characterisation of a digraph with interval competition graph is given. Let \(D=[X,E]\) be a digraph. The competition graph of D is an undirected graph \(G=[X,E']\) where \(\{\) x,y\(\}\) is an edge in G iff there exists such z that (x,z)\(\in E\) and (y,z)\(\in E\). The question investigated in this paper is: What digraphs have competition graphs that are interval? The characterisation of such (acyclic) digraphs is given by means of the competition cover of D which is a generalisation of cover by instars. Another approach to characterize the digraphs with the interval competition graphs is using of forbidden induced subgraphs. There is shown that digraph D with the interval competition graph may contain a subdigraph without this property. On the other hand an acyclic digraph D has a competition graph iff every sink subdigraph H of D is an induced subdigraph with additional property: if \(x\in H\) and (x,y)\(\in E\), then \(y\in H\).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3222864)