General Properties of Some Families of Graphs Defined by Systems of Equations

摘要

In this paper we present a simple method for constructing infinite families of graphs defined by a class of systems of equations over commutative rings. We show that the graphs in all such families possess some general properties including regularity and biregularity, existence of special vertex colorings, and existence of covering maps-hence, embedded spectra-between every two members of the same family. Another general property, recently discovered, is that nearly every graph constructed in this manner edge-decomposes either the complete, or complete bipartite, graph which it spans. In many instances, specializations of these constructions have proved useful in various graph theory problems, but especially in many extremal problems. A short survey of the related results is included. We also show that the edge-decomposition property allows one to improve existing lower bounds for some multicolor Ramsey numbers.