A 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.

Let L be a sequence of p unlabeled connected graphs of some specified type and order n. We define the following procedure for constructing a graph B. The vertices of B correspond to elements of L and are labeled with their indices. The set of edges of B is defined as follows. Vertices i and j (1 < i < j < p) are adjacent if and only if for graphs L_i of size k and L_j of size h > k, the graph L_j can be obtained from L_i by adding d edges and there is no intermediate graph in L between these two graphs. The value of d can be used as a weight for edges in B.

If d is fixed then the graph B is bipartite for any L. If d = 1 and the elements of L are taken as f-graphs of order n (each vertex is bounded by a constant f), then B is the underlying graph of the transition graph of the Random f-Graph Process. Additionally, for d = 1 one can cosider the sequence L to consist of traceable graphs with non-traceable edges (no Hamilton path contains the letter edges) or claw-free graphs. As an example for d > 1 (and not fixed) the sequence L can consist of integral graphs.

Problem: What is the order, size, and degree distribution of the graph B? What other properties does this graph possess?

We recapitulate work done in 1979 since many questions remain unanswered.

We assign distinct values to the vertices of a graph and then calculate the graph?s edge values as the absolute difference of each edge's endvertices. A "part" of the graph is the induced subgraph consisting of all edges labeled with the same edge value. Consequently, the graph is decomposed into as many parts as there are edge labels.

We are particularly interested in graphs with isomorphic parts. A hierarchy of three types of questions arises naturally in the study of these equal weight decomposition:

1. What graphs can be decomposed into isomorphic parts if we specify before numbering which edges are to go into each part?

2. What graphs can be decomposed into isomorphic parts if we specify the structure of each part without designating which edges will be assigned to the part?

3. What graphs can be decomposed into isomorphic parts if we only specify how many edges are to belong to each part?

We will show that only linear forests can form the parts of a graph labeled in this way. We also show some of the families of graphs that lend themselves to this type of decomposition, as well as some that do not.

We also look at some n-vertex graphs that have a set of decompositions into isomorphic parts respectively having m (1), m (2), m (3), ... , m (k) edges, where m (j), j = 1, 2, ... , k are all of the factors of n. A graph whch can be decomposed into orders of all possible sizes is "equitably decomposable"?

In 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.

In 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.

Let G = (V,E) be a graph. A numbering of G is a bijection f : V -> {1,2,...,n} where n = |V|. The bandwidth of G with respect to numbering f is B_f (G) = max_{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⁺(G). Paralleling the definition of bandwidth, we have B⁺_f (G) = max_{uv belongs to E}|f(u) + f(v) - (n+1)| and B⁺(G) = min {B⁺_f (G) : f is a numbering of G}. B⁺(G) 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.

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.

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.

1) Let G be a simple connected graph whose vertices are labeled 1, 2, ..., n. A path is increasing, non-consecutive if the labels of the vertices in that path increase and no two are consecutively labeled. Let d(n) be the number of such paths. We consider d(n) for various graphs.
Joint work with M. Lewinter and J. Malerba

2) Let D be an acyclic digraph whose nodes are labeled 1, 2, ..., n and whose arcs are directed from a lower label to a higher label. A dipath is alternating, if it begins with an odd label and alternates in parity along the dipath. Let a(n) be the number of such dipaths. We consider a(n) for various graphs.
Joint work with K.T. Balinska and L.V. Quintas

3) A digraph whose arcs are labeled with an abelian group is called a group weighted digraph. Some comments pertaining to such digraphs will be mentioned.
Joint work with J.W. Kennedy and L.V. Quintas

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.

A two-valued function f defined on the vertices of a graph G=(V,E), f:V \rightarrow \{-1,1\}, is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. That is, for every v \in V, f(N(v)) \geq 1, where N(v) consists of every vertex adjacent to v. The weight of a total signed dominating function is f(V) = \sum f(v), over all vertices v \in V. The total signed domination number of a graph G, denoted \gamma^s_t(G), equals the minimum weight of a total signed dominating function of G. If, instead of the range {-1,1}, we allow the range {-1,0,1}, then we get the concept of a total minus dominating function. Its associated parameter, called the total minus domination number of a graph G, is denoted gamma^-_t(G). We show that the decision problem corresponding to the computation of the total minus domination number of a graph is NP-complete, even when restricted to bipartite graphs or chordal graphs. For a fixed k, we show that the decision problem corresponding to determining whether a graph has a total minus dominating function of weight at most k may be NP-complete, even when restricted to bipartite or chordal graphs. Linear time algorithms for computing gamma^-_t(T) and gamma^s_t(T) for an arbitrary tree T are also presented.

If 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.

