Competition numbers of graphs with a small number of triangles

Suh Ryung Kim; Fred S. Roberts

doi:10.1016/S0166-218X(97)00026-7

Competition numbers of graphs with a small number of triangles

Suh Ryung Kim, Fred S. Roberts

Research output: Contribution to journal › Article › peer-review

22 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	153-162
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	78
Issue number	1-3
DOIs	https://doi.org/10.1016/S0166-218X(97)00026-7
State	Published - Oct 21 1997

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Keywords

Competition graph
Competition number

Access to Document

10.1016/S0166-218X(97)00026-7

Cite this

@article{c25be8bfdc744b5bae95ae36c61f7f1f,

title = "Competition numbers of graphs with a small number of triangles",

abstract = "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.",

keywords = "Competition graph, Competition number",

author = "Kim, {Suh Ryung} and Roberts, {Fred S.}",

note = "Funding Information: Suh-Ryung Kim thanks the ResearchI nstitute of Basic Scienceso f Kyung Hee Universityf or its supporta nd the Korean Ministry of Educationf or its supportu nder grantB SRI-96-1432F. red Robertst hankst he Air Force Office of ScientificR esearch for its support under grants AFOSR-89-0512,A FOSR-90-0008,F 49620-93-1-0041 and F49620-95-1-023to3 RutgersU niversity.B oth authorst hank Li Sheng,A leksan-dar Pekec,D ale Peterson,a nd Shaoji Xu for their extremelyh elpfulc ommentsT. he authorsa lso thank an anonymousr efereefo r his or her helpfulc ommentse, specially for suggestingsh orterp roofs of Theorems6 and 7.",

year = "1997",

month = oct,

day = "21",

doi = "10.1016/S0166-218X(97)00026-7",

language = "English (US)",

volume = "78",

pages = "153--162",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Competition numbers of graphs with a small number of triangles

AU - Kim, Suh Ryung

AU - Roberts, Fred S.

N1 - Funding Information: Suh-Ryung Kim thanks the ResearchI nstitute of Basic Scienceso f Kyung Hee Universityf or its supporta nd the Korean Ministry of Educationf or its supportu nder grantB SRI-96-1432F. red Robertst hankst he Air Force Office of ScientificR esearch for its support under grants AFOSR-89-0512,A FOSR-90-0008,F 49620-93-1-0041 and F49620-95-1-023to3 RutgersU niversity.B oth authorst hank Li Sheng,A leksan-dar Pekec,D ale Peterson,a nd Shaoji Xu for their extremelyh elpfulc ommentsT. he authorsa lso thank an anonymousr efereefo r his or her helpfulc ommentse, specially for suggestingsh orterp roofs of Theorems6 and 7.

PY - 1997/10/21

Y1 - 1997/10/21

N2 - 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.

AB - 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.

KW - Competition graph

KW - Competition number

UR - http://www.scopus.com/inward/record.url?scp=0043015773&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0043015773&partnerID=8YFLogxK

U2 - 10.1016/S0166-218X(97)00026-7

DO - 10.1016/S0166-218X(97)00026-7

M3 - Article

AN - SCOPUS:0043015773

SN - 0166-218X

VL - 78

SP - 153

EP - 162

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

Competition numbers of graphs with a small number of triangles

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this