کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420007 | 683882 | 2013 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The competition number of the complement of a cycle The competition number of the complement of a cycle](/preview/png/420007.png)
In this paper, we compute the competition number of the complement of a cycle. It is well-known that the competition number of a cycle of length at least 4 is two while the competition number of a cycle of length 3 is one. Characterizing a graph by its competition number has been one of important research problems in the study of competition graphs, and competition numbers of various interesting families of graphs have been found. We thought that it is worthy of computing the competition number of the complement of a cycle. In the meantime, the observation that the complement of an odd cycle of length at least 5 is isomorphic to a circulant graph led us to compute the competition number of a large family of circulant graphs. In fact, those circulant graphs satisfy the long lasting Opsut’s conjecture stating that the competition number of a locally cobipartite graph is at most two.
Journal: Discrete Applied Mathematics - Volume 161, Issue 12, August 2013, Pages 1755–1760