
Evènement pour le groupe GT Graphes et Applications
Date  20110527 14:0015:00 
Titre  2dipath and oriented L(2,1)labelings of some families of oriented planar graphs 
Résumé  To distinguish close and very close transmitters in a wireless communication system, Griggs and Yeh proposed a variation of the Frequency Assignment Problem (or simply FAP) by introducing the notion of L(2,1) labeling. A feature of this graph theoretic models for FAP was that, communication was assumed to be possible in both directions (duplex) between two radio transmitters and, therefore, these models were based on undirected graphs. But in reality, to model FAP on directed or oriented graphs could be interesting, was pointed by Aardal et al in their survey. There are two different L(2,1) labelings of oriented graphs, namely, 2dipath L(2,1) labeling (that is, a vertex labeling with non negative integers, such that, the label difference for adjacent vertices is at least 2 and for vertices at directed distance 2 is at least 1) and oriented L(2,1) labeling (that is, a 2dipath L(2,1) labeling which is also an oriented coloring).
In this talk, we have improved the existing bounds for 2dipath and oriented L(2,1) span (the minimum possible "largest" value used for the respective labelings) for the class of planar graphs with girth 5, 11, 16, outerplanar, cactus, wheels and leaf independent Halin graphs.

Lieu  Salle 178 
Orateur  Sagnik Sen 
Url  LaBRI 
Aucun document lié à cet événement. RetourRetour à l'index
 