Norm-graphs were introduced in a paper by Kollàr, Rònyai and the speaker. They are dense graphs, which do not contain the complete bipartite graph K_{t,t!+1} for some fixed t. In this talk we discuss certain variations and generalizations of these creatures. We obtain new sharp bounds for the Turàn number of complete bipartite graphs. We also present applications of the construction in discrepancy theory and Ramsey theory. The talk represents joint work with Noga Alon and Lajos Rònyai.

Andrè Kündgen*, and Z.Füredi, University of Illinois at Urbana-Champaign
Turàn Problems for Weighted Graphs

What is the maximal number of edges in a multigraph on n vertices if every k-set spans at most r edges? We asymptotically determine the maximum possible weight of such (k,r)-dense graphs for almost all k and r as n tends to infinity, thus giving a generalization of Turàn's theorem. We find exact answers in many cases, even when negative integer weights are also allowed.

Mike Plantholt, Illinois State University
The Overfull Conjecture for Graphs with High Minimum Degree

Chetwynd & Hilton showed that any regular graph G of even order n which has relatively high degree D(G) >= .83 n can always be 1-factored. This can be viewed as saying that under this condition G has chromatic index equal to its maximum degree D(G). We extend this result by showing that any (not necessarily regular) graph G of even order n that has sufficiently high minimum degree d(G)>= .89 n and does not contain a subgraph which trivially forces the chromatic index to be more than the maximum degree, has chromatic index equal to its maximum degree. This result thus verifies the Overfull Conjecture of Chetwynd and Hilton for graphs of sufficiently high minimum degree.

 

Douglas B. West, University of Illinois at Urbana-Champaign
Coloring trees with minimum sum of colors

The chromatic sum of a graph is the smallest sum of colors on vertices among all proper colorings with natural numbers. The strength is the minimum number of colors needed to obtain a proper coloring with sum of colors on vertices achieving the chromatic sum. We construct for each integer $k$ a tree with strength $k$ that has maximum degree only $2k-2$. The result is best possible.

David Day, Wayne Goddard, Michael Henning and Henda Swart*
Multipartite Ramsey Numbers

 
For a graph G, we define r(k, c, G) as the minimum m such that, given any c-edge colouring of the complete balanced k-partite graph with m vertices in each partite set, there must exist an i such that there is a  monochromatic copy of G in colour i (if such a number exists).  We characterize graphs G for which r(k, c, G) exists and find values of the parameter for selected graphs G and small values of k and c.

Maria Axenovich, University of Illinois, at Urbana-Champaign
The Generalized Ramsey Problem

Given graphs $G$ and $H$, a coloring of $E(G)$ is called an $(H,p,q)$-coloring if the edges of every copy of $H$ in $G$ together receive at least $p$ colors and at most $q$ colors. We study the maximal and the minimal number of colors in $(H,p,q)$ coloring in case when $G$ is complete or complete bipartite graph. For example, we show that the minimum number of colors on edges of $K_{n,n}$ such that every $K_{3,3}$ has at least 8 colors is $(3/4)n^2$. We also show some bounds for arbitrary graphs $G$ and $H$. This generalizes a recent result of Erd\H{o}s and Gy\'arf\'as and earlier results of S\'os , Simonovits and Chung on classical Ramsey and Anti-Ramsey problems.

 

Tao Jiang* and Dhruv Mubayi, University of Illinois at Urbana-Champaign
Flashes and Rainbows - A Problem in Ramsey Theory

We improve the known bounds on a variation of a problem in canonical Ramsey theory. We color the edges of a clique on $n$ vertices. An *increasing path* is a path on which the vertex labels successively increase. A *flash* is an increasing path whose edges all have the same color. A *rainbow* is an increasing path whose edges all have different colors. Let $f(l,k)$ be the minimum $n$ such that every edge coloring of $K_{n+1}$ has a flash of length $l$ or a rainbow of length $k$. Lefmann, R"odl, and Thomas conjectured that $f(l,k)=l^{k-1}$. We prove a result in support of this. We obtain a general upper bound for $f(l,k)$. In particular, if $k=o(\sqrt l)$, then the upper bound implies that $f(l,k)$ is asymptotic to $l^{k-1}$ as $l$ goes to infinity.

 

