Research article Special Issues

The independence number of circulant triangle-free graphs

  • Received: 26 November 2019 Accepted: 13 April 2020 Published: 20 April 2020
  • MSC : 05C69, 05C75

  • 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.

    Citation: S. Masih Ayat, S. Majid Ayat, Meysam Ghahramani. The independence number of circulant triangle-free graphs[J]. AIMS Mathematics, 2020, 5(4): 3741-3750. doi: 10.3934/math.2020242

    Related Papers:

  • 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.


    加载中


    [1] D. Bauer, Regular Kn-free graphs, J. Combin. Theory Ser. B., 35 (1983), 193-200. doi: 10.1016/0095-8956(83)90071-0
    [2] S. Brandt, Triangle-free graphs whose independence number equals the degree, Discrete Math., 310 (2010), 662-669. doi: 10.1016/j.disc.2009.05.021
    [3] C. Heckman, C. Thomas, A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math., 233 (2001), 233-237. doi: 10.1016/S0012-365X(00)00242-9
    [4] N. Punnim, The clique numbers of regular graphs, Graph. Combinator., 18 (2002), 781-785. doi: 10.1007/s003730200064
    [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. doi: 10.1016/0012-365X(91)90114-H
    [7] W. Staton, Some Ramsey-type numbers and the independence ratio, T. Am. Math. Soc., 256 (1979), 353-370. doi: 10.1090/S0002-9947-1979-0546922-6
  • Reader Comments
  • © 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(2772) PDF downloads(313) Cited by(1)

Article outline

Figures and Tables

Figures(2)  /  Tables(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog