The Clique Numbers of Regular Graphs |
| |
Authors: | Narong Punnim |
| |
Affiliation: | (1) Department of Mathematics, Srinakharinwirot University, Sukhumvit 23, Bangkok 10110, Thailand. e-mail: narongp@psm.swu.ac.th, TH |
| |
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: where 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=r n :=(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)=ω(Gˉ), we obtain parallel results for the independence number of graphs. Received: October, 2001 Final version received: July 25, 2002 RID="*" ID="*" Work supported by The Thailand Research Fund, under the grant number BRG/09/2545 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|