The clique numbers of regular graphs

Abstract

Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a, b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω, d) and max(ω, d) as follows: min(ω, d) := min{ω(G) : G ∈ R(d)} and max(ω, d) := max{ω(G) : G ∈ R(d)}, where R(d) is the graph of realizations of d. Thus the two invariants a := min(ω, d) and b :=max(ω, d) naturally arise. For a graphic degree sequence d = rn := (r, r,..., r) where r is the vertex degree and n is the number of vertices, the exact values of a and b are found in all situations. Since the independence number, α(G) = ω(Ḡ), we obtain parallel results for the independence number of graphs.