Abstracts for MIGHTY XXXII

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₁,G₂) 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₁ with every edge the same color or a subgraph isomorphic to G₂ with every edge a different color. This number exists if and only if G₁ is a star or G₂ 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₁ is transformed into a graph G₂ by means of a given connected graph H. When H is P₃, this transformation results in the transfer of a single edge from G₁ to G₂. 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₁[u,v], P₂[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

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₁, T₂, ..., 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₅, in which case

(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;

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.

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