Export file:


  • RIS(for EndNote,Reference Manager,ProCite)
  • BibTex
  • Text


  • Citation Only
  • Citation and Abstract

The independence number of circulant triangle-free graphs

1 Department of Mathematics, University of Zabol, Zabol, Iran
2 Chemical Engineering group, Pardis College, Isfahan University Of Technology, Isfahan, Iran
3 Computer Engineering and Information Technology Department, Shiraz University of Technology, Shiraz, Iran

Special Issues: 8th International Eurasian Conference on Mathematical Sciences and Applications (IECMSA-2019)

The independence number of circulant triangle-free graphs for 2-regular, 3-regular graphs are investigated. It is shown that the independence ratio of circulant triangle-free graphs for 3-regular graphs is at least 3/8. Some bounds for the number of vertices of r-regular circulant triangle-free graphs with independence number equal to r for odd degrees are determined. These bounds are close to Sidorenko’s bounds for even degrees.
  Article Metrics


1. D. Bauer, Regular Kn-free graphs, J. Combin. Theory Ser. B., 35 (1983), 193-200.    

2. S. Brandt, Triangle-free graphs whose independence number equals the degree, Discrete Math., 310 (2010), 662-669.    

3. C. Heckman, C. Thomas, A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math., 233 (2001), 233-237.    

4. N. Punnim, The clique numbers of regular graphs, Graph. Combinator., 18 (2002), 781-785.    

5. R. D. Ringeisen, F. S. Roberts, Applications of Discrete Mathematics, In: Proceedings of the Third SIAM Conference on Discrete Mathematics held at Clemson University, SIAM, Philadelphia, PA, 1988.

6. A. F. Sidorenko, Triangle-free regular graphs, Discrete Math., 91 (1991), 215-217.    

7. W. Staton, Some Ramsey-type numbers and the independence ratio, T. Am. Math. Soc., 256 (1979), 353-370.    

© 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution Licese (http://creativecommons.org/licenses/by/4.0)

Download full text in PDF

Export Citation

Article outline

Show full outline
Copyright © AIMS Press All Rights Reserved