Dissertation > Excellent graduate degree dissertation topics show

The Chromaticity of Certain Complete T-partite Graphs

Author: XuLiMin
Tutor: YangZhiLin
School: Hefei University of Technology
Course: Applied Mathematics
Keywords: chromatically unique graph chromatically equivalent completet-partite graph numbers of partition into color classes numbers ofcharacteristic subgraph
CLC: O157.5
Type: Master's thesis
Year: 2013
Downloads: 6
Quote: 0
Read: Download Dissertation

Abstract


Let P(G,λ) be the chromatic polynomial of a graph G. Two graphs are chromatically equivalent, symbolically G~H, if P(G,λ)=P(H,λ). A graph G is chromatically unique, if for any graph H with H~G implies G≌H. The notion of the chromatic uniqueness was first introduced by Chao and Whitehead in1978. Since then, the problems of chromatic uniqueness of the complete t-partite graphs still are studied. Koh K M and Teo K L have summarized achievements and problems that were studied before that in1990and1997in ref [Koh K M, Teo K L. The search for chromatically unique graphs[J]. Graphs and Combinatorics,1990,6:259-285; KOH K M, TEO K L. The search for chromatically unique graphs-Ⅱ [J].Discrete Mathematics,1997(172):59-78.]. Among them, the famous problem (for|n1-n1|≤2and i,j=1,2,…,t, if min{n1,n2,…,n1} is sufficiently, is the complete t-partite graph K(nl,n2,…nt) chromatically unique?) and the conjecture (The complete tripartite graph K(n-k,n,n) is chromatically unique if n≥k+2≥4.) have be solved in ref [Zhao Hai xing, Li Xue-liang, Liu Ru-ying, et al. The chromaticity of certain complete multipartite graphs [J]. Graphs and Combinatorics,2004,20:423-434; Liu Ruyin, Zhao Hal xing, Ye Cheng-fu. A complete solution to a conjecture on chromalic unique of complete tripartite graphs[J].Discrete Mathematics,2004,289:175-179.]. They proved that the complete tripartite graph K(n-k,n,n) is chromatically unique if n>k+2>4, and the complete tripartite graph K(n-k,n-1,n) is chromatically unique if n>2k>4, the compete t-partite graph K(n1,n2,…,nt) is chromatically unique for|ni-nj|≤k (i,j=1,2,…,) if min{n1,n2,…;nt}≥tk2/4+k√2(t-T1/2+1. In ref [Su Ke Yi, Chen Xiang En. A note on chromatic uniqueness of completely tripartite graphs[J].Journal of Mathematical Research&Expsition,2010,30(2):233-240.], Su Ke Yi and Chen Xiang En showed that K(n-v,n,n+k) is chromatically unique for v≥2and k≥0if n≥3/1(k2+v2+kv+v-k+4),and they present a conjecture (Ifn≥3/1(k2+v2+kv+v-k+4), then K(n-v,n,n+k) is chromatically unique, where v=0and k≥4,orv=1and k≥3.). In ref [LAU.G.C, PENG.Y.H. Chromatic uniqueness of certain complete tripartite graphs[J].Acta Mathematica Sinica, English Series,2011,27(5):919-926.], LAU.G.C and PENG.Y.H showed that K(n-k,n-v,n) is chromatically unique for n≥4/1k2+v+1, where2≤v≤4and k≥v, they present a conjecture (If n≥4/1k2+v+1and k≥v≥2, the graph K(n-k,n-v,n) is chromatically unique.In the paper,by compa ring the number of triangles in graphs and the number of cycles of4一order without chords in graphs and the numbers of partition into t+1color classes,proved the following results. The complete t-partite graph K(n+α1,n+α2,…,n+αt) is chromatically unique if min{n+αa,n+α2,…,n+αt}≥2/1{∑1<i<t..,αi2-2t/1(∑1<i<t..,αi;)2+1;The complete tripartite graph K(n,n+v,n+k)is chromatically unique if n>(k-1)2/4and4≤v+2≤k≤2v; The complete t-partite graph K(n-k,n-2,…,n)is chromatically unique if n>2and n>(k+1)2/4+1,etc.

Related Dissertations

  1. Several three chromatic uniqueness,O157.5
  2. The Uniqueness of Chromaticity of Some Kinds of Graphs and Maximal Energy of Trees,O157.5
  3. Several types of chromatic uniqueness,O157.5
  4. On Ohba’s Conjecture of One Class of Complete Multipartite Graphs,O157.5
  5. Some Properties of Perfect Matchings of 4 Ary n Cubes,O157.5
  6. Research on Detecting Complex Network Community Structure,O157.5
  7. The Number of Subtress of Graph and Reliability of Networks,O157.5
  8. The Signless Laplacian Spectral Radius with Some Graphs,O157.5
  9. The composite equilibrium existence of the network and its algorithm,O157.5
  10. Network based on the provision of public goods countermeasures study strategic interaction and equilibrium problems,O157.5
  11. The Chromaticity of Several Classes of Graphs and the Fifth Coefficient of Adjoint Polynormial,O157.5
  12. Several three chromatic uniqueness,O157.5
  13. Consensus in Complex Dynamic Network of Multi-Agent Based on LMI Method,O157.5
  14. K5-Minor-Free Graphs Are Acyclically 5-Colorable,O157.5
  15. On Radio Colorings and Hamiltonian Colorings of Some Graphs,O157.5
  16. Local twisted cube graph crossing number of,O157.5
  17. Attack directed repair complex network invulnerability Strategy,O157.5
  18. Simulation and Analysis of Social Learning Model Besed on Expert Agents,O157.5
  19. Markov chains in the use of biological networks,O157.5
  20. Research of Hierarchical Community Structure in Complex Network Based on Maximal-Degree Node,O157.5
  21. Research and application of time series of the causal relationship between Grainger triggered the complex network analysis method based on,O157.5

CLC: > Mathematical sciences and chemical > Mathematics > Algebra,number theory, portfolio theory > Combinatorics ( combinatorics ) > Graph Theory
© 2012 www.DissertationTopic.Net  Mobile