给定团数的图的距离无符号拉普拉斯谱半径

The Distance Signless Laplacian Spectral Radii of Graphs with Given Clique Number

设G是n阶简单连通图,T(G)表示图G的点传递度对角矩阵,D(G)表示距离矩阵,G的距离无符号拉普拉斯矩阵定义为:Q(G)=T(G)+D(G),相应的谱半径(即最大特征值)记作q^D(G).图G中一个相互邻接的顶点子集称为G的一个团,定义G的团数为其最大团的顶点个数,记作ω(G).图G的一个正常着色是指使得G中任意2个相邻的顶点着不同颜色的一种着色方案.在G的所有正常着色中,所需颜色数目的最小值称为G的色数,记作!(G).显见,!(G)≥ω(G).为了研究给定团数ω(G)=ω的n阶简单连通图G中取得最小距离无符号拉普拉斯谱半径的极图,文中综合运用代数、矩阵论与图论等方法,分如下2种情形进行讨论:(1)!(G)=ω(G)=ω;(2)X(G)>ω(G)=ω.证明了Turan图T_(n,ω)是团数为ω的n阶简单连通图中具有最小距离无符号拉普拉斯谱半径的唯一图.

Let G be a simple connected graph,T（G） be the diagonal matrix of vertex transmission of G and D（G）be the distance matrix of G,the distance signless Laplacian matrix of G is the n×n matrix defined as Q（G） = T（G） ＋D（G）,and the distance signless Laplacian spectral radius of G,denoted by q^D（G）. Recall that a clique of a graph is a set of mutually adjacent vertices and the clique number ω（G） is the number of vertices in the largest clique in G. The chromatic number X（G） is the smallest number of colors needed to color the vertices of G such that any two adjacent vertices have different colors. It is clear that !（ G） ≥ω（ G）. In order to look for what＇s the extremal graph with the minimal distance signless Laplacian spectral radius among all simple connected graphs with given clique number ω,this paper investigates the following two cases by combining the methods in the graph theory,algebra and matrix theory：（1）X（G） = ω（G） = ω;（2）x（G） ω（G） = ω,and shows that Turan graph T_（n,ω） is the unique graph having the minimal distance signless Laplacian spectral radius among all simple connected graphs with n vertices and given clique number ω.