Dissertation > Excellent graduate degree dissertation topics show

L(d, 1)-Labeling of Graphs

Author: TangYuXiang
Tutor: WangWeiFan
School: Zhejiang Normal University
Course: Operational Research and Cybernetics
Keywords: L(d,1)-labelling 2-outerplanar graph Generalized Petersen graph Planar grids Triangular grids Channel assignment
CLC: O157.5
Type: Master's thesis
Year: 2009
Downloads: 12
Quote: 0
Read: Download Dissertation

Abstract


All graphs considered in this paper are finite simple graphs.For a graph G,we denote its vertex set,edge set and maximum degree by V（G）,E（G） andΔ（G） respectively. A k-L（d,1）-labelling of a graph G is a function f from its vertex set V（G） to the label set {0,1,…,k} such that |f（x）-f（y）|≥d if z and y are adjacent,and |f（x）-f（y）|≥1 if x and y are at distance 2.The L（d,1）-labelling numberλd（G） of G is the smallest k such that G has a k-L（d,1）-labelling.The L（2,1）-labelling of a graph arose from a variation of the Frequency Channel Assignment problem introduced by Hale.This subject has been studied rather extensively in recent years.In 1992,Griggs and Yeh conjectured thatλ2（G）≤Δ2（G） for any graph G withΔ（G）≥2.The best known upper boundΔ2（G） +Δ（G） - 2 forλ2（G） was established by Goncalves.In this thesis,we consider the L（d,1）-labelling for some graphs.In Chapter 1,we collect some basic notions used in the thesis and give a chief survey on this direction.In Chapter 2,3,4,5,we study the labeling problem of 2-outerplanar graphs,Generalized Petersen graphs,Planar grids,Triangular grids.Our main results in the present paper are as follows:（1） Forevery 2-outerplanar graph G,λ2（G）≤Δ（G） + 12.（2） For every Generalized Petersen graph P（G）,if d≥3 and n≥3,thenλd（P（n））≤3d + 3.（3） Characterize the L（d,1）-labelling number of planar grids and triangular grids.

Related Dissertations

  1. The Research on Incidence Coloring and Incidence Game Coloring of Saveral Types of Graphs,O157.5
  2. Strong Edge-coloring of Some Special Classes of Graphs,O157.5
  3. The Lower Bound of the Number of 1-Factors of Generalized Petersen Graph P(N,3),O157.5
  4. The Conditional Coloring and L (2, 1)-labeling of Generalized Petersen Graphs,O157.5
  5. Conditional Coloring of 3-regular Graphs,O157.5
  6. Two Kinds of Graph Coloring Problems Related to the Channel Assignment,O157.5
  7. Star-Edge Coloring of Some Special Classes of Graphs,O157.5
  8. On （a, d）-Antimagic Labelings of Generalized Petersen Grapgs and Radio Number of P2□Pn,O157.5
  9. Research on Equitable Total Coloring and Rainbow Domination of Some Graphs,O157.5
  10. The Research on (d, 1)-labelling and (2, 1)-labelling in Some Graphs,O157.5
  11. The Domination Parameters of Generalized Petersen Graphs and Circulant Graphs,O157.5
  12. Research & Development of Teaching Simulation System for NC Programme Experiment,TG659
  13. L(2, 1)-labeling of 3-regular Graphs with Perfect Matching and the Optimal Labeling of Caterpillar,O157.5
  14. The Cubic Graph and its associated graph crossing number problem,O157.5
  15. Cyclic graph crossing number C (n; {1, k}),O157.5
  16. Researches on the Crossing Numbers of Some Graphs,O157.5
  17. Research on Crossing Numbers and Some other Problems in Graph Theory,O157.5
  18. Research on Some Selected Graph Labeling Topics in Graph Theory,TP391.41
  19. Chinese Named Entity Recognition Based on Conditional Random Fields,TP391.43
  20. Researches on Theories and Technologies of Capacity and Channel Assignment in Wireless Mesh Networks (WMNs),TN92

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