Abstract
A graph G is t-tough if any induced subgraph of it with x > 1 connected components is obtained from G by deleting at least tx vertices. It is shown that for every t and g there are t-tough graphs of girth strictly greater than g. This strengthens a recent result of Bauer, van den Heuvel and Schmeichel who proved the above for g = 3, and hence disproves in a strong sense a conjecture of Chvátal that there exists an absolute constant t 0 so that every t 0-tough graph is pancyclic. The proof is by an explicit construction based on the tight relationship between the spectral properties of a regular graph and its expansion properties. A similar technique provides a simple construction of triangle-free graphs with independence number m on Ω(m 4/3) vertices, improving previously known explicit constructions by Erdös and by Chung, Cleve and Dagum.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Ajtai, J. Komlós, and E. Szemerédi, “A note on Ramsey numbers,” J. Combinatorial Theory Ser. A 29 (1980), 354–360.
N. Alon, “Eigenvalues and expanders,” Combinatorica 6 (1986), 83–96.
N. Alon and F.R.K. Chung, “Explicit construction of linear sized tolerant networks,” Discrete Math. 72 (1988), 15–19; (Proc. of the First Japan Conference on Graph Theory and Applications, Hakone, Japan, 1986).
N. Alon, O. Goldreich, J. Hastad, and R. Peralta, “Simple constructions of almost k-wise independent random variables,” Proc. 31 st IEEE FOCS, St. Louis, Missouri, IEEE (1990), 544–553. See also: Random Structures and Algorithms 3 (1992), 289–304.
N. Alon and V.D. Milman, “λ1, isoperimetric inequalities for graphs and superconcentrators,” J. Comb. Theory, Ser. B 38 (1985), 73–88. See also: “Eigenvalues, expanders and superconcentrators,” Proc. 25 st IEEE FOCS, Singer Island, Florida, IEEE (1984), 320–322.
N. Alon and Y. Roichman, “Random Cayley graphs and expanders,” Random Structures and Algorithms, 5 (1994), 271–284.
N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, 1991.
D. Bauer, J. van den Heuvel and E. Schmeichel, Toughness and triangle-free graphs, (to appear).
B. Bollobás, Extremal Graph Theory, Academic Press, 1978.
V. Chvátal, “Tough graphs and Hamiltonian circuits,” Discrete Mathematics 5 (1973), 215–218.
F.R.K. Chung, R. Cleve, and P. Dagum, “A note on constructive lower bounds for the Ramsey numbers R(3, t),” J. Combinatorial Theory Ser. B 57 (1993), 150–155.
R. Cleve and P. Dagum, “A constructive Ω(t 1.26) lower bound for the Ramsey number R(3, t),” Inter. Comp. Sci. Inst. Tech. Rep. TR-89-009, 1989.
H. Davenport, Multiplicative Number Theory, Springer Verlag, 1980 (Second Edition).
P. Erdös, “Graph Theory and Probability,” Canad. J. Math. 11 (1959), 34–38.
P. Erdös, “Graph Theory and Probability, II,” Canad. J. Math. 13 (1961), 346–352.
P. Erdös, “On the construction of certain graphs,” J. Combinatorial Theory 1 (1966), 149–153.
L. Lovász, Combinatorial Problems and Exercises, North Holland, Amsterdam, 1979, Problem 11.8.
A. Lubotzky, R. Phillips, and P. Sarnak, “Explicit expanders and the Ramanujan conjectures,” Proc. 18 th ACM STOC (1986), 240–246. See also: “Ramanujan graphs,” Combinatorica 8 (1988), 261–277.
G. A. Margulis, “Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators,” Problemy Peredachi Informatsii 24 (1988), 51–60 (in Russian). English translation in Problems of Information Transmission 24 (1988), 39–46.
F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North Holland, Amsterdam, 1977.
J.B. Shearer, “A note on the independence number of a triangle-free graph,” Discrete Math. 46 (1983), 83–87.
J. Spencer, “Asymptotic lower bounds for Ramsey functions,” Discrete Math. 20 (1977), 69–76.
R.M. Tanner, “Explicit construction of concentrators from generalized N-gons,” SIAM J. Alg. Disc. Meth. 5 (1984), 287–293.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Alon, N. Tough Ramsey Graphs Without Short Cycles. Journal of Algebraic Combinatorics 4, 189–195 (1995). https://doi.org/10.1023/A:1022453926717
Issue Date:
DOI: https://doi.org/10.1023/A:1022453926717