Line completion number - recent progress

Jay Bagga*, Lowell Beineke, Badri Varma

The line completion number
lc(G) of a graph G is the least r for which the super line graph
*L*_{r}(G) is complete. In this talk, some recent
progress on the line completion number of K_{m,n} will be
given.

Embedding extended Mendelsohn triple systems.

Vince Castellana*, Michael Raines.

An extended Mendelsohn triple is an ordered triple of the form {a,a,a}, {a,a,b}, or {a,b,c}. An extended Mendelsohn triple system (EMTS) is a pair (S,T), where S is a set of points and T is a set of extended Mendelsohn triples defined on S such that each ordered pair of (not necessarily distinct) points of S appears in exactly one extended Mendelsohn triple of T. We say that an EMTS (S,T) is embedded in an EMTS (S',T') if S Í S' and TÍ T'. In this talk, we consider necessary and sufficient conditions for embedding extended Mendelsohn triple systems.

Counting labeled general cubic graphs.

Gaby Chae

We derive recurrence relations from partial differential equations whose formal power series solutions are the exponential generating functions for labeled, general cubic graphs with given connectedness. The relations are used to compute number of these graphs with a specified number of loops and multiple edges. This work builds on the methods of Read (Some unusual enumeration problems, 1970), Wormald (Enumeration of labelled graphs II : Cubic graphs with a given connectivity, 1979) and E. M. Palmer, R. C. Read, and R. W. Robinson (Counting claw-free cubic graphs, to appear).

On the Hamiltonian index and the diameter of a graph

Zhi-Hong Chen*, Hong-Jian Lai

Let G
be a graph. The minimum integer m such that the iterated line graph
L^{m}(G) has a Hamiltonian cycle is called the Hamiltonian
index of G. The distance between two vertices u and v of a connected
graph is the minimum length of all paths joining u and v, and is
denoted by d(u,v). The diameter of G is defined by
diam(G)=max_{u,vÎ V(G)}d(u,v).
A graph G is collapsible if for every even subset XÍ V(G), G has a spanning connected subgraph
whose set of odd-degree vertices is X. Taking X=Æ , it follows that every collapsible graph
has a spanning closed trail. The reduction of G, denoted by G', is
the graph obtained from G by contracting all non-trivial collapsible
subgraphs of G.

In this paper, using the reduction method, we study the relationships between the Hamiltonian index and the diameter of a graph. This improves and extends several known results.

Antiweb-wheel inequalities and their separation problems over the stable set polytopes.

Eddie Cheng*, Sven de Vries

A stable set in a graph G is a set of pairwise nonadjacent vertices. The problem of finding a maximum weight stable set is one of the most basic NP-hard problems. An important approach to this problem is to formulate it as the problem of optimizing a linear function over the convex hull STAB(G) of incidence vectors of stable sets.

Since it is impossible (unless NP=coNP) to obtain a ``concise'' characterization of STAB(G) as the solution set of a system of linear inequalities, it is a more realistic goal to find large classes of valid inequalities with the property that the corresponding separation problem (given a point x*, find, if possible, an inequality in the class that x* violates) is efficiently solvable.

Some known large classes of separable inequalities are the trivial, edge, cycle, and wheel inequalities. In this paper, we give a polynomial time separation algorithm for the (t)-antiweb inequalities of Trotter. We then introduce an even larger class (in fact, a sequence of classes) of valid inequalities, called (t)-antiweb-wheel inequalities. This class can be seen as a common generalization of the (t)-antiweb inequalities and the wheel inequalities. We also give efficient separation algorithms for them.

Rainbow Ramsey numbers

Linda Eroh

We define the rainbow Ramsey number
RR(G_{1},G_{2}) to be the minimum integer N such that
if the complete graph on N vertices is edge-colored with any number of
colors, then the resulting graph contains either a subgraph isomorphic
to G_{1} with every edge the same color or a subgraph
isomorphic to G_{2} with every edge a different color. This
number exists if and only if G_{1} is a star or G_{2}
is a forest. We consider a variety of upper and lower bounds for
different classes of graphs and define several variations on this
number.

Strong distance in strong digraphs

David Erwin*, Gary Chartrand, Michael Raines, Ping Zhang

