Evènement pour le groupe GT Graphes et Applications

Date 2011-05-27  14:00-15:00
Titre2-dipath 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, 2-dipath 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 2-dipath L(2,1) labeling which is also an oriented coloring). In this talk, we have improved the existing bounds for 2-dipath 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.  
LieuSalle 178 
OrateurSagnik Sen 

Aucun document lié à cet événement.

Retour à l'index