圖的距離二標號多項式.pdf

1、圖的著色問題是圖論中的經(jīng)典問題之一，給定圖G，正整數(shù)k，圖G的一個著色f是指一個從頂點集合V(G)到整數(shù)集{1,…,K}的映射，使得，著色問題的主要研究內容之一就是求解圖的色數(shù)X(G)。近年出現(xiàn)的圖的L(p,q)-標號是頻道分配問題的一種特殊模型，它可以被看成是圖的經(jīng)典著色的推廣。給定圖G，正整數(shù)K，圖G的一個k-L(p,q)-標號g是一個從V(G)道{0,1,…,k-1}的映射，使得，
　　 近些年來，L（p,q）-標號的研究

2、取得了很多成果.但是我們發(fā)現(xiàn)，關于L(p,q)-標號的計數(shù)的問題卻沒有被充分研究過.有鑒于色多項式對著色問題的重要意義，對距離2標號的對應問題的研究顯得很有必要.本文中，我們把色多項式的概念推廣，得到了L(p,q)-標號函數(shù)Np,q（G;k）的概念，給定圖G，我們Np,q（G;K)k=k0指的是G的所有k0-L(p,q)-標號的數(shù)目.
　　 第二章中，我們證明了，對所有的圖G,N1,1（G;K）,N2,l（G;K),N1.2（G