For two vertices u and v in a strong oriented graph D of order n >= 3, the strong distance sd(u,v) between u and v is the minimum size of a strong subdigraph of D containing u and v. For a vertex v of D, the strong eccentricity se(v) is the strong distance between v and a vertex furthest from v. The minimum strong eccentricity among the vertices of D is the strong radius srad(D) and the maximum strong eccentricity is its strong diameter sdiam(D). Some properties of the strong radius and strong diameter are presented and a sharp upper bound for the strong diameter established.

Convexity in oriented graphs

John Frederick Fink*, Gary Chartrand, Ping Zhang

For vertices u and v in an oriented graph D, the closed interval I[u, v] consists of u and v together with all vertices lying in a u-v geodesic or v-u geodesic in D. For S Í
V(D), I[S] is the union of all closed intervals I[u, v] with u, v Î
S. A set S is convex if I[S] = S. The convexity number con(D) is the
maximum cardinality of a proper convex set of V(D). The nontrivial
connected oriented graphs of order n with convexity number n-1 are
characterized. It is shown that there is no connected oriented graph
of order at least 4 with convexity number 2 and that every pair k, n
of integers with 1 <= k <= n-1 and k ¹
2 is realizable as the convexity number and order, respectively, of
some connected oriented graph. For a nontrivial connected graph G, the
lower orientable convexity number con^{-}(G) is the minimum
convexity number among all orientations of G and the upper orientable
convexity number con^{+}(G) is the maximum such convexity
number. It is shown that con^{+}(G) = n-1 for every graph G of
order n >= 2. The lower orientable convexity numbers of some
well-known graphs are determined, with special attention given to
outerplanar graphs.

A transformation of graphs

Heather Gavlas

A transformation of graphs is described where a graph
G_{1} is transformed into a graph G_{2} by means of a
given connected graph H. When H is P_{3}, this transformation
results in the transfer of a single edge from G_{1} to
G_{2}. Edge transfers, such as rotations and jumps, have been
previously studied and some relationships between these
transformations and the transformation discussed above are
presented.

Graph connectivity after path removal

Ron Gould

Let G be a graph and u,v be two distinct
vertices of G. A u-v path P is called nonseparating if G-V(P) is
connected. In this talk we study the number of nonseparating u-v paths
for two arbitrary vertices u and v of a given graph. For a positive
integer k, we show that there is a minimum integer a(k) so that if G is an a(k)-connected graph and u and v are two
arbitrary vertices in G, then there exist k vertex disjoint paths
P_{1}[u,v], P_{2}[u,v], …,
P_{k}[u,v] such that G-V(P_{i}[u,v]) is
connected for every i (i=1,2, …,k). In fact, we prove that a(k) <= 22k+2. It is known that a(1)=3. A result of Tutte showed that a(2)=3. We show that a(3)=6. In addition, we prove that if G is a
5-connected graph, then for every pair of vertices u and v there
exists a path P[u,v] such that G-V(P[u,v]) is 2-connected.

The best three (tree) and my favorite tree (three)

Peter Hamburger

A summary of selected results from Lowell Beineke's research in graph theory, in anticipation of his 60th birthday.

Forcing concepts in graph theory

Frank Harary

There have already been several forcing
ideas in graph theory. For example, within the topic of degree
sequences, it is known which sequences force the associated graph to
be either a tree, or connected, or 2-connected, among other
properties. The chromatic forcing number of a graph G was defined
independently at least twice as the smallest number of nodes which
must be colored so that, with the restriction that c (G) colors are used, every remaining node
has its color determined uniquely. The same concept has been studied
in the context of combinatorial designs where the phrase "defining
set" is used. The concept of forcing can be applied to independent
nodes and edges and to perfect matchings, with applications to
benzenoid compounds in organic chemistry (*J. Math. Chem.*
1994). Many invariants arising from the study of forcing in graph
theory offer abundant new subjects for new and applicable
research. Other forcing invariants for graphs include the smallest
number of nodes in a set S which uniquely determine the remaining
nodes in a minimum dominating set for G, the smallest number of nodes
or edges which determine connectivity or edge connectivity, and in
general any invariant involving sets. This is also meaningful for
digraphs, for example, the smallest number of edges of a graph which
can be oriented so that to obtain a strongly connected digraph, the
orientations of all the remaining edges of G are forced.