Interest in the Boolean coloring arises from a clever observation in 1984 by Maamoun and Meyniel that the Boolean coloring does not contain a polychrome Hamiltonian path. Our approach to the study of PSTs in Boolean colorings is as follows. Let T = (V,E) be any tree with vertex set V and edge set E. A vertex-labeling is a map f from V into a Boolean group B. Any such map induces an edge-labeling f* given by f*[u,v] = f(u) + f(v). A vertex labeling f is admissible iff both f and f* are one-to-one. Thus admissible labelings correspond to polychrome embeddings of T into B. A vertex labeling f is perfect iff it is admissible and f is also onto. Perfect labelings correspond to realizations of T as a PST in B.

A vertex labeling f is closed iff f is admissible and every edge-label is also a vertex label. This is a slightly weaker condition than perfect which makes it possible to study whole classes of extensions of a single tree. The talk will explain this connection and discuss what is known about closed labelings.

Let 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.

We 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.

We give here a survey of recent works on group _iV magic graphs. Several research problems will be proposed.

Distance 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.

A 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.

We 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.

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.

We show when a path, cycle , and some classes of trees possess such a (hooked) Skolem labelling and also investigate the problem of when a graph is an induced subgraph of a Skolem labelled graph, and how many additional vertices and edges one must add to achieve a Skolem labelling.

A graph is said to have a representation modulo n if its vertices can be labeled with integers between 0 and n-1 inclusive such that two vertices are adjacent if and only if the difference between their labels is relatively prime to n. Erdos and Evans showed that every finite graph can be represented modulo some positive integer. The representation number of a graph G, denoted Rep(G) is the smallest n such that G has a representation modulo n. We will investigate Rep(G) for several classes of graphs and pose a number of related open problems,

A 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.

Let V be a set of vertices and L a set of labels. Define a rule for labeling the vertices and an adjacency relation for labeled vertices which depends on the labeling. From this obtain a graph (or graphs) that satisfy the given conditions.

An example: (classical type problem) Let n vertices and k colors be given. Require that a vertex be labeled with exactly one of the k colors and a vertex can only be adjacent to a vertex of a different color. Note that the labeling can be varied by requiring that the coloring of the vertices satisfies a specific distribution over the n vertices.

Problem: What is the maximum size connected graph of order n that can be colored in this way, that is, "properly" colored?

A second example: Let V be a set of |L| vertices, where L is a set of unlabeled graphs of some specified type and order. By a 1-1 correspondence, let the vertices in V be labeled by the elements of L, that is, L is thought of as a set of labeled vertices. Then define H and K in L to be adjacent if and only if K is a one-edge-transformation of H. In this case a unique graph is obtained.

Note that variations of the adjacency relation can yield a directed graph or a set of graphs.

Thus, our approach is to start with labels, which in turn specify graphs, and then consider problems that are associated with these graphs, in contrast to starting with a graph and asking how it can be labeled in a prescribed way.

L(2,1)-colorings of graphs assign integers to vertices so that colors assigned to adjacent vertices differ by at least 2 and colors assigned to vertices at distance 2 in the graph differ by at least 1. 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.

We 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.

Since 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 L(2,1)-labeling of a graph is an assignment of nonnegative integers to its vertices so that adjacent vertices get integers at least two apart and vertices at distance two get integers at least one apart. An L(2,1)-labeling that uses integers in the set {0,1,...,k} is called k-labeling. The minimum k so that a given graph G has a k-labeling is denoted by λ(G).

A connected graph G is said to be λ-critical if λ = λ(G) and λ(G-e) < λ for every edge e of G. This talk focuses on λ-critical trees. The first non-trivial case, when λ = 5 and maximum degree Δ = 3, was studied independently by Georges and Mauro, and by Fishburn and Roberts, who observed that the class of 5-critical trees with Δ = 3 is very complex. Path-like structures, called j-paths, were essential for reaching a better understanding of such class of graphs. For j > 1, two vertices in a graph are said to be j-path adjacent if there is a path of length j connecting them so that all internal vertices have degree two in the graph; such a path is called a j-path. In this talk we will consider λ-critical trees with Δ > 4, generalizing the existing results on j-paths for the case Δ = 3 and ultimately constructing an infinite family of λ-critical trees for each Δ > 4.

The 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.

Given 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.

We shall discuss the existence of totally magic graphs. The story appears to be that such graphs are extremely rare. Only two infinite families and two other (rather trivial) totally magic graphs are known.

An L(2,1)-labelings of a graph G is an assignment of nonnegative integers to the vertices of G such that adjacent vertices get integers which are at least 2 apart, and vertices of distance 2 get different integers. The L(2,1)-labeling number lambda(G) of a graph G is the smallest integer k such that there is an L(2,1)-labeling f of G with ${\rm max}\{f(x): x \in V(G)\} = k$.

The problem of determining lambda(G) arises in the context of radio frequency assignment. We prove that if G is an outerplanar graph of maximum degree Delta > 14, then lambda(G) < Delta +2. The bound is easily seen to be optimal.