SAGEposterAnanda2014
?Download as PPTX, PDF?
0 likes?92 views
This document discusses radio labeling of grid graphs. It defines key terms like radio labeling, radio number, distance between vertices, and diameter. It summarizes recent findings about analyzing the fundamental characteristics of grids to determine bounds on the radio number. New tools have allowed establishing important results about radio numbers of grids and completely determining the radio number for some grids. The document outlines approaches for constructing upper and lower bounds on the radio number for grids and establishing conditions where the bounds meet.
![Let ? ?, ? denote the distance between two vertices u and v on a graph G and let ????(?) denote the diameter of
such a graph ?. A connected graph ? has a radio labeling ? if for all distinct pairs of vertices ? and ? of ?,
? ?, ? + |? ? ? ? ? ¡Ý ???? ? + ?.
Using algebraic and combinatorial techniques, bounds for the radio number of ?? ¡õ ?? can be established. By
analyzing the fundamental characteristics of abstract grids, tools may be developed to state important
findings about the radio number of grids and, ultimately, completely determine the radio number of the grids.
A graph ? is comprised of two main elements: ?, a set of vertices, and ?, a set of edges. Each edge is also defined
by an unordered pair of vertices that the edge connects. For example, in the path graph ?5belows, the vertices are
defined from left-to-right as ?1 through ?5, and edge ?2 connects vertices ?2 and ?3.
The distance ?(??, ??) between two vertices ?? and ?? is the least number of edges connecting ?? and ??. In ?5
above, the shortest path between ?2 and ?5 consists of 3 edges, namely ?2, ?3, and ?4. Thus, ? ?2, ?5 = 5.
The diameter of a graph is the maximum distance between any two vertices of a graph. ???? ?5 = 4 because if
we take the distances between all pairs of, then we see that the greatest distance of 4 lies between ?1 and ?5.
A labeling of a graph is an assignment of labels to vertices. Vertex labels are typically assigned integer values and
all labels in this paper can be assumed to be represented by integers. Furthermore, a labeling of a graph can be
defined by a function or mapping that assigns labels algorithmically. A radio labeling is defined as an assignment
of vertex labels such that all distinct pairs of vertices of a graph satisfy the radio condition (see abstract).
The span of a labeling is the difference between the highest and lowest labels.
The radio number of a graph ?, ??(?), is then the minimum possible span across all radio labelings of ?. In other
words, if all radio labelings of a graph are considered, the radio number is the lowest span that we can find for that
graph under any of those radio labelings.
? Define a na?ve labeling ? accordingly: ? ?? = ? ???1 + ???? ? + 1 ? ?(??, ???1).
? Define a 1st-order pair of vertices as any consecutively labeled vertices. We can think of an
nth-order pair of vertices as any pair of vertices ?? and ??+? for all ? ¡Ý 0.
? The term ¡°bump¡± refers to the increase in span of a labeling associated with the
occurrence of some deviation from a purely distance-maximizing labeling scheme.
? An even grid can be subdivided into four quadrants, defined as ?1, ?2, ?3, and ?4 as
illustrated below. ?1 and ?3 are diagonally opposite quadrants. adjacent quadrants are
quadrants having the characteristic of not being diagonally opposite to one another ¨C e.g., ?1
and ?2.
PROPOSITION 1 (diagonal triple ¡Ø): Let ? be an even grid and ?? a vertex labeled in any
quadrant of grid G. Say ?? and ??+1 are vertices in a diagonally opposite quadrant. Then for
any na?ve labeling ? of ? and any radio labeling ??
of ?,
??
??+? ? ??
???? ¡Ý ? ??+? ? ? ???? + ?,
for any 3 consecutively labeled vertices ???1, ??, and??+1.
LEMMA 1 (¡Ø independent triples): In an even grid ?, given a distance-maximizing labeling
?0 and any labeling ?? that label vertices of ? in the same order,
???? ??
¡Ý ???? ? ? + ¡Ø,
where ¡Ø is the number of diagonal triples that occur in the complete labeling of ? under ??
.
LEMMA 2 (? adjacent flips): Given a distance-maximizing labeling ?0 and a radio labeling
? of an even grid ?,
???? ? ¡Ý ???? ? ? + ? ? ?,
where ? is the number of adjacent flips that occur in the complete labeling of ? under ??
.
LEMMA 3 (¡Ø independent diagonal triples and ? adjacent flips): Let ? be an even grid
with distance-maximizing labeling ? and any other labeling ??
. If ??
contains ¡Ø
independent diagonal triples and ? adjacent flips,
???? ??
¡Ý ???? ? +¡Ø +? ? ?.
In order to establish the upper bound for ?? ?? ¡õ ? ? , we must:
? Specify the labeling order for vertices
? Label ordered vertices with minimum values that satisfy the radio condition
? Compute the span of this labeling ? upper bound of ?? ?? ¡õ ? ?
The span is computed by rearranging the radio condition and summing distances:
? ??+? ¡Ü ???? ? + ? ? ?(??, ??+?) + ?(??)
We determine the minimal value for the last vertex labeled satisfying the radio condition¡
¡apply this to odd grids without loss of generality:
? ?(2?+1)2 ¡Ü ???? ? + 1 ? ?(?(2?+1)2?1,?(2?+1)2) + ?(?(2?+1)2?1)
? ?(2?+1)2?1 ¡Ü ???? ? + 1 ? ?(?(2?+1)2?2,?(2?+1)2?1) + ?(?(2?+1)2?2)
?
? ?1 ¡Ý 0
???? ? = ? ?(2?+1)2 ¡Ü
?=1
?
2? + 1 + 2?(8? ? 1)
THEOREM 1: ?? ? ??+? ¡õ ? ??+? ¡Ü ?? ?
+ ?? ?
+ ?
The lower bound for ?? ?? ¡õ ? ? is established by maximizing distances.
Again, rearranging the radio condition and summing across all vertex pairs gives:
?(??+1) ¡Ý (?2
? 1)(2? ? 1)
?=1
?2?1
?(??+1, ??)
? Let ? denote the row index and ? the column index of a vertex. Then,
? ?=?
? ???
? ??+?, ?? = ? ? ? ? ? + ? ? ? ? ? + ? ? ? ? ? + ? ? ? ? ? + ?
? + ? ? ??? ? ? ? ? + ? ? ??? ? ? ? ?
? If we want to maximize distances, we must label vertices such that the highest row and column
indices are added in the sum, while the lowest are subtracted.
The first and last vertices labeled only contribute 2 indices each to the sum and
we choose arrangements of vertices that maximize the sum to minimize the span¡
THEOREM 2.1: THEOREM 2.2:
?? ? ??+? ¡õ ? ??+? ¡Ý ?? ?
+ ?? ?
? ? ?? ? ?? ¡õ ? ?? ¡Ý ?? ?
? ?? ?
? ?? + ?
[1] Calles, Eduardo and Gomez, Henry, via personal communication and electronic files from C. Wyels
[2] G. Chartrand and Erwin, David and Zhang, Ping and Harary, Frank. Radio labelings of graphs, Bull Inst.
Combin. Appl., 33 (2001), pp. 77-85.
[3] G. Chartrand, D. Erwin, and P. Zhang. A graph labeling problem suggested by FM channel restrictions, Bull
Inst. Combin. Appl., 43 (2005), pp. 43-57.
[4] Liu, Daphne Der-Fen and Zhu, Xuding. Multi-level distance labelings for paths and cycles, Siam J. Discrete
Math., 19 (1993) pp. 610-621.
Allow me to offer my humble gratitude to my wonderful advisor and professor DR.
CYNTHIA WYELS. In addition, I would also like to thank DR. IVONA GRZEGORCZYK,
as well as CSUCI MATHEMATICS for providing such a positive learning environment!
RADIO LABELING SQUARE GRIDS
Dev Ananda Advisor : Dr. Cynthia Wyels Master¡¯s Thesis Project
Path graphs represent the best model for radio labeling square grids because grids are just constructions of paths.
Below are radio labelings of path graph ?4. The first is a radio labeling ? of ?4.The second is a minimal or
optimal radio labeling ??
of ?4 under which the span of the given labeling is as low as possible under the radio
condition for all pairs of vertices.
A grid graph is the Cartesian product of two path graphs, and square grids are composed of
two identical paths. Odd grid ? ? ¡õ ? ? is depicted below as a set of vertices and edges, and
subsequently, as a set of vertices in an array of boxes. The connected set of boxes represent
vertices, and two vertices are considered adjacent if they share an edge. An optimal radio
labeling ? ??????? of the grid is shown using the box representation with label values associated
the corresponding vertex. Here we see that ?? ? ? ¡õ ? ? = ??.
Label Order4 7 2
9 5
6 3 8
3x3 ordering
14 23 7
25 1
20 11 3
4 16 21
6 18 13
10
19
5
15
24
2
12
17
22
8
9
5x5 ordering
k+1,1
k,1
k+1,k+1
1,2k+11,k
2k+1,2k+12k+1,1 2k+1,k 2k+1,k+1
1,1
? The first vertex labeled is ? + ?, ? + ?
? Cyclic labeling proceeds in the order: top
right, top left, bottom left, bottom right
? The distance between each pair of vertices in
the same cycle = ?? + ?
? The distance between pairs of vertices in
consecutive (different) cycles = ??
Substituting inequalities while incorporating the distances that our labeling
order above mandates yields the following general span inequality:
1
Q1
Q3Q4
Q2
??
??+?????
an abstract grid subdivided
into quadrants ?? ¡ú ??
quadrants of ? ? ¡õ ? ?
with a diagonal triple
ACKNOWLEDGEMENTS
ABSTRACT
RADIO LABELING PATHS & GRIDS
RELEVANT DEFINITIONS
NEW FINDINGS, THE BUMP, & CLOSING THE GAP
REFERENCES
CONSTRUCTING THE UPPER BOUND
CONSTRUCTING THE LOWER BOUND
Considerations for advantageous ways of analyzing grids, with regards to the radio number,
allows us to refine bounds and establish conditions in which upper and lower bounds meet.
MOTIVATIONS: THE CHANNEL ASSIGNMENT PROBLEM
Radio labeling, in graph theory, is motivated by a problem originating from the FCC's regulation of
FM radio stations. The FCC categorizes radio stations into classes. Stations are then assigned channels
based on certain factors, including antenna height and signal power. The distances between stations also
affect what channel is assigned to a radio station of a given station class. Radio stations assigned the same
must be some minimum distance apart in order to satisfy FFC regulations. Stations that are in closer
proximity to one another must be channels that are farther apart, after considering station class. This is
called the CHANNEL ASSIGNMENT PROBLEM. Graph theory abstracts this problem from radio
transmitter and tower organizational grids, and its solution is the RADIO NUMBER.](https://image.slidesharecdn.com/c06631ab-bed1-4d13-9cd1-8a3919e8c12d-150608200143-lva1-app6891/85/SAGEposterAnanda2014-1-320.jpg)
SAGEposterAnanda2014
- 1. Let ? ?, ? denote the distance between two vertices u and v on a graph G and let ????(?) denote the diameter of such a graph ?. A connected graph ? has a radio labeling ? if for all distinct pairs of vertices ? and ? of ?, ? ?, ? + |? ? ? ? ? ¡Ý ???? ? + ?. Using algebraic and combinatorial techniques, bounds for the radio number of ?? ¡õ ?? can be established. By analyzing the fundamental characteristics of abstract grids, tools may be developed to state important findings about the radio number of grids and, ultimately, completely determine the radio number of the grids. A graph ? is comprised of two main elements: ?, a set of vertices, and ?, a set of edges. Each edge is also defined by an unordered pair of vertices that the edge connects. For example, in the path graph ?5belows, the vertices are defined from left-to-right as ?1 through ?5, and edge ?2 connects vertices ?2 and ?3. The distance ?(??, ??) between two vertices ?? and ?? is the least number of edges connecting ?? and ??. In ?5 above, the shortest path between ?2 and ?5 consists of 3 edges, namely ?2, ?3, and ?4. Thus, ? ?2, ?5 = 5. The diameter of a graph is the maximum distance between any two vertices of a graph. ???? ?5 = 4 because if we take the distances between all pairs of, then we see that the greatest distance of 4 lies between ?1 and ?5. A labeling of a graph is an assignment of labels to vertices. Vertex labels are typically assigned integer values and all labels in this paper can be assumed to be represented by integers. Furthermore, a labeling of a graph can be defined by a function or mapping that assigns labels algorithmically. A radio labeling is defined as an assignment of vertex labels such that all distinct pairs of vertices of a graph satisfy the radio condition (see abstract). The span of a labeling is the difference between the highest and lowest labels. The radio number of a graph ?, ??(?), is then the minimum possible span across all radio labelings of ?. In other words, if all radio labelings of a graph are considered, the radio number is the lowest span that we can find for that graph under any of those radio labelings. ? Define a na?ve labeling ? accordingly: ? ?? = ? ???1 + ???? ? + 1 ? ?(??, ???1). ? Define a 1st-order pair of vertices as any consecutively labeled vertices. We can think of an nth-order pair of vertices as any pair of vertices ?? and ??+? for all ? ¡Ý 0. ? The term ¡°bump¡± refers to the increase in span of a labeling associated with the occurrence of some deviation from a purely distance-maximizing labeling scheme. ? An even grid can be subdivided into four quadrants, defined as ?1, ?2, ?3, and ?4 as illustrated below. ?1 and ?3 are diagonally opposite quadrants. adjacent quadrants are quadrants having the characteristic of not being diagonally opposite to one another ¨C e.g., ?1 and ?2. PROPOSITION 1 (diagonal triple ¡Ø): Let ? be an even grid and ?? a vertex labeled in any quadrant of grid G. Say ?? and ??+1 are vertices in a diagonally opposite quadrant. Then for any na?ve labeling ? of ? and any radio labeling ?? of ?, ?? ??+? ? ?? ???? ¡Ý ? ??+? ? ? ???? + ?, for any 3 consecutively labeled vertices ???1, ??, and??+1. LEMMA 1 (¡Ø independent triples): In an even grid ?, given a distance-maximizing labeling ?0 and any labeling ?? that label vertices of ? in the same order, ???? ?? ¡Ý ???? ? ? + ¡Ø, where ¡Ø is the number of diagonal triples that occur in the complete labeling of ? under ?? . LEMMA 2 (? adjacent flips): Given a distance-maximizing labeling ?0 and a radio labeling ? of an even grid ?, ???? ? ¡Ý ???? ? ? + ? ? ?, where ? is the number of adjacent flips that occur in the complete labeling of ? under ?? . LEMMA 3 (¡Ø independent diagonal triples and ? adjacent flips): Let ? be an even grid with distance-maximizing labeling ? and any other labeling ?? . If ?? contains ¡Ø independent diagonal triples and ? adjacent flips, ???? ?? ¡Ý ???? ? +¡Ø +? ? ?. In order to establish the upper bound for ?? ?? ¡õ ? ? , we must: ? Specify the labeling order for vertices ? Label ordered vertices with minimum values that satisfy the radio condition ? Compute the span of this labeling ? upper bound of ?? ?? ¡õ ? ? The span is computed by rearranging the radio condition and summing distances: ? ??+? ¡Ü ???? ? + ? ? ?(??, ??+?) + ?(??) We determine the minimal value for the last vertex labeled satisfying the radio condition¡ ¡apply this to odd grids without loss of generality: ? ?(2?+1)2 ¡Ü ???? ? + 1 ? ?(?(2?+1)2?1,?(2?+1)2) + ?(?(2?+1)2?1) ? ?(2?+1)2?1 ¡Ü ???? ? + 1 ? ?(?(2?+1)2?2,?(2?+1)2?1) + ?(?(2?+1)2?2) ? ? ?1 ¡Ý 0 ???? ? = ? ?(2?+1)2 ¡Ü ?=1 ? 2? + 1 + 2?(8? ? 1) THEOREM 1: ?? ? ??+? ¡õ ? ??+? ¡Ü ?? ? + ?? ? + ? The lower bound for ?? ?? ¡õ ? ? is established by maximizing distances. Again, rearranging the radio condition and summing across all vertex pairs gives: ?(??+1) ¡Ý (?2 ? 1)(2? ? 1) ?=1 ?2?1 ?(??+1, ??) ? Let ? denote the row index and ? the column index of a vertex. Then, ? ?=? ? ??? ? ??+?, ?? = ? ? ? ? ? + ? ? ? ? ? + ? ? ? ? ? + ? ? ? ? ? + ? ? + ? ? ??? ? ? ? ? + ? ? ??? ? ? ? ? ? If we want to maximize distances, we must label vertices such that the highest row and column indices are added in the sum, while the lowest are subtracted. The first and last vertices labeled only contribute 2 indices each to the sum and we choose arrangements of vertices that maximize the sum to minimize the span¡ THEOREM 2.1: THEOREM 2.2: ?? ? ??+? ¡õ ? ??+? ¡Ý ?? ? + ?? ? ? ? ?? ? ?? ¡õ ? ?? ¡Ý ?? ? ? ?? ? ? ?? + ? [1] Calles, Eduardo and Gomez, Henry, via personal communication and electronic files from C. Wyels [2] G. Chartrand and Erwin, David and Zhang, Ping and Harary, Frank. Radio labelings of graphs, Bull Inst. Combin. Appl., 33 (2001), pp. 77-85. [3] G. Chartrand, D. Erwin, and P. Zhang. A graph labeling problem suggested by FM channel restrictions, Bull Inst. Combin. Appl., 43 (2005), pp. 43-57. [4] Liu, Daphne Der-Fen and Zhu, Xuding. Multi-level distance labelings for paths and cycles, Siam J. Discrete Math., 19 (1993) pp. 610-621. Allow me to offer my humble gratitude to my wonderful advisor and professor DR. CYNTHIA WYELS. In addition, I would also like to thank DR. IVONA GRZEGORCZYK, as well as CSUCI MATHEMATICS for providing such a positive learning environment! RADIO LABELING SQUARE GRIDS Dev Ananda Advisor : Dr. Cynthia Wyels Master¡¯s Thesis Project Path graphs represent the best model for radio labeling square grids because grids are just constructions of paths. Below are radio labelings of path graph ?4. The first is a radio labeling ? of ?4.The second is a minimal or optimal radio labeling ?? of ?4 under which the span of the given labeling is as low as possible under the radio condition for all pairs of vertices. A grid graph is the Cartesian product of two path graphs, and square grids are composed of two identical paths. Odd grid ? ? ¡õ ? ? is depicted below as a set of vertices and edges, and subsequently, as a set of vertices in an array of boxes. The connected set of boxes represent vertices, and two vertices are considered adjacent if they share an edge. An optimal radio labeling ? ??????? of the grid is shown using the box representation with label values associated the corresponding vertex. Here we see that ?? ? ? ¡õ ? ? = ??. Label Order4 7 2 9 5 6 3 8 3x3 ordering 14 23 7 25 1 20 11 3 4 16 21 6 18 13 10 19 5 15 24 2 12 17 22 8 9 5x5 ordering k+1,1 k,1 k+1,k+1 1,2k+11,k 2k+1,2k+12k+1,1 2k+1,k 2k+1,k+1 1,1 ? The first vertex labeled is ? + ?, ? + ? ? Cyclic labeling proceeds in the order: top right, top left, bottom left, bottom right ? The distance between each pair of vertices in the same cycle = ?? + ? ? The distance between pairs of vertices in consecutive (different) cycles = ?? Substituting inequalities while incorporating the distances that our labeling order above mandates yields the following general span inequality: 1 Q1 Q3Q4 Q2 ?? ??+????? an abstract grid subdivided into quadrants ?? ¡ú ?? quadrants of ? ? ¡õ ? ? with a diagonal triple ACKNOWLEDGEMENTS ABSTRACT RADIO LABELING PATHS & GRIDS RELEVANT DEFINITIONS NEW FINDINGS, THE BUMP, & CLOSING THE GAP REFERENCES CONSTRUCTING THE UPPER BOUND CONSTRUCTING THE LOWER BOUND Considerations for advantageous ways of analyzing grids, with regards to the radio number, allows us to refine bounds and establish conditions in which upper and lower bounds meet. MOTIVATIONS: THE CHANNEL ASSIGNMENT PROBLEM Radio labeling, in graph theory, is motivated by a problem originating from the FCC's regulation of FM radio stations. The FCC categorizes radio stations into classes. Stations are then assigned channels based on certain factors, including antenna height and signal power. The distances between stations also affect what channel is assigned to a radio station of a given station class. Radio stations assigned the same must be some minimum distance apart in order to satisfy FFC regulations. Stations that are in closer proximity to one another must be channels that are farther apart, after considering station class. This is called the CHANNEL ASSIGNMENT PROBLEM. Graph theory abstracts this problem from radio transmitter and tower organizational grids, and its solution is the RADIO NUMBER.