Mathematics – Combinatorics
Scientific paper
2011-03-05
Applied Mathematics Letters 25 (2012) 638-642
Mathematics
Combinatorics
6 pages, 3 figures
Scientific paper
10.1016/j.aml.2011.10.003
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. Recently, the relationship between the competition number and the number of holes of a graph is being studied. A hole of a graph is a cycle of length at least 4 as an induced subgraph. In this paper, we conjecture that the dimension of the hole space of a graph is no smaller than the competition number of the graph. We verify this conjecture for various kinds of graphs and show that our conjectured inequality is indeed an equality for connected triangle-free graphs.
Kim Suh-Ryung
Lee Jung Yeun
Park Boram
Sano Yoshio
No associations
LandOfFree
The competition number of a graph and the dimension of its hole space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The competition number of a graph and the dimension of its hole space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The competition number of a graph and the dimension of its hole space will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-8744