Infinite families of crossing-critical graphs with given average degree Article uri icon

abstract

  • In their paper on minimal graphs with crossing number at least k (or, equivalently, k-crossing-critical graphs) (J. Combin. Theory Ser. B 58 (2) (1993) 217-224) Richter and Thomassen described a construction of an infinite family of 4-regular 3-crossing-critical graphs. They also showed that no infinite family of 6-regular k-crossing-critical graphs exists. In this paper we generalize the Richter and Thomassen construction, and prove the following result: for each rational number q[4,6) there is an infinite family of graphs that are k-crossing-critical for the same integer k, each of which has average degree q. Moreover, we show that for each rational number q[4,6) this statement holds for infinitely many values of k. © 2003 Elsevier B.V. All rights reserved.

publication date

  • 2003-01-01