journal6 ›› 2009, Vol. 30 ›› Issue (4): 4-6.

• 数学 • 上一篇    下一篇

色数与谱半径和生成偶子图

  

  1. (湖州师范学院理学院,浙江 湖州313000)
  • 出版日期:2009-07-25 发布日期:2012-04-22

Chromatic Number,Spectral Radius and Spanning Bipartite Subgraph

  1. (Faculty of Science,Huzhou Teachers’ College,Huzhou 313000,Zhejiang China)
  • Online:2009-07-25 Published:2012-04-22
  • About author:FANG Kun-fu(1963-),male,was born in Tongxiang,Zhejiang Province,associate professor;research area are graph theory and its applications.
  • Supported by:

    Natural Science Foundation of China (10671074)

摘要:设G为n≥1 阶简单无向图,ρ(G)和μ(G)分别表示图G的邻接谱谱半径和Laplacian谱谱半径.利用生成偶子图证明了:当k为偶数时,ρ(G)≤(k-1)/kμ(G);当k为奇数时,ρ(G)≤k/(k+1)μ(G).其中k(≥1)为简单图G的色数.

关键词: 谱半径, Laplacian谱半径, 色数, 生成偶子图

Abstract: Let  G be a simple undirected graph with order n≥1.Denote by ρ(G) and μ(G) the spectral radius of the adjacency matrix and the Laplacian matrix of G,respectively.In this paper,by the way of spanning bipartite subgraphs,it is  showed that:let G be a simple graph with chromatic number k≥1.If k is even,ρ(G)≤(k-1)/kμ(G);if  k is odd,ρ(G)≤k/(k+1)μ(G).

Key words: spectral radius, Laplacian spectral radius, chromatic number, spanning bipartite subgraph

公众号 电子书橱 超星期刊 手机浏览 在线QQ