In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition o...In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition of K n is introduced.It is showed that an optimal complete multipartite decomposition of type 1 of K n is a normal complete multipartite decomposition.As for any complete multipartite decomposition of K n,there is a derived complete multipartite decomposition for Q n.It is also showed that any optimal complete multipartite decomposition of type 1 of Q n is a derived decomposition of an optimal complete multipartite decomposition of type 1 of K n.Besides,some structural properties of an optimal complete multipartite decomposition of type 1 of K n are given.展开更多
The chromatically uniqueness of bipartite graphs K(m, n)- A(|A|=2) was studied. With comparing the numbers of partitions into r color classes of two chromatically equivalent graphs, one general numerical condition gua...The chromatically uniqueness of bipartite graphs K(m, n)- A(|A|=2) was studied. With comparing the numbers of partitions into r color classes of two chromatically equivalent graphs, one general numerical condition guaranteeing that K(m, n)-A(|A|=2) is chromatically unique were obtained. This covers and improves the former correlative results.展开更多
With its comprehensive application in network information engineering (e.g. dynamic spectrum allocation under different distance constraints) and in network combination optimization (e.g. safe storage of deleterious m...With its comprehensive application in network information engineering (e.g. dynamic spectrum allocation under different distance constraints) and in network combination optimization (e.g. safe storage of deleterious materials), the graphs ’ cloring theory and chromatic uniqueness theory have been the forward position of graph theory research. The later concerns the equivalent classification of graphs with their color polynomials and the determination of uniqueness of some equivalent classification under isomorphism. In this paper, by introducing the concept of chromatic normality and comparing the number of partitions of two chromatically equivalent graphs, a general numerical condition guarenteeing that bipartite graphs K(m, n)-A (AE(K(m, n)) and |A|≥2) is chromatically unique was obtained and a lot of chromatic uniqueness graphs of bipartite graphs K(m,n)-A were determined. The results obtained in this paper were general. And the results cover and extend the majority of the relevant results obtained within the world.展开更多
Let P（G,λ） be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P（H,λ） = P（G,λ） implies that H is isomorphic to G. Many sufficient conditions guarantee...Let P（G,λ） be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P（H,λ） = P（G,λ） implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 〉 1/3m2 ＋ 3/1k2 ＋ 3/1mk＋ 1/3m-1/3k＋ 3/2√m2 ＋ k2 ＋ mk, where n,k and m are non-negative integers, then the complete tripartite graph K（n - m,n,n ＋ k） is chromatically unique （or simply χ–unique）. In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 3/1m2 ＋ 3/1k2 ＋ 3/1mk ＋ 3/1m - 3/1k ＋ 43, then the complete tripartite graph K（n - m,n,n ＋ k） is χ–unique, which is an improvement on Zou Hui-wen’s result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture.展开更多
设P(G,λ)是图G的色多项式.如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.通过比较图的特征子图的个数,讨论了由文献[Koh K M,Teo K L.The search for chromatically unique graphs.Graphs and Combinatorics,1999,6:2...设P(G,λ)是图G的色多项式.如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.通过比较图的特征子图的个数,讨论了由文献[Koh K M,Teo K L.The search for chromatically unique graphs.Graphs and Combinatorics,1999,6:259-285]中提出的猜想(若n≥k+2,则完全三部图K(n-k,n,n)是色唯一图);推广了文献[Liu Ru-yin,Zhao Hai-xing,Ye Cheng-fu.A complete solution to a conjecture on chromatic unique of complete tripartite graphs.Discrete Mathematics,2004,289:175-179]中的结果(若n≥k+2≥4,则K(n-k,n,n)是色唯一图;若n≥2k≥4,则K(n-k,n-1,n)是色唯一图);证明了若n≥k+2≥4,则K(n-k,n,…,n)是色唯一图,若n≥k+2≥4,则K(n-k,n-1,n,…,n)是色唯一图.展开更多
基金Supported by the National Natural Science Foundation of China( 1 0 2 71 1 1 0 )
文摘In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition of K n is introduced.It is showed that an optimal complete multipartite decomposition of type 1 of K n is a normal complete multipartite decomposition.As for any complete multipartite decomposition of K n,there is a derived complete multipartite decomposition for Q n.It is also showed that any optimal complete multipartite decomposition of type 1 of Q n is a derived decomposition of an optimal complete multipartite decomposition of type 1 of K n.Besides,some structural properties of an optimal complete multipartite decomposition of type 1 of K n are given.
基金Supported by the Natural Science Foundation of Jiangxi , China (No.0511006)
文摘The chromatically uniqueness of bipartite graphs K(m, n)- A(|A|=2) was studied. With comparing the numbers of partitions into r color classes of two chromatically equivalent graphs, one general numerical condition guaranteeing that K(m, n)-A(|A|=2) is chromatically unique were obtained. This covers and improves the former correlative results.
基金Natural Science Foundation of Fujian, China (No.S0650011)
文摘With its comprehensive application in network information engineering (e.g. dynamic spectrum allocation under different distance constraints) and in network combination optimization (e.g. safe storage of deleterious materials), the graphs ’ cloring theory and chromatic uniqueness theory have been the forward position of graph theory research. The later concerns the equivalent classification of graphs with their color polynomials and the determination of uniqueness of some equivalent classification under isomorphism. In this paper, by introducing the concept of chromatic normality and comparing the number of partitions of two chromatically equivalent graphs, a general numerical condition guarenteeing that bipartite graphs K(m, n)-A (AE(K(m, n)) and |A|≥2) is chromatically unique was obtained and a lot of chromatic uniqueness graphs of bipartite graphs K(m,n)-A were determined. The results obtained in this paper were general. And the results cover and extend the majority of the relevant results obtained within the world.
基金Supported by the National Natural Science Foundation of China (Grant No.10771091)the Science and Research Project of the Education Department of Gansu Province (Grant No.0501-02)
文摘Let P（G,λ） be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P（H,λ） = P（G,λ） implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 〉 1/3m2 ＋ 3/1k2 ＋ 3/1mk＋ 1/3m-1/3k＋ 3/2√m2 ＋ k2 ＋ mk, where n,k and m are non-negative integers, then the complete tripartite graph K（n - m,n,n ＋ k） is chromatically unique （or simply χ–unique）. In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 3/1m2 ＋ 3/1k2 ＋ 3/1mk ＋ 3/1m - 3/1k ＋ 43, then the complete tripartite graph K（n - m,n,n ＋ k） is χ–unique, which is an improvement on Zou Hui-wen’s result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture.
文摘设P(G,λ)是图G的色多项式.如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.通过比较图的特征子图的个数,讨论了由文献[Koh K M,Teo K L.The search for chromatically unique graphs.Graphs and Combinatorics,1999,6:259-285]中提出的猜想(若n≥k+2,则完全三部图K(n-k,n,n)是色唯一图);推广了文献[Liu Ru-yin,Zhao Hai-xing,Ye Cheng-fu.A complete solution to a conjecture on chromatic unique of complete tripartite graphs.Discrete Mathematics,2004,289:175-179]中的结果(若n≥k+2≥4,则K(n-k,n,n)是色唯一图;若n≥2k≥4,则K(n-k,n-1,n)是色唯一图);证明了若n≥k+2≥4,则K(n-k,n,…,n)是色唯一图,若n≥k+2≥4,则K(n-k,n-1,n,…,n)是色唯一图.
