NOTE: Several of the abstracts contain "standard" LaTeX commands. We hope to have this document entirely converted into HTML soon. For now, in an attempt to make things as readable as possible, it is a hodgepodge of LaTeX and HTML. If you need to report any errors in the information below, just e-mail one of the members of the organizing committee. CHECK THIS PAGE OFTEN!!! IT'S STILL EVOLVING!
The scheduled speakers are:
Let G be a simple connected graph on 2n vertices with a perfect matching. For a positive integer k, $1\leq k\leq n-1$, G is k-extendable if for every matching M of size k in G, there is a perfect matching in G containing all the edges of M. For an integer k, $0\leq k\leq n-2$, G is strongly k-extendable if $G-\{u,v\}$ is k-extendable for every pair of vertices u and v of G. The problem that arises is that of characterizing k-extendable graphs and strongly k-extendable graphs. The first of these problems has been considered by several authors whilst the latter has only been recently studied by the author. In a recent paper, we establish a number of properties of strongly k-extendable graphs including some sufficient conditions for strongly k-extendable graphs. In this paper, we focus on a necessary condition, in terms of minimum degree, for strongly k-extendable graphs. Further, we determine the set of realizable values for minimum degree of strongly k-extendable graphs. A complete characterization of strongly k-extendable graphs on 2n vertices for k=n-2 and n-3 is also established.
We discuss several recent results and problems concerning coloring problems that involve distance. These include the new concepts of the chromatic status and achromatic status of a graph as well as problems concerning extending graph colorings.
Given a positive integer k, this article investigates the problem of partitioning a graph into k vertex-disjoint paths. In particular, the following result is obtained. Let G be a graph of order n = n_1+n_2 +... + n_k (where n_i >= 2 for each i). If the minimum degree $\delta(G) \geq \lfloor\frac{n_1}2\rfloor + \lfloor\frac{n_2}2\rfloor +\dots + \lfloor \frac{n_k}2\rfloor$, then G be can be partitioned into k vertex-disjoint paths of lengths n_1, n_2, ..., n_k respectively. A minimum degree condition is also obtained such that for any 2k vertices consisting of vertex sets {x_1, x_2, \dots, x_k\} and {y_1, y_2, \dots, y_k} there are k vertex-disjoint paths P_i[x_i, y_i] (i=1, 2, ..., k) which span V(G).
For each vertex s of the subset S of vertices of a graph G, we define Boolean variables p,q,r which measure existence of three kinds of S-private neighbours (S-pns) of s. A 3-variable Boolean function f=f(p,q,r) may be considered as a compound existence property of S-pns. The set S is called an f-set of G if f=1 for all s in S and the class of all f-sets of G is denoted by W(f). Special cases of W(f) include the independent sets, irredundant sets, open irredundant sets and CO-irredundant sets of G.
There are 62 non-trivial families W(f) which include the seven of a framework proposed earlier by Fellows, Fricke, Hedetniemi and Jacobs.
The functions f for which W(f) is hereditary for any graph G, are determined, existence and properties of f-Ramsey numbers (analogs of the elusive classical Ramsey numbers) are investigated and future directions for the theory of the classes W(f) are considered.
Several countably infinite sequences of integer parameter values are identified for which it is established that the corresponding potential generalized Hadamard matrices do not exist. A typical case is the sequence GH(3,3.5.(2k+1)) over group G={0,1,2}, (+), where k is an integer for which 2k+1 is not a multiple of 5. Methods for establishing nonexistence of nontrivial solutions to homogenuous, quadratic Diophantine equations are examined.
A question of Erdos asks if every graph with minimum degree 3 must contain a pair of cycles whose lengths differ by 1 or 2. This conjecture has recently been proved by Haggkvist and Scott. Indeed they have also proved that minimum degree 500k^2 guarantees the existence of cycles whose lengths are of the form m, m+2, m+4, ..., m+2k for some m. In like vein, we prove that provided G is cubic, hamiltonian of order n then G must contain cycles whose lengths form an arithmetic progression of length O(log n). Using this we give a partial answer to a question of Erdos.
Let G be a graph with n vertices. We show that $\omega(G) \leq n - \delta(G)$, where $\delta(G)$ denotes the minimum degree of G and $\omega(G)$ denotes either the weak domination number of G or the independent weak domination number of G. We also show that $\sigma(G) \leq n - \Delta(G)$, where $\Delta(G)$ denotes the maximum degree of G and $\sigma(G)$ denotes the strong domination number of G or the independent strong domination number of G. In each case we give necessary and sufficient conditions for equality to hold and describe specific classes of graphs for which this is true.
In investigating P. Frankl's well known problem about union closed set systems, we have discovered some surprising connections between set systems and Hamilton cycles in directed circulant graphs. In addition, a related inequality for sizes of ideals and filters in distributive lattices has been obtained.
This is joint work with B. Sands (The University of Calgary)
Let $\tau(G)$ denote the number of vertices in a longest path of the graph G and let k_1 and k_2 be positive integers such that $\tau(G) = k_1 + k_2$. We denote by G[V_1] the subgraph induced by V_1 in G.
The Path Partition Conjecture is: For an arbitrary graph G, with $\tau(G) = k_1 + k_2$, V(G) can be partitioned into two subsets, V_1 and V_2 such that $\tau(G[V_1] ) \leq k_1$ and $\tau(G[ V_2] ) \leq k_2$. We show that several classes of graphs support this conjecture.
It is obvious that a vertex set V has many triangulations. In this talk, we will discuss an algorithm to find optimal triangulations for the purpose of spline approximation. We define a so-called type-O triangulation and introduce an Edge Swapping Algorithm to change an arbitrary triangulation into a type-O triangulation. We will also demonstrate a MatLab package to implement this algorithm.
The concept of a strong $\alpha$-valuation was introduced by Maheo, who showed that if a graph G has a strong $\alpha$-valuation, then so does $G \times K_2$. We show that for various graphs G, G x Q_n has a strong $\alpha$-valuation and G x P_n has an $\alpha$-valuation, where Q_n is the n-cube and P_n the path with n edges, including G=K_{m,2} for any m. Yet we show that K_{m,n} x K_2 does not have a strong $\alpha$-valuation if m and n are distinct odd integers.
We consider the following general question: If a condition is sufficient to imply hamiltonicity, is it also enough to imply the existence of a 2-factor consisting of k cycles (for some integer $k \geq 1$)? We provide some answers to this question for conditions involving neighborhood unions and conditions involving claw-free graphs. For example, we can show that if a graph G on n vertices is 2-connected, claw-free, and has minimum degree at least (n-2)/3, then G contains a 2-factor with k vertices for any integer k, $1 \leq k \leq (n-30)/3.$
Paul Erdos conjectured that for any odd integer $n \geq 5$, $r(C_n,C_n,C_n) = 4n-3$. It has been shown by Tomasz Luczak that $r(C_n,C_n,C_n) = (4 + o(1))n$. Using Turan type extremal theory the conjecture will be verified for the first case when n=5; (i.e. $r(C_5,C_5,C_5) = 17$).
Finding a legal coloring of the vertices of a graph using the minimum number of colors is one of the most computationally difficult problems in graph theory. In this talk we explore the effectiveness of using genetic algorithms to attack this problem. After examining the effectiveness of pure genetic algorithms for graph coloring using both order based and coloring based encodings, we also hybridize the genetic algorithm with other heuristic techniques that have shown to be effective in attacking this problem. These include Tabu search, Monte Carlo methods and iterated greedy coloring. We will compare our results using these mixed heuristics on random and Leighton graphs to results obtained by others using different techniques.
Ng and Schultz introduced the idea of cycle orderability. For a positive integer k, a graph G is k-ordered if for every ordered sequence of k vertices, there is a cycle that encounters the vertices of the sequence in the given order. If the cycle is also hamiltonian, we say the graph is k-ordered hamiltonian. We give minimum degree, degree sum, and neighborhood union conditions that imply a graph is k-ordered hamiltonian. Sharpness examples will also be shown.
We prove that if T is a tournament on $n\ge 7$ vertices and x,y are distinct vertices of T with the property that T remains 2-connected if we delete the arc between x and y, then there exist disjoint 3-cycles C_x, C_y such that $x\in V(C_x)$ and $y\in V(C_y)$. Using this result, we prove that under the same connectivity assumption and if $n\ge 8$, then T also contains complementary cycles $C'_x, C'_y$ (i.e. $V(C'_x)\cup V(C'_y)=V(T)$ and $V(C'_x)\cap V(C'_y)=\emptyset$). This is best possible in terms of the connectivity assumption. It is a trivial consequence of our result that one can decide in polynomial time whether a given tournament T with special vertices x,y contains disjoint cycles $C_x,C_y$ such that $x\in V(C_x)$ and $y\in V(C_y)$. This problem is NP-complete for general digraphs and furthermore there is no degree of strong connectivity which suffices to guarantee such cycles in a general digraph.
Asymptotic approximations for the number of self-avoiding walks on infinite grid graphs are determined by the construction and analysis of an associated family of finite automata.
Let G=(V,E) be a graph. A set $S \subseteq V$ is a weak dominating set of G if for every u in V-S, there exists a $v \in S$ such that $uv \in E$ and $\deg u \geq \deg v$. The weak domination number of G, denoted by $\gamma_w(G)$, is the minimum cardinality of a weak dominating set of G. We show that if $T \neq K_2$ is a tree of order n, then $\gamma_w(T) \ge \lceil (n+2) / 3 \rceil$. We constructively characterize the extremal trees T of order n achieving this lower bound. Furthermore, we show that if G is a connected graph of order $n \geq 3$ which is not a star, then $\gamma_w(G) \leq n-2$ and characterize those connected graphs of order n achieving n-2.
In this talk, we present recent bounds on domination parameters. A characterization of graphs with minimum degree 2 and domination number exceeding a third their size is obtained. Upper bounds on the total domination number, $\gamma_t(G)$, of a graph G in terms of their order and size are established. We show that if G is a connected graph of order n with minimum degree at least 2, then either $\gamma_t(G) \le 4n/7$ or $G \in \{C_3, C_5, C_6, C_{10}\}$. A characterization of those graphs of order n which are edge-minimal with respect to satisfying G connected, $\delta(G) \ge 2$ and $\gamma_t(G) \ge 4n/7$ is obtained. We establish that if G is a connected graph of size q with minimum degree at least 2, then $\gamma_t(G) \le (q+2)/2$. Connected graphs G of size q with minimum degree at least 2 satisfying $\gamma_t(G) > q/2$ are characterized. Upper bounds on other domination parameters, including the strong domination number, the restrained domination number, and the strict majority number are presented. We provide a constructive characterization of those trees with equal domination and restrained domination numbers. A constructive characterization of those trees with equal domination and weak domination numbers is also obtained.
The trade spectum of a simple graph G is the set of all integers t for which there is a simple graph H, and two partitions of the edges of H into copies of G which have no copies of G in common. Trade spectra arise both in intersection problems for G-designs, and defining sets for G-designs. We determine here the trade spectra of complete partite graphs, with but a handful of exceptions.
Median graphs can be characterized as retracts of hypercubes. Considerable attention has been devoted to finding good recognition algorithms for them. Based on results about the structure of median graphs obtained jointly with S. Klavzar and a modification of an algorithm of Noga Alon for recognizing triangle-free graphs a new algorithm for the recognition of median graphs is derived. It has complexity O(m^1.41), where m is the number of edges in the graph to be investigated and improves the complexity of previous algorithms.
Some recent developments regarding the relations among the fractional chromatic, choice (aka list-chromatic), Hall, and Hall-condition numbers are exposed.
A pair of nonadjacent vertices of a graph is called an even pair if every chordless path connecting the vertices has an even number of edges. Recently there has been much interest in even pairs because of their use in designing combinatorial, polynomial-time coloring algorithms for certain families of perfect graphs. A graph is minimally even pair free if it is not a clique, contains no even pair, but every proper induced subgraph that is not a clique contains an even pair. Hougardy conjectured that a minimally even pair free graph is either an odd cycle of length at least five, the complement of a cycle (even or odd) of length at least five, or the linegraph of a bipartite graph. A diamond is a graph obtained from a complete graph on four vertices by removing an edge. Adapting the characterization of diamond-free perfect graphs given by Fonlupt and Zemirline, we verify Hougardy's conjecture for diamond-free graphs.
A quasi-progression of diameter n is a sequence $\{x_{1},\ldots, x_{k}\}$ for which there exists a positive integer L such that $L \leq x_{i}-x_{i-1} \leq L+n$ for $i=2,\ldots,k$. Define an h_m-progression to be a sequence $\{x_{1},\ldots,x_{k}\}$ such that for some $d \in Z^{+}$, $x_{i+1}-x_{i} \in \{d,2d,\ldots,md\}$ for $i=2,\ldots,k$. Let Q_n(k) and h_m(k) represent the associated van der Waerden-like numbers for k-term quasi-progessions of diameter n and for k-term h_m-progressions, respectively. Upper and lower bounds for Q_n(k) and h_m(k) are found for certain cases.
A k-ranking, f$for a graph G=3D(V,E) is a function from V(G) to a set of positive integers {1,2,..., k} such that if u, v in V(G) and f(u)=3Df(v), then every u-v path contains a vertex w such that f(w)>f(u). A ranking is a proper coloring. We study properties of rank and arank number of G , which are respectively ,the minimum and maximum k over all minimal rankings of G=20.
Given any uncapacitated transportation problem on a (not necessarily complete) bipartite graph, there always exists an ordering of the edges such that a feasible solution to the problem (if one exists) results from greedily assigning the maximum possible flow through each edge of the sequence in turn. Of course this fact is generally useless in practice, and the sequence usually depends upon the particular values of the supplies and demands. However, it is well-known that there is a class of graphs for which such edge sequences exist that depend on the structure of the graph alone---the same sequence can be used for any feasible set of supply and demand values. These are the chordal bipartite graphs, and the desired edge-orderings are the Monge sequences. We discuss how to extend these results to capacitated transportation problems on bipartite graphs and in particular describe the appropriate analogue to Monge sequences.
Chordal graphs are graphs with no induced cycles of length greater than three. Strongly chordal graphs have the further property that every cycle of even length greater than four has a chord that divides the cycle into two odd-length paths. These graphs form a nice family of graphs that has received considerably more attention than one would expect from that definition. I shall survey the existing characterizations of strongly chordal graphs and then present a couple of new characterizations that may be more natural strengthenings of chordal graphs.
This talk will be a rather informal discussion of a characterization of those trees that have equal domination and independent domination numbers. The characterization involves the sets of vertices of a tree which are respectively contained in all its minimum dominating and all its minimum independent dominating sets.
We present some recent results on combinatorial properties of nonlinear binary perfect single error-correcting codes and discuss some open questions and connections to perfect dominatng sets in the hypercube.
For a graph G, with domination number $\gamma(G) = j$, we say G is (j,t)-critical if the removal of any t vertices from a packing reduces the domination number by exactly t. We show that no tree is (j,t)-critical. However, given any integers j and t, where $t \leq j$, we show there exists a (j,t)-critical graph. In addition, we determine properties of (j,t)-critical graphs and give bounds on the diameter.
Let G be a graph with at least 2(m+n+1) vertices. Then G is E(m,n) if for each pair of disjoint matchings $M,N\subseteq E(G)$ of size m and n respectively, there exists a perfect matching F in G such that $M\subseteq F$ and $F\cap N=\emptyset$. In the present paper we wish to study property E(m,n) for the various values of integers m and n when the graphs in question are restricted to be planar. It has been known for ten years that no planar graph is E(3,0). This result is sharpened in the present paper by showing that no planar graph is E(2,1). This result severely limits the values of m and n for which a planar graph can have property E(m,n). The property E(2,0) has been rather extensively studied for planar graphs by various authors. There exists a lattice of implications of the form $E(m,n)\longrightarrow E(k,l)$ due to Aldred and Porteous. In this paper we study the various properties E(1,n) and E(0,n) for graphs in the plane in conjunction with that portion of the implication lattice applicable to these cases. General planar graphs are considered, as are various special planar families such as the cubic graphs, bipartite graphs, triangulations and quadrangulations for various possible vertex connectivities. Sharpness of these results is also explored.
Combinatorial proofs can lead to a great appreciation and
understanding for any topic. Fibonacci and Lucas identities are no
exception. Many mathematicians are familiar with the representation of
Fibonacci numbers as the number of tilings of a 1xn board by squares
(1x1 pieces) and dominoes (1x2 pieces). Lucas numbers can be represented
similarly as the number of tilings of a circular 1xn board by
(appropriately curved) squares and dominoes. Relying on these
representations and sometimes adding a splash of color, it is possible to
get fun proofs for many identities involving Fibonacci and Lucas numbers,
including my favorites
$$ F_{n} = 2^{n-1}\left(
\binom{n}{1}
+ 5
\binom{n}{3}
+ 5^2
\binom{n}{5}
+ \cdots + 5^{k}
\binom{n}{2k+1}
+ \cdots \right )$$
$$L_n = 2^{n-1}\left(
\binom{n}{0}
+ 5
\binom{n}{2}
+ 5^2
\binom{n}{4}
+ \cdots + 5^{k}
\binom{n}{2k}
+ \cdots \right). $$
With the help of computer algorithms we prove that 15 is the exact value of the (edge) Folkman number F_e(3,3;5), which is defined as the smallest positive integer n, such that there exists a K_5-free graph on n vertices, whose every coloring of the edges with two colors contains a monochromatic triangle. We construct all critical graphs on 15 vertices for this number and present some of their properties. Similarly, we obtain F_v(3,3;4)=14 and all K_4-free critical graphs for the (vertex) Folkman number, where instead of the edges we color the vertices. The exact values of both numbers were previously unknown, and both were the smallest open cases of a general problem of computing edge- and vertex- Folkman numbers F(k,l;m), respectively.
All computations were performed at least twice with independent implementations of algorithms written by different authors.
A dominating set A in a graph G is called an acyclic dominating set of G if $\langle A \rangle$, the subgraph induced by A, is acyclic (that is, $\langle A \rangle$ contains no cycles). We define a lower and upper acyclic domination number and a lower and upper acyclic irredundance number and investigate relationships between these four parameters and the six domination-type parameters in the standard "domination inequality chain." In addition we will report on the complexity of computing these new parameters.
Among the most important problems in the social sciences is the problem of group decisionmaking. Among the most useful group decisionmaking procedures are the median procedure, which chooses all those alternatives that minimize the sum of the distances to a given set of alternatives, and the mean procedure, which chooses all those alternatives that minimize the sum of the squares of the distances. This talk will explore problems in graph theory and combinatorics related to the median and mean.
In oriented matroid theory, the class of binary matroids and their orientations is completely understood. For example, we know that for an oriented matroid, the underlying matroid is binary if and only if the oriented matroid can be represented by a totally-unimodular matrix. Also, all orientations of a binary matroid are equivalent.
In this talk we will present analagous results for the class of ternary
matroids and their orientations. In particular,
Theorem 1
Let M be an oriented matroid.
Let $\underline{M}$ be the matroid underlying M.
Then $\underline{M}$ is ternary if and only if
M can be represented by a rational matrix
with the property that all of its
nonzero subdeterminants are in
$D:=\{\pm 2^k\ :\ k \in {\bf Z}\}$.
Theorem 2 If M is a 3-connected,
ternary matroid, then M has 0, 1 or 3 inequivalent orientations.
A given sequence ${\cal D}=(d_1,d_2,\cdots,d_n)$ is said to contain a repetition subsequence ${\cal {D^*}}=(d_{i_1},d_{i_2},\cdots,d_{i_k})$ for some $k\leq n-2$ if all values of $\cal {D-D^*}$ are distinct and for any $d_{i_j}\in \cal {D^*}$ there exists some $d_t\in \cal {D-D^*}$ such that d_{i_j}=d_t. For any pair of integers n and k with $n\geq k+2$, we investigate the existence of a graphic sequence which contains a given repetition subsequence. The main theorem contains the known results for the special cases when $d_{i_1}=d_{i_k}$ for k=1 and for k=2.
The problem of covering all pairs from a v-set by a family of subsets, when the cardinality of the family is minimal, has long be solved. Indeed, the much more important problem of finding the minimal family when the size of the largest˙subset˙ in the covering family is known, is basically completely solved.
On the other hand, almost nothing is known about the corresponding problem when each pair is to be covered not once but twice. In this talk I will indicate some approaches that hold promise for providing partial answers.
Many graph theoretic subset problems, such as, fractional domination, fractional independence, and fractional packing, can be formulated as Linear Programming (LP) problems, where the constraint matrix for the LP-problem is the closed neighborhood, adjacency, incidence,or total matrix. The Automorphism Class Theorem states that there exists an optimum LP-solution which is constant on automorphism classes. We investigate the properties of the constraint matrix which allow for this constant solution. The property which results is referred to as a matrix partition. We show that the matrix partition is a generalization of the ACT.
Klostermeyer [1] has defined a
dynamically orientable graph (dog) to be a
graph G=(V,E) in which
each edge of the graph may be neutral or
directed in either direction. Initially all edges
are neutral.When a neutral edge between u and v is traversed from u
to v
the
state of the edge changes from neutral to
For
conventional undirected graphs, Farley [2] showed that B_m(G), the time
to broadcast
m messages in graph
G, is bounded by
\[2(m-1) + D \leq B_m(G) \leq d_{max}(m-1)
+ (n-1)\]
where D is the diameter of G and d_{max} is the maximum
degree of
a point in G.
For many dogs, however, B_m(G) is asymptotically
twice as large as for the same graph without
dynamic orientation.
This increase in
broadcast time can be compensated for in some classes of graphs by using
multiple rather
than single sources of messages. We describe our current work in
mutliple message
broadcasting in dynamically oriented paths, with single and multiple
sources.
This work is supported by the National
Science Foundation and West Virginia EPSCoR programs.
We address the problem of classification of one-factorizations of complete graphs. Several tools have been suggested; which are most efficient, computationally?
In particular, many one-factorizations of K_2n are constructed by combining two one-factorizations (or near-one-factorizations) of K_n with a one-factorization of K_{n,n}. But how many?
The astute reader will guess that this is a preliminary report which raises more questions than it solves.
We say that a graph is {G_1,G_2}-free if it does not contain an induced copy of G_1 or G_2. A family $\Gamma$ of graphs is said to be determined by the forbidden pair of subgraphs {G_1,G_2} if it consists of all {G_1,G_2}-free graphs. Let $\chi(G)$ be the chromatic number of G and $\omega(G)$ be the clique number of G. A family $\Gamma$ of graphs is said to be $\chi$-bound with binding function f if $\chi(G')\leq f(\omega(G'))$ holds whenever G' is an induced subgraph for $G\in\Gamma$.
In this talk, we consider results and open problems concerning the $\chi$-bounds on families of graphs determined by pairs of forbidden subgraphs. In this case, it is sufficient to say that $\chi(G)\leq f(\omega(G))$ for every $G\in\Gamma$.
In this talk, we will talk about reconstructing graphs embedded in surfaces and prove that if a connected graph G embedded in a surface S of characteristic c satisfies (1) the minimum degree of G>4, (2) |V(G)|>-42c, then G is edge reconstructible.
Return to the Cumberland Conferences' home page