The independence number of circulant triangle-free graphs

S. Masih Ayat; S. Majid Ayat; Meysam Ghahramani; S. Masih Ayat; S. Majid Ayat; Meysam Ghahramani

doi:10.3934/math.2020242

AIMS Mathematics

2020, Volume 5, Issue 4: 3741-3750. doi: 10.3934/math.2020242

Previous Article Next Article

Research article Special Issues

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

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.
- triangular-free graphs,
- circulant graphs,
- independence number,
- independence ratio,
- Ramsey graphs
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:

Abstract

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.

References

[1]	D. Bauer, Regular K_n-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

Your name:*

Email:*
© 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)