✦ LIBER ✦

Competition numbers of graphs with a small number of triangles

✍ Scribed by Suh-Ryung Kim; Fred S. Roberts

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 722 KB
Volume: 78
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(97)00026-7

No coin nor oath required. For personal study only.

✦ Synopsis

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 (x, a) and (y, a) are both arcs of D. If G is any graph, 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. Roberts (1978) gives a formula for the competition number of connected graphs with no triangles. In this paper, we compute the competition numbers of connected graphs with exactly one or exactly two triangles.

📜 SIMILAR VOLUMES

The double competition number of some tr

The double competition number of some triangle-free graphs

✍ Suzanne M. Seager 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 299 KB

Chromatic numbers of competition graphs

✍ J.Richard Lundgren; Sarah K. Merz; Craig W. Rasmussen 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 964 KB

A triangle-free circle graph with chroma

A triangle-free circle graph with chromatic number 5

✍ A.A. Ageev 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 170 KB

It follows from the results of , Gyirfis and Lehel (1985), and Kostochka (1988) that 4 ~x\* ## ~5 where x\* = max {X(G): G is a triangle-free circle graph}. We show that X\* ? 5 and thus X\* = 5. This disproves the conjecture of Karapetyan that X\* = 4 and answers negatively a question of Gyirfis

Graphs with small numbers of independent

Graphs with small numbers of independent edges

✍ Miroslav M. Petrović; Ivan Gutman; Mirko Lepović 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 327 KB

The graphs with exactly one, two or three independent edges are determined.

A characterization of graphs of competit

A characterization of graphs of competition number m

✍ J.Richard Lundgren; John S. Maybee 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 245 KB

Graphs with a small number of distinct i

Graphs with a small number of distinct induced subgraphs

✍ Noga Alon; Béla Bollobás 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 514 KB

Let G be a graph on n vertices. We show that if the total number of isomorphism types of induced subgraphs of G is at most &II', where E < lo-\*', then either G or its complement contain an independent set on at least (1 -4e)n vertices. This settles a problem of Erdiis and Hajnal.