Dissertation > Excellent graduate degree dissertation topics show

The L(2,1)-Labelings on General Mycielski Graphs and Full-Colorable Graphs

Author: ZhaoXiaoLing
Tutor: LvChangHong
School: East China Normal University
Course: Operational Research and Cybernetics
Keywords: Generalized Mycielski Graphs L (2,1) label Can be full of coloring Figure Halin graphs
CLC: O157.5
Type: Master's thesis
Year: 2008
Downloads: 13
Quote: 0
Read: Download Dissertation

Abstract


Figure label is an important research branch of graph theory, a wide range of applications in real life. For general graphs, determine the exact value of the label number is an NP-hard problem. For some special graphs, we can explore their precise value and the upper and lower bounds of the labeling number. This paper introduces the research progress of the labeling problem on the L (2,1) and I work in this regard, including the following three parts: (1) generalized Mycielski graphs L (2,1) label number ; (2) Discussion of the special structure of the Figure with λ (G) = (?) (G) the nature of; (3) discussed the constraint condition is extended to the reference numerals of the three Figure. In the first part, the paper has been of general Mycielski following special map map L (2,1) labeling number of conclusions: (1) Order M p (P n ) Road P n General Mycielski, λ (M p (P n )) = 4 when n = 2, p ≥ 2; λ (M , p (the P n )) = 5 when n = 3, p = 2; λ (M p (P n )) = 6 when n ≥ 3, p ≥ 3. (2) M p (K 1, n-1 ) the star map K 1, n-1 ) Generalized Mycielski Figure (n ≥ 4), the λ \/ sub> (K 1, n-1 )) = 2n when the p ≥ 3. (3) Order the M p (K n ) K n General Mycielski graph, then λ (M p (the K n )) = 4 when n = 2; λ (M , p (the K n )) = 3n-2 when n ≥ 3. (4) Order M p (C n ) is a circle C n Generalized Mycielski graph, then λ (the M p (C n )) = 7 when n = 3,4,5. In the second part of the article discusses the problem of the continuous label. some K 2 of disjoint union. Both having λ (G) = (?) (G) The nature of the Figure, all of which are not in communication FIG. In this paper, we consider the general Mycielski special structure connected graph, with the nature of the λ (G) = (?) (G) of a connected graph. In the third part, we study constraints label promotion of three. Discuss a generalized Halin graphs and complete graph Mycielski graph L (3,2,1) the upper bound of the labeling number, get the following conclusions: (1) Let G with maximum degree △ Halin graphs λ 3,2.1 (G) ≤ 5 △ 16. (2) Order the M p (K n ) is K n generalized Mycielski graphs, λ 3,2,1 < / sub> (M p (K n )) ≤ 7n-4.

Related Dissertations

  1. Study on the Technology of Control Plane in the Interconnection Network Based on the Intergraded Node,TN929.1
  2. Research on Key Technology in GMPLS Based Optical Burst Switch Networks,TN929.1
  3. Studies on Anti-collision Algorithms Used in UHF RFID,TP391.44
  4. The Research and Implementation of Contour Map Algorithm and Its Application in Multi-dimensional Oil-gas System,P285.1
  5. Based on MPLS / VPN technology research program to build an Intranet,TP393.4
  6. UHF RFID anti- collision algorithm,TP391.44
  7. Design and Implement on Encoding and Decoding Module for Wireless Communication Systems,TP391.44
  8. Chinese BBS Information Extraction and Classification,TP393.094
  9. Content Management System Based on the Page Label,TP311.52
  10. MPLS-based Next Generation Network Service Quality,TP393.06
  11. Study and Design of UHF RFID Tag Digital System,TP391.44
  12. Study and Realization of Click-Based MPLS Protocol Modules,TN915.04
  13. Simulation and Analysis on OAM of T-MPLS,TN915.09
  14. Research of Text Categorization Algorithm Based on Non-negative Sparse Representation,TP391.1
  15. Design and Manufacture of Micro-optical Label with Active Encryption,TP391.44
  16. Research on Sentiment Label Extraction,TP391.1
  17. Research on User-based Analysis Method in Social Tagging System,TP311.12
  18. Design of Security Gateway Model Based on Stego-Label,TP393.08
  19. Graph’s Optimal Research in Graph-based Semi-supervised Learning,TP181
  20. Prepartion of HMPSA for Label and Study of Influencing Factor on the Properties of HMPSA,TQ436.3
  21. Research on SoC Test Data Compression Based on Partition Coding,TN47

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