Trees in graphs with large girth

Tao Jiang

Dobson (1994) conjectured that every graph G with girth at least 2t+1 and minimum degree at least k/t contains every tree T with k edges, whose maximum degree does not exceed the minimum degree of G. The conjecture has been proven for t <= 3. In particular, a slightly stronger version of the conjecture for t=2, proven by Brandt and Dobson, implies that the famous Erdös-Sós conjecture that every graph on n vertices with more than (1/2)n(k-1) edges contains every tree with k edges, is true for graphs with girth at least 5. In this talk, we prove Dobson's conjecture.

Dense graphs that are not absorbing common subgraphs

Grzegorz Kubicki

A graph G is an
absorbing common subgraph of two graphs if G is a common subgraph of
these two graphs and, moreover, it contains (absorbs) every other
common subgraph of them. This concept was introduced and studied by
G. Chartrand, P. Erdös, and G. Kubicki in the paper "Absorbing
Common Subgraphs". One of the questions discussed there was to decide
whether a given graph G without isolated vertices is an absorbing
common subgraph of two suitably chosen larger graphs. In the case of
positive answer for this question, the graph G is called an absorbing
common subgraph. It is known that K_{n} is not an absorbing
common subgraph but complete graphs without one edge are absorbing
common subgraphs.

Here we determine the size of a densest graph
(excluding the complete graph) that is not an absorbing common
subgraph, answering the question posed in the original paper. For
every n, n >= 3, the smallest cardinality of a set of edges to be
removed from K_{n} to obtain a graph that is not an absorbing
common subgraph is n - 1.

Small cycle covers of 3-connected graphs

Xiangwen Li*, Hong-Jian Lai

Let G be a 2-connected graph of order n. Bondy conjectured that the edges of G can be covered by at most é(2n-1)/3ù cycles. In this note we shall investigate the special cases of this conjecture. We shall show that if G is a 3-connected graph of order n on the projective plane and the torus, then the edges of G can be also covered by at most é(n+1)/2ù cycles.

A generalization of the Oberwolfach problem and
C_{t}-factorization of complete equipartite graphs

Jiuqiang Liu

We consider the following
generalization of the Oberwolfach problem: "At a gathering there are n
delegations each having m people. Is it possible to arrange a seating
of mn people present at s round tables T_{1}, T_{2},
..., T_{s} (where each table can accommodate
t_{i}>2 people) for k different meals so that each person
has every other person not in the same delegation for a neighbor
exactly once?" We will concentrate on the case when all tables
accommodate the same number t of people, give a complete solution for
even t and settle most cases for odd t.

Properties of directed polygon visibility graphs

J. Michael McGrew*, Jay Bagga, John Emert

Given a simple closed polygon in the plane, its polygon visibility graph has the same vertices as those of the polygon, while the edges are those on the polygon, together with the internal chords (that is, chords which do not intersect with the exterior of the polygon). We have previously extended this notion to directed polygon visibility graphs, and studied some properties including bounds on the size of such digraphs. In this paper we consider a more general situation. We obtain bounds on the size of those directed polygon visibility graphs which can be formed from a polygon for which each edge is individually and arbitrarily oriented. These bounds are functions of the size of the polygon and the number of changes in orientation along the polygon.

Chordal maximal planar bipartite graphs

Terry McKee

Within the well-studied class of maximal planar graphs, those that are chordal graphs – meaning that every induced cycle is a triangle – form an unexpectedly natural subclass. This motivates looking at corresponding phenomena (and the role of the radial graph operator) for the class of maximal planar bipartite graphs.

The average connectivity of graphs and digraphs

Ortrud Oellermann

The average connectivity of a graph is defined as the average over all pairs of vertices of the maximum number of internally disjoint paths connecting these vertices. The average connectivity is defined similarly for digraphs. For an ordered pair (u, v) of vertices in a digraph, the connectivity from u to v is the maximum number of internally disjoint u-v paths in the digraph. The average connectivity of a digraph is the average connectivity over all ordered pairs of vertices in the digraph. We survey results on these parameters. For graphs our focus is on bounds for these parameters relative to the average degree. For digraphs we focus on the problem of orienting a graph to produce a digraph with largest average connectivity.

