2011/02/28 by Jung Yeun Lee, Lee, Jung Yeun, Suh-Ryung Kim +3
Computer Science · Decision Sciences · Mathematics · #05C38 #05C75 #05C76 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Applications #Optimization and Search Problems #math.CO #msc:05C38 #msc:05C75 #msc:05C76
paper · pdf · doi:10.48550/arxiv.1102.5718
29 pages, 14 figures, 1 table
arxiv created 2011/02/28 · openalex publication_date 2011/02/28 · arxiv updated 2011/03/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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 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 G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of important research problems in the study of competition graphs to characterize a graph by its competition number. A hole of a graph is a cycle of length at least 4 as an induced subgraph. It holds that the competition number of a graph cannot exceed one plus the number of its holes if G satisfies a certain condition. In this paper, we show that the competition number of a graph with exactly h holes any two of which share at most one edge is at most h+1, which generalizes the existing results on this subject.