We consider extensions of Turán's original theorem of 1941 to planar grids. For a complete kxm array of vertices, we establish in Proposition 4.3 an exact formula for the maximal number of edges possible without any square regions. We establish with Theorem 4.12 an upper bound and with Theorem 4.15 an asymptotic lower bound for the maximal number of edges on a general grid graph with n vertices and no rectangles.
Frank Morgan, Department of Mathematics and Statistics Williams College Frank.Morgan@williams.edu
"Extensions of Extremal Graph Theory to Grids,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 10
, Article 10.
Available at: http://scholar.rose-hulman.edu/rhumj/vol10/iss2/10