Infinite graphs that do not contain cycles of length four

2014/01/18 by Javier Cilleruelo, Cilleruelo, Javier
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT) #math.CO #math.NT

paper · pdf · doi:10.48550/arxiv.1401.4502

This paper has been withdrawn because we have found an easier proof of the result

arxiv created 2016/01/22 · arxiv updated 2016/01/25

Abstract

We construct a countable infinite graph G that does not contain cycles of length four having the property that the sequence of graphs G_n induced by the first n vertices has minimum degree δ(G_n)> n^{√(2)-1+o(1)}.

Related

• Excluding Degree Sequences of Cycles
• Graphs with no 2δ+ 1 cycle
• Graphs with degree sequence \m^m-1,n^n-1\ and \mⁿ,n^m\
• Vertex degrees close to the average degree
• Cycles of Length 4 or 8 in Graphs with Diameter 2 and Minimum Degree at Least 3