Competition numbers of graphs with a small number of triangles
type: Item
instance of: scholarly article
title: Competition numbers of graphs with a small number of triangles
zbMATH Open document ID: 0889.05057
DOI: 10.1016/S0166-218X(97)00026-7
author: Suh-Ryung Kim
author: Fred Roberts
published in: Discrete Applied Mathematics
publication date: 1998-06-11T00:00:00Z
full work available at URL: dam
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1109940
zbMATH Keywords: acyclic digraph
zbMATH Keywords: competition graph
zbMATH Keywords: competition number
zbMATH Keywords: connected graphs
zbMATH Keywords: triangles
reviewed by: Wenpeng Zhang
MaRDI profile type: Publication
cites work: Q5422499
cites work: Niche graphs
cites work: A characterization of competition graphs
cites work: Niche numbers
cites work: Q3797197
cites work: Q3479858
cites work: On the Computation of the Competition Number of a Graph
cites work: Q3689222
cites work: Q4171826
cites work: A characterization of competition graphs of arbitrary digraphs
cites work: The competition-common enemy graph of a digraph
OpenAlex ID: W2053270673
description: scientific article; zbMATH DE number 1109940