Hamiltonian connected line graph

Yongbin Ou

We show that if G is 3 edge-connected and every degree 3 vertex is incident with 2 multiple edges or a triangle, then the line L(G) is Hamiltonian connected.

Upper bounds of dynamic chromatic number

Hoifung Poon*, Hong-Jian Lai, Bruce Montgomery

A proper vertex k-coloring of a graph G is dynamic if for every vertex v with degree at least 2, the neighbors of v receive at least two different colors. The smallest integer k such that G has a dynamic k-coloring is the dynamic chromatic number c
_{d}(G). We prove in this paper the following best possible upper bounds as an analogue to the Brook's Theorem, together with the determination of chromatic numbers for complete k-partite graphs.

(1) If D
<= 3, then c
_{d}(G) <= 4, with the only exception that G = C_{5}, in which case

c _{d} (C_{5}) =
5.

(2) If D
>= 4, then c _{d} (G) <= D + 1.

(3) c _{d} (K_{1,1}) = 2, c _{d} (K_{1,m}) = 3 and
c _{d} (K_{m,n}) = 4
for m, n >= 2;

c
_{d} (K_{n1, n2, …, nk}) = k for k >= 3.

The spectrum of triangle-free regular graphs containing a cut vertex

Rolf S. Rees

We determine, for all n>0, the set C(n)={k: there exists a triangle-free k-regular graph on n vertices containing a cut vertex}.

Application of graph theory in software engineering

Farrokh Saba

Software engineering is a collection of processes, software tooling, and design activities for software development. Graph theory plays an important role in software engineering. Several examples of these roles will be studied and related applications will be presented.

Vertex-magic total labelings

W. D. Wallis

Suppose G is a graph with v vertices and e edges. A *total labeling* of G is a map from the vertices and edges of G onto {1, 2, …, v+e}. Such a labeling is *vertex-magic* if, for every vertex, the sum of its label with all labels of edges incident with it equals some constant. Some open problems in vertex-magic total labelings will be discussed.

Classification of minimum dominating sets of hypercubes

William D. Weakley*, Patric R. J. Östergĺrd

We complete the classification up to equivalence of all minimum dominating sets in hypercubes of dimension at most eight.

All four symmetric 3-configurations of order twelve are toroidal.

Art White

All four symmetric 3-configurations of order twelve are toroidal.

Transition restricted Gray codes: long trees, grids, and digraphs of digirth 3.

Elizabeth L. Wilmer*, Michael Ernst

The digraph of a Gray code on n bits has
vertex set {1, 2, ..., n}; the edge (i, j) is included exactly when
bit positions i and j change consecutively at some point during the
code. Generalizing the standard reflected binary Gray code by allowing
shifts yields new Gray codes whose digraphs are (undirected) trees. We
construct Gray codes where this tree has large diameter and where it
is a spanning subtree of a grid. We also construct a family of cyclic
Gray codes whose digraphs contain no directed 2-cycles. In all, we
answer three questions posed by Bultena and Ruskey (*The Electronic
Journal of Combinatorics* **3**(1996), #R11).

Distance properties of edge-deleted graphs

Steven J. Winters

The center, median and periphery have many applications in facility location problems. But the best location for a facility may change if a road is blocked due to road construction or an accident. So we consider graphs with an edge removed at random and the following definitions. For a vertex v in a 2-edge-connected graph G, the edge-deleted eccentricity of v is the maximum eccentricity of v in G-e over all edges e of G. The edge-deleted distance of v is the maximum distance of v in G-e over all edges e of G. This talk will investigate the center, median and periphery of graphs that have an edge removed at random.

Stratification and domination in graphs

Ping Zhang

A graph G is 2-stratified if its vertex set is partitioned into two classes, the red vertices and the blue vertices. Let F be a 2-stratified graph rooted at some blue vertex v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that every blue vertex v of G belongs to a copy of F rooted at v. Some examples of and results concerning F-domination are presented.

* denotes speaker

This document in .dvi or .ps or .pdf format.