Abstract | ||
---|---|---|
Let G be a simple graph with n vertices and let G c be its complement. Let ρ ( G ) be the spectral radius of adjacency matrix A ( G ) of G. In this paper, a sharp upper bound of the Nordhaus–Gaddum type is obtained: ρ(G)+ρ(G c )⩽ 2− 1 k − 1 k ̄ n(n−1) , where k and k̄ are the chromatic numbers of G and G c , respectively. Equality holds if and only if G is a complete graph or an empty graph. MSC 05C50 05C99 Keywords Complementary graph Chromatic number Spectral radius |
Year | DOI | Venue |
---|---|---|
2000 | 10.1016/S0012-365X(99)90280-7 | Discrete Mathematics |
Keywords | Field | DocType |
spectral radius,nordhaus-gaddum type,complete graph,adjacency matrix,upper bound | Discrete mathematics,Strongly regular graph,Combinatorics,Graph energy,Graph power,Bound graph,Regular graph,Distance-regular graph,Petersen graph,Windmill graph,Mathematics | Journal |
Volume | Issue | ISSN |
211 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
10 | 1.39 | 0 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yuan Hong | 1 | 50 | 8.20 |
Jinlong Shu | 2 | 99 | 24.28 |