Gary Chartrand, Western Michigan University
The Geodetic Number of an Oriented Graph

For two vertices $u$ and $v$ of a connected graph $G$, a $u-v$ geodesic is a shortest $u-v$ path in $G$. The geodetic number $g(G)$ is the minimum cardinality of a set $S$ of vertices such that every vertex of $G$ lies on a $u-v$ geodesic for some $u, v \in S$. This concept is extended to orientations of a connected graph. Some results and open problems are presented.

Ping Zhang, Western Michigan University
On the Planarity of Jump Graphs

For a graph $G$ of size $m \geq 1$ and edge-induced subgraphs $F$ and $H$ of size $k$ ($1 \leq k \leq m$), the subgraph $H$ is said to be obtained from $F$ by an edge jump if there exist four distinct vertices $u, v, w,$ and $x$ in $G$ such that $uv \in E(F)$, $wx \in E(G) - E(F)$, and $H = F - uv + wx$. The minimum number of edge jumps required to transform $F$ into $H$ is the $k$-jump distance from $F$ to $H$. For a graph $G$ of size $m \geq 1$ and an integer $k$ with $1 \leq k \leq m$, the $k$-jump graph $J_k(G)$ is that graph whose vertices correspond to the edge-induced subgraphs of size $k$ of $G$ and where two vertices of $J_k(G)$ are adjacent if and only if the $k$-jump distance between the corresponding subgraphs is 1. All connected graphs $G$ for which $J_2(G)$ is planar are determined.

Terry A. McKee, Wright State University
Induced Cycle Structure and Outerplanarity

