Topic: Labelings and Numberings of Graphs
James AbelloDIMACS, Rutgers UniversityMassive Graph MiningA variety of massive data sets exhibit an underlying structure that can be modeled as dynamic weighted
multi-digraphs. Their sizes range from tens of gigabytes to petabytes. These include the World Wide Web,
Internet Traffic and Telephone Call Detail. These data sets sheer volume brings with it a series of
computational and visualization challenges due mainly to the I/O and Screen Bottlenecks. We present external memory algorithms for connectivity and minimum spanning trees together with
heuristics for quasi-clique finding. We describe how hierarchy trees help us to cope in a unified manner
with both, the I/O and screen bottlenecks. This line of research has suggested the need to look for
"novel" graph representations in order to provide a user or a data mining engine with informed navigation
paths. We will discuss our results with graphs having on the order of 200 million vertices and several
billion edges and we will point out some mathematical problems that have surfaced along the way. The overall goal is to extract useful information that can be brought into a user's palm top and to
export these techniques to other mining domains. http://www.research.att.com/~abello and www.visdays Krystyna BalinskaTechnical University of PoznanOn Weighted Graphs Whose Vertices Are GraphsJoint work with L.V. Quintas and M.L. Gargano
Let If d is fixed then the graph
Gary BloomCity College of New York (CUNY)Equal Weight Graph Decompositions into Isomorphic ComponentsJoint work with Ruiz, Universidad Catolica de Valparaiso (deceased)We recapitulate work done in 1979 since many questions remain
unanswered. Gary BloomCity College of New York (CUNY)Applications of Numbered Graphs and How to Generate Lots of Graceful GraphsIn the first part of this talk we will review the idea of numbering
graphs. That is, we will consider some of the ways to assign values
to the edges of the graph in order to induce values on the edges that
satisfy a specified set of conditions. (Conversely, some assignment
of values to the edges can induce numberings on the nodes.) We will also review how certain of these numberings have "real-world"
applications in x-ray crystallography, designing missile guidance
codes, determining the spacing of mobile telescopes for radio
astronomy, determining optimal sonar codes, designing very efficient
rulers, etc. The second part of the talk focuses on numberings called "graceful"
and a conjecture of Ringel and Kotzig's made popular in publications
of Rosa, Golomb, and Gardner that for the past thirty years has
withstood all attempts to resolve it: "All trees are graceful." A gracefully numbered tree with e edges has values V = {0, 1, 2,
..., e-1, e} assigned to its vertices so that when its edges are
labeled with the absolute differences of their endvertices, the edge
number set = {1, 2, 3, ... , e}. For graceful graphs with no fewer
edges than vertices a subset of V labels the vertices, so that again
the edge labels = {1, 2, 3, ... , e}. We show how a set of operations on the adjacency matrix of a graceful graph yields many other graceful graphs. We show how many families of graceful graphs, including trees, can be generated. We also show that some graphs are not graceful. Ljiljana BrankovicThe University of NewcastleOn the Graceful Tree ConjectureJoint work with J. Siran, Slovak University of TechnologyIn 1967 Rosa defined beta-labeling of a finite undirected graph G with n edges to be a
one-to-one function f from the set of vertices of G to the set {0,1,2,...,n} such that the
induced edge labels are all distinct (by an induced label of an edge between vertices u and v we
mean |f(u)-(f(v)|). In 1972 Golomb called such labeling a graceful labeling and this became the
standard name for it. In addition to graceful (beta) labeling, in the same 1967 paper Rosa
introduced a few other hierarchically related labelings in order to study the connection with
decomposition of complete graphs into isomorphic subgraphs. The existence of a beta-labeling of
a given graph G with n edges is a sufficient condition for the existence of a cyclic
decomposition of a complete graph of order 2n+1 into subgraphs isomorphic to the given graph G.
In 1963 Ringel conjectured that the complete graph of order 2n+1 can be decomposed into 2n+1
subgraphs which are all isomorphic to a given tree with n edges. Kotzig conjectured that the
complete graph of order 2n+1 can be cyclically decomposed into 2n+1 subgraphs which are all
isomorphic to a given tree with n edges. What is today commonly known as Ringel-Kotzig
conjecture (also as Graceful Tree Conjecture - GTC) is a stronger claim that all trees have a
graceful labeling. Over the last 35 years limited progress has been made on GTC, despite severl
PhD theses and numerous research papers pushing the bounds on the various relaxed versions of
graceful labeling or dealing with special cases of very regualar or otherwise restricted classes
of trees. In this talk we give the state of art of advances towards this famous conjecture,
fondly called a 'disease' of graph theory. Robert C. BrighamUniversity of Central FloridaAdditive Bandwidth-A SurveyLet _{uv belongs to E}|f(u) - f(v)|. Then the well-known and much studies
bandwidth of G, denoted B(G), is given by B(G) = min{B
: _{f} (G)f
is a numbering of G}. B(G) is a measure of how close the ones in the adjacency matrix of
G can be to the main diagonal. This has implications related to the efficiency of storage of the
matrix. In 1992, Bascuñán, Ruiz, and Slater introduced the concept of additive bandwidth,
denoted B. Paralleling the definition of bandwidth, we have ^{+}(G)B = max^{+}_{f
}(G)|_{uv belongs to E}f(u) + f(v) - (n+1)| and B
= min {^{+}(G)B : ^{+}_{f} (G)f is a numbering of G}.
B is a measure of how close the ones of the adjacency matrix can be to the main
contradiagonal. This talk attempts to survey the work which has been done on additive bandwidth.^{+}(G)Linda
ErohUniversity of Wisconsin, OshkoshThe Set of Edge-Deleted Eccentricities of a GraphPreliminary report on joint work with John Koker, Hosien Moghadam, and Steve Winters
For a vertex v in a connected graph G, the edge-deleted eccentricity of v is the minimum, over all edges e in G, of the eccentricity of v in G-e. This concept has been explored in previous papers by Koker, Moghadam, Winters, Karen Klemm, Kevin McDougal, and Shubhangi Stalder. In this talk, we consider the following question. Given a set S of positive integers, does there exist a graph G so that the set of edge-deleted eccentricities of the vertices of G is precisely S? Koker, Winters, and Kevin McDougal previously showed that such a graph exists for a set of consecutive integers in which the smallest integer is at least 2 and the largest integer is at most twice the smallest. For edge-deleted eccentricies, unlike the usual eccentricities, the integers do not have to be consecutive. Provided each gap in the integers is followed by a string of consecutive integers at least as long as the gap, the string of integers is the set of edge-deleted eccentricities for some graph. We will also show individual examples in which the gap is longer than the string of consecutive integers following it. For any integer n > 2, there is a graph with edge-deleted eccentricities precisely { n, n+2 }. However, we conjecture that there is no graph with edge-deleted eccentricities precisely { k, l } where l > k+2. This is shown in the case when G has a cut-vertex whose removal results in three or more components. David ErwinTrinity CollegeInduced Labelings in GraphsJoint work with F. Harary
In this talk, a coloring of a graph G is a function on V(G) and a labeling of G is an injective coloring of G. While many colorings are not labelings, some non-injective colorings induce labelings in the sense that the structure of the coloring can be used to define an injection on V(G). Examples of such colorings arise in the study of many different `dimensional' or `locating' invariants that have been around since at least 1970 and which have applications to the problem of drug design. In this talk we discuss induced labelings, dimension, and the more general idea of symmetry breaking by destruction of the automorphism group. Michael L. GarganoPace UniversityTwo Numbers Associated with Graphs and Digraphs Whose Vertices are Labeled and Group Weighted Digraphs1) Let 2) Let 3) A digraph whose arcs are labeled with an abelian group is called
a Bert HartnellSt. Mary's UniversityA Game based on Vertex-Magic Total LabelingsJoint work with E. Boudreau, K. Schmeisser and J. Whiteley
We shall consider the following game based on the concept of vertex-magic total labelings. For a given graph G with V vertices and E edges two players alternate assigning an unused label from {1,2,...,V + E} to a vertex or edge that has not yet been assigned a label. The first time some vertex has all incident edges and itself assigned a label, the sum of those labels is called the magic constant. If the first time this occurs it involves two vertices (by labeling the edge joining them), both sums must be the same. Once the magic constant, say k, has been set, a player can assign the last label in the immediate neighbourhood of a vertex only if the sum will be k. Observe that it is legal for the sum of all labels assigned so far (to a vertex and its incident edges) to exceed k as long as at least one edge or the vertex itself is still unlabelled. The last player able to make a legal move wins. Thus, in general, the game will be over before all the vertices and edges have been labeled. A winning strategy for a restricted collection of graphs will be outlined. Johannes H. HattinghGeorgia State UniversityOn Functional Variations of Total Domination in GraphsJoint work with L. Harris
A two-valued function Robert JamisonClemson UniversityLabeling Trees by Boolean GroupsJoint work with D. ZhengIf G is an edge colored graph, a polychrome spanning tree (PST) of
G is a spanning tree all of whose edges have different colors. This
talk will address PSTs in a very special, tight edge coloring of the
complete graph. A Boolean group is a (finite) group in which every
element is its own inverse. If we take the elements of a Boolean
group as the vertices of a complete graph and color the edge from x to
y with x+y, we obtain a proper edge coloring whose color classes form
a 1-factorization. Renu LaskarClemson UniversityLocally Minimal Graph Rankings are Globally MinimalJoint work with R.E. JamisonLet G = (V,E) be a simple, undirected graph. A function f assigning to each vertex a positive integer rank is a ranking iff for any k, any path joining two vertices of rank k necessarily passes through a vertex of rank less than k. The rankings on G form a partially ordered set Rank(G) under pointwise order. This talk will investigate some properties of this partial order. Sin-Min LeeSan Jose State UniversityMy Conjectures on Edge-graceful Graphs and Edge-magic GraphsWe give here a survey of theory of edge-graceful graphs and edge-magic graphs. The progress of some of my conjectures in these fields will be reported. Sin-Min LeeSan Jose State UniversityEverything You Wanted to Know About Group-Magic Graphs(or Alice in Magic-graph Land) We give here a survey of recent works on group Daphne LiuCalifornia State University at Los AngelesDistance Labelings of GraphsDistance labelings are motivated from the channel assignment problem. For instance, the distance-two labeling provides a model for assigning channels to cities or transmitters such that two levels of interference are avoided. In this talk we introduce an extension of the distance-two labeling, namely, multiple-level distance labeling (or distance-labeling for short) which provides a model assigning channels so that all possible levels of interference are avoided. Given a graph G, a distance-labeling is a function on V(G) to positive integers such that for any two vertices u and v, the value of |f(u)-f(v)| is larger than [diam(G)-d(u, v)], where diam(G) denotes the diameter of G, and d(u, v) is the distance between u and v. The span of f is the difference between the largest and the smallest channels used in f(V). Given a graph G, the "radio number" is the minimum span of a distance-labeling for G. We study the radio numbers for paths, and for other graphs. We improve the results of Chartrand, Erwin and Zhang on the upper bounds of the radio numbers for odd paths and for graphs with even diameters. In addition, problems for further investigations are raised. James A. MacDougallThe University of NewcastleVertex-magic Labeling of Regular GraphsA vertex-magic total labeling assigns the numbers 1, ..., v+e to
the vertices and edges of a simple graph G so that the sum of all
labels at each vertex is the same constant. These labelings have been
constructed for many families of graphs, most of which are regular.
By contrast, the only families of graphs which have been shown not to
have vertex-magic labelings are rather far from being regular. The only regular graphs known not to be vertex-magic are K2 and 2K3. I conjecture that there are no others, and will discuss the evidence for this conjecture and a related conjecture. Dan McQuillanNorwich UniversityLabellings of 3-regular GraphsWe provide vertex magic labellings for all generalized peterson graphs, and other cubic graphs. We also provide a useful necessary condition for a regular graph to be totally magic, using determinants. Eric MendelsohnUniversity of TorontoSkolem Labellings of GraphsJoint work with Nabil Shalaby
A Skolem Sequence is a pair of sequences a_i and b_i such that
b_i-a_i,i=1,2,..n and every integer in [1,2n] is in one of the
sequences. A hooked Skolem sequence is similar except [1,2n] is
replaced by [1,2n-1] union{2n+1}.A folkloric reprentation of these
sequences as labelled paths leads to the idea of labelling the
vertices of a graph (V,E) so that there are exactly two vertices
labeled i and they are at distance i in the graph, with the further
condition that for any e in E (V,E\{e}) does not have the distance
property. We call this a Skolem labelling of a graph and say the graph
is Skolem labelled. If we allow one vertex to be labelled 0 we call it
a hooked Skolem labelling. Darren NarayanRochester Institute of TechnologyRepresentation of Graphs Modulo nA graph is said to have a representation modulo Nick C. PhillipsSouthern Illinios UniversityComputational aspects of the search for Totally Magic GraphsA totally magic graph has both a magic edge labelling and a magic vertex labelling. I describe some aspects of the computer search for these graphs where we tested exhaustively all graphs up to 12 vertices. Louis QuintasPace UniveristyFrom Labels to GraphsJoint work with K.T. Balinska and M.L. Gargano
Let Fred S.
RobertsDIMACS, Rutgers UniversityFull L(2,1)-colorings of Graphs and the Channel Assignment ProblemJoint work with Peter Fishburn, AT&T Labs
L(2,1)-colorings first arose as a generalization of T-colorings that were
motivated by problems of assigning frequencies to channels in communications problems and were
first investigated extensively by Jerry Griggs and Roger Yeh. The span of a graph G is the
smallest k so that there is an L(2,1)-coloring using integers between 0 and k. Motivated by
heuristic algorithms arising in channel assignment, we dicuss the problem of identifying graphs
which have a full L(2,1)-coloring, i.e., an L(2,1)-coloring of optimal span in which every color
between the smallest and largest is actually used on some vertex.Alexander RosaMcMaster UniversityThe Hierarchy of Labellings and Their Relationship with Graph Decompositions and DesignsWe revisit the old concepts of alpha-, beta-, sigma-, and rho- labellings that were inspired by Ringel's tree decomposition problem formulated at the 1963 Smolenice conference. We examine the relationship of these as well as of some more recently defined labellings with the existence of decompositions of complete graphs into isomorphic subgraphs, and with combinatorial designs that these are closely related with. Denise S. TroxellBabson CollegeOn Critical Trees Labeled with a Condition at Distance TwoSince Griggs and Yeh first introduced vertex labelings of a graph with a condition at
distance two, or L(2,1)-labelings, in 1992, several authors have been actively investigating
different aspects of this graph coloring generalization. An A connected graph G is said to be John
VillalpandoClemson UniversityL(2,1)-Colorings ParametersJoint work with R. Laskar, Clemson UniversityThe problem of assigning frequencies to radio transmitters in such a way that the
communications do not interfere is known as the channel assignment problem. Transmitters
interfere with each other if they share similar frequencies and are at a prescribed distance from
each other. An L(2,1)-coloring of a graph G is a labeling of V(G) onto the non-negative
integers such that adjacent vertices differ in color by two and vertices at distance two differ
in color. The span of a grpah is the largest k such that there exists an L(2,1)-coloring with
maximum color k. A no-hole coloring is a coloring where the labeling in onto. We introduce
irreducible L(2,1)-colorings, and define a coloring f to be an inh-coloring if it is both
irreducible and no-hole. We consider the parameters lower inh-span and upper inh-span of a
graph. We determine exact values for paths and cycles. We develop bounds for these parameters
on trees and grid graphs. Walter WallisSouthern Illinois UniversityTotally Magic GraphsGiven a graph G, a total labeling of G is a one-to-one map from set
of all vertices and edges of G to the first |V(G)|+ |E(G)| positive
integers. A total labeling is called vertex magic if there is a
constant h such that, for every vertex x of G, the sum of the labels
on x and on all edges containing it equals h, and edge magic if there
is a constant k such that, for every edge y of G, the sum of the
labels on y and its endpoints equals k. A graph is totally magic if
it has a labeling that is simultaneously vertex magic and edge magic. Xuding ZhuNational Sun Yat-sen UniversityL(2, 1) - labelings of outerplanar graphsAn The problem of determining lambda(G) . The bound is easily seen to be optimal.
< Delta +2 |

Page last updated July 15, 2002.