Competitively Tight Graphs |
| |
Authors: | Suh-Ryung Kim Jung Yeun Lee Boram Park Yoshio Sano |
| |
Institution: | 1. Department of Mathematics Education, Seoul National University, Seoul, 151-742, Korea 2. Hanbat National University, Daejeon, 305-719, Korea 3. National Institute for Mathematical Sciences, Daejeon, 305-811, Korea 4. Division of Information Engineering, Faculty of Engineering, Information and Systems, University of Tsukuba, Ibaraki, 305-8573, Japan
|
| |
Abstract: | The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is the smallest number of such isolated vertices. Computing the competition number of a graph is an NP-hard problem in general and has been one of the important research problems in the study of competition graphs. Opsut 1982] showed that the competition number of a graph G is related to the edge clique cover number θ E (G) of the graph G via θ E (G) ? |V(G)| + 2 ≤ k(G) ≤ θ E (G). We first show that for any positive integer m satisfying 2 ≤ m ≤ |V(G)|, there exists a graph G with k(G) = θ E (G) ? |V(G)| + m and characterize a graph G satisfying k(G) = θ E (G). We then focus on what we call competitively tight graphs G which satisfy the lower bound, i.e., k(G) = θ E (G) ? |V(G)| + 2. We completely characterize the competitively tight graphs having at most two triangles. In addition, we provide a new upper bound for the competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|