Nathan Karst
  • Home
  • Teaching
  • Research

Research update: L(d,1)-labelings

5/27/2013

0 Comments

 
With summer here, I've had some time to square away some projects I've been working on. It's been great to reconnect with them after all the craziness that comes with the end of the semester. I'll devote a post to each of the projects I've been working on over the last little while. 

Denise Troxell, Sarah Adams and I advise a group of Olin undergraduates who work on discrete problems, usually centered on $L(d,1)$-labelings of graphs. This research stems from the frequency assignment problem in wireless communications: how do you assign frequency bands to spatially distributed transmitters such that transmitters that are in close proximity to one another use frequencies that are sufficiently spectrally separated to avoid interference? 

Mathematically, we consider the transmitters to be the vertices of a graph $G$, with vertices $x$ and $y$ adjacent if the associated transmitters are closer than some distance threshold. We can then think of a "good'' frequency assignment as a function $f : V(G) \rightarrow \{0,1,2,...,c\}$ such that $|f(x) - f(y)| \geq d$ if $x$ and $y$ are adjacent and $|f(x) - f(y)| \geq 1$ if $x$ and $y$ are at distance 2 in $G$. This is an $L(d,1)$-labeling of $G$. For a fixed graph $G$, the minimum value of $c$ over all $L(d,1)$-labelings is denoted $\lambda_d(G)$. A  lot of work has been dedicated to determining $\lambda_d(G)$. The major open conjecture in the field was made by Griggs and Yeh and states that $\lambda_2(G) \leq \Delta^2$, where $\Delta$ is the maximum degree of $G$.  Georges, Mauro, and Whittlesey show that determining $\lambda_d(G)$ is NP-Complete in general. This has motivated many researchers, including those in our group, to investigate classes of graphs that are of practical or theoretical interest. 

Our newest piece of work, just accepted to the Journal of Combinatorial Optimization, deals with so-called edge-path replacement graphs. Here we replace each edge of a graph $G$ with a path $P_k$ on $k$ vertices to form $G(P_k)$. This is a really interesting problem, because degree and distance play such large roles in $L(d,1)$-labelings. By adding these paths, we're in some sense increasing the distance  between high degree vertices while at the same time preserving the maximum degree of the graph. 

Picture
Our solution to this problem involved decomposing $G$ using a 2-factorization, and then labeling each of the 2-factor separately using a specific scheme. The results prove a conjecture made by Lu: for any graph $G$ with $\Delta \geq 2$, $\lambda_2(G(P_4)) \leq \Delta + 2$. Ours are significantly more general: for any graph $G$ with $\Delta  > 2$, $\lambda_d(G(P_k)) \leq d + \lceil \Delta /2 \rceil + \max ( \lceil \Delta / 2 \rceil, d) $ for any $d \geq 2$ and $k \geq 4$. The case with $\Delta \leq 2$ deals with graphs that are unions of paths and cycles, and the $L(d,1)$-labelings of these graphs are well understood. The case of $k = 3$ is the so-called total  labeling of $G$ and is significantly harder. In some cases we can do a little bit better than the bounds I've quoted here. 

All in all, the project was a great team effort. It's great to work with such bright and motivated undergrads. It looks like both Jessica and Jason are going to stick around next semester, so look for more great work to come from these two.
0 Comments



Leave a Reply.

    Archives

    June 2015
    May 2015
    February 2015
    December 2014
    October 2014
    September 2014
    August 2014
    July 2014
    May 2014
    March 2014
    February 2014
    January 2014
    December 2013
    October 2013
    July 2013
    June 2013
    May 2013
    April 2013
    March 2013
    February 2013
    January 2013

    Nathan Karst

    Doing and teaching mathematics. 

    Categories

    All

    RSS Feed

Powered by Create your own unique website with customizable templates.
Photo used under Creative Commons from ByoLogyc