Those nonseparable graphs whose induced cycles form a (minimum length) cycle basis can be characterized both by means of a natural `tree structure' and from among the series-parallel graphs by forbidding subdivisions of $K_{2,3}$ as induced subgraphs. Those nonseparable graphs that have a unique tree structure are precisely the outerplanar graphs.

 

Hong-Jian Lai* and Bolian Liu
Graph Homomorphism into an odd cycle

For integers $n k \ge 4$, a simple graph with $n$ vertices that contains no odd cycle of length at most $2k-1$ and that has minimum degree exceeding $\frac{2n-1}{2(k+1)}$ can have a homomorphism into the odd cycle of length $2k+1$. As a corollary, such a graph will contain an independent set with boundary

  

Jay Bagga, Lowell Beineke, and Badri Varma*
The Line Completion Number of a Graph: Some New Results

Super line graphs were introduced by the authors as a generalization of line graphs. In the super line graph L_r(G) of index r of a graph G, the vertices consist of r edges of G, with two being adjacent if an edge in one is adjacent (in G) to an edge in the other. The line completion number lc(G)of a graph G is the least r for which the super line graph L_r(G) is a complete graph. In one of our earlier papers we determined the line completion numbers for certain classes of graphs. In this talk we consider some other classes.

Roger B. Eggleton, Illinois State University
Subgraphs of Moser & Moser Type in Prime Distance Graphs

For any subset D of the prime numbers, the prime distance graph with distance set D is the graph Z(D) with vertex set Z, the set of all integers, and an edge between integers x and y precisely  when the distance |x-y| is a prime in D. It is known that the chromatic number of any prime distance graph Z(D) is at most 4, but it is not known exactly which subsets D of the primes require 4 colors (the "Four Color Problem for Prime Distance Graphs"). This talk looks at a family of graphs which generalize a graph used by Moser & Moser to show that the unit distance graph on the Euclidean plane has chromatic number at least 4. I will show that these generalized graphs of Moser & Moser type are minimal 4-chromatic graphs which occur in certain prime distance graphs, so they provide a structural "explanation" why those graphs are 4-chromatic.

Eddie Cheng*, Marc Lipman, and Alan Park, Oakland University
An attractive variation of graphs generated by stars: graphs generated by split-stars

In the system design of the architecture of distributed processors, an important aspect is the underlying graph structure. Such a graph is usually exponentially big, or even combinatorially big. Hence even the efficient shortest path algorithm becomes prohibitedly expensive. A standard method is to impose a certain group structure on the graph, that is, a Cayley graph so that a local structure of the graph gives rise to the global structure. In this talk, we introduce a graph generated by a split-star, which is a variant of a popular graph used in this area, namely a graph generated by a star. The major difference between these two graphs is that the graph generated by a split-star is only vertex-transitive and not edge-transitive. This is not a deficiency because it is almost edge-transitive so that they retain the attractive properties required for good interconnection networks while providing some diversification in designing system topologies. Since the regularity of these graphs is different, it provides an alternative in such system design. Routing algorithm, connectivity, diameter, average distance and vulnerability issues will be discussed.

 

Zoltan Furedi, University of Illinois at Urbana-Champaign
Lotto, footballpool and other covering radius problems

The code $C$ is called a covering code of $X$ with radius $r$ if  every element of $X$ is within Hamming distance $r$ from at
least one codeword from $C$. Given $X$ we are interested in a minimum sized $C$. Continuing a work of Hanani, Ornstein and S\'os, and Brouwer we determine the Lottery number, $L(n,k,p,2)$, the minimum number of  $k$-subsets of an $n$-set such that all the ${n \choose p}$ $p$-sets are intersected by one of them in at least $2$ elements, for all $n n_0(k,p)$. Answering a question of H\"am\"al\"ainen, Honkala, Litsyn and \"Ostergard we show further connections between Tur\'an theorem and constant weight covering codes.

 

Gary Chartrand, David Erwin*, Michael Raines and Ping Zhang, Western Michigan University
The Decomposition Dimension of Graphs

For an ordered $k$-decomposition $D = \{G_1, G_2, \cdots, G_k\}$ of a connected graph $G$ and an edge $e$ of $G$, the $D$-representation of $e$ is the $k$-tuple $r(e | D) = (d(e, G_1), d(e, G_2), \cdots, d(e, G_k))$, where $d(e, G_i)$ is the distance from $e$ to $G_i$. A decomposition $D$ is resolving if every two distinct edges have distinct representations. The minimum $k$ for which $G$ has a resolving $k$-decomposition is the decomposition dimension $\dec(G)$. It is shown that for every two positive integers $k$ and $n \geq 2$, there exists a tree $T$ of order $n$ with $\dec(T) = k$. It is also shown that $\dec(G) \leq n$ for every graph $G$ of order $n \geq 3$ and that $\dec(K_n) \leq \lfloor{(2n+5)/3}\rfloor$ for $n \geq 3$.

  

Ya-Chen Chen, University of Illinois at Urbana-Champaign
Kneser graphs are Hamiltonian for $n$ at least $3k$

The Kneser graph $K(n,k)$ is the graph whose vertices are the $k$-subsets of an $n$-set, with vertices adjacent when the corresponding sets are disjoint. The Petersen graph is $K(5,2)$ and is not Hamiltonian. It is conjectured that $K(n,k)$ is Hamiltonian for all other Kneser graphs with $n$ at least $2k+1$. Heinrich and Wallis proved this for $K(n,2)$ and $K(n,3)$. A theorem of Bor-Liang Chen and Lih implies the conjecture for $n$ exceeding $k^2/log k$. We show that $K(n,k)$ is Hamiltonian when $n$ is at least $3k$, and we extend this to the bipartite analogue of Kneser graphs. Our tools include Baranyai's partition theorem, Gray codes, and induction.