Competition numbers of graphs with a small number of triangles
If \(D\) is an acyclic digraph, its competition graph is an undirected graph with the same vertex set and an edge between vertices \(x\) and \(y\) if there is a vertex \(a\) so that both \((x,a)\) and \((y,a)\) are arcs of \(D\). If \(G\) is any graph, then \(G\) together with sufficiently many isolated vertices is a competition graph, and the competition number of \(G\) is the smallest number of such isolated vertices. \textit{F. S. Roberts} [Theor. Appl. Graphs, Proc. Kalaneazoo 1976, Lect. Notes Math. 642, 477-490 (1978; Zbl 0389.90036)] gave a formula for the competition number of connected graphs with no triangles. In this paper, the authors compute the competition number of connected graphs without or two triangles, and obtain several exact formulas.
scientific article; zbMATH DE number 1109940