On the Aleksandrov-Fenchel inequality involving zonoids

The equality case in the general quadratic inequality V(K, L, K ₁, ..., K _n–2)² V(K, K, K ₁, ..., K _n–2) V(L, L, K ₁, ..., K _n–2) for mixed volumes is settled under the assumption that K and L are centrally symmetric and K ₁, ..., K _n–2 are zonoids. This result partly confirms a conjecture on the general case made in an earlier paper.     

Some observations on the oberwolfach problem

Some results concerning decompositions of K_n, K_n - F(where F denotes a 1-factor) and complements of a family of special cubic graphs into 2-factors of the same type are given. In particular, if 2d is a divisor of n, it is shown that K_n - F can be decomposed into 2-factors each of whose components is a cycle of length 2d.     

Conservative graphs

A graph G with q edges is defined to be conservative if the edges of G can be oriented and distinctly numbered with the integers 1, 2,…, q so that at each vertex the sum of the numbers on the inwardly directed edges equals that on the outwardly directed edges. Several classes of graphs, including K_n, for n ≥4, and K_{2n, 2m}, for n, m ≥ 2, are shown to be conservative. It is proven that the dual of a planar graceful graph is conservative, and that the converse of this result is false.     

Restricted 2-factor polytopes

The optimal k-restricted 2-factor problem consists of finding, in a complete undirected graph K _n , a minimum cost 2-factor (subgraph having degree 2 at every node) with all components having more than k nodes. The problem is a relaxation of the well-known symmetric travelling salesman problem, and is equivalent to it when ≤k≤n−1. We study the k-restricted 2-factor polytope. We present a large class of valid inequalities, called bipartition inequalities, and describe some of their properties; some of these results are new even for the travelling salesman polytope. For the case k=3, the triangle-free 2-factor polytope, we derive a necessary and sufficient condition for such inequalities to be facet inducing. Received March 4, 1997 / Revised version received September 7, 1998?Published online November 9, 1999     

On Independent Cycles in a Bipartite Graph

 Let G=(V ₁,V ₂;E) be a bipartite graph with 2k≤m=|V ₁|≤|V ₂|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs. Received: December 9, 1998 Final version received: June 2, 1999     

A Polynomial-Time Algorithm to Approximate the Mixed Volume within a Simply Exponential Factor

Let K=(K ₁,…,K _n ) be an n-tuple of convex compact subsets in the Euclidean space R ⁿ , and let V(⋅) be the Euclidean volume in R ⁿ . The Minkowski polynomial V _K is defined as V _K (λ ₁,…,λ _n )=V(λ ₁ K ₁+⋅⋅⋅+λ _n K _n ) and the mixed volume V(K ₁,…,K _n ) as

Almost resolvable Pk-decompositions of complete graphs

An almost P_k-factor of G is a P_k-factor of G - { v } for some vertex v. An almost resolvable P_k-decomposition of λK_n is a partition of the edges of λK_n into almost P_k-factors. We prove that necessary and sufficient conditions for the existence of an almost resolvable P_k-decomposition of λK_n are n ≡ 1 (mod k) and λnk/2 ≡ 0 (mod k ?1).     

Sum List Coloring Graphs

Let G=(V,E) be a graph with n vertices and e edges. The sum choice number of G is the smallest integer p such that there exist list sizes (f(v):v ∈ V) whose sum is p for which G has a proper coloring no matter which color lists of size f(v) are assigned to the vertices v. The sum choice number is bounded above by n+e. If the sum choice number of G equals n+e, then G is sum choice greedy. Complete graphs K_n are sum choice greedy as are trees. Based on a simple, but powerful, lemma we show that a graph each of whose blocks is sum choice greedy is also sum choice greedy. We also determine the sum choice number of K_2,n, and we show that every tree on n vertices can be obtained from K_n by consecutively deleting single edges where all intermediate graphs are sc-greedy.     

<Emphasis Type="Italic">k</Emphasis>-factors in regular graphs

Plesnik in 1972 proved that an （m - 1）-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular （2n ＋ 1）-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and （or） excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik＇s result and the results obtained by Liu et al. in 1998, and improve Katerinis＇ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.     

Tripartite Ramsey numbers for paths

In this article, we study the tripartite Ramsey numbers of paths. We show that in any two‐coloring of the edges of the complete tripartite graph K(n, n, n) there is a monochromatic path of length (1 ? o(1))2n. Since R(P_2n+1,P_2n+1)=3n, this means that the length of the longest monochromatic path is about the same when two‐colorings of K_3n and K(n, n, n) are considered. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 164–174, 2007     

Contractions to k8

It is proved that the maximal number of edges in a graph with n ≧ 8 vertices that is not contractible to K₈ is 6n ? 21, unless 5 divides n, and the only graphs with n = 5m vertices and more than 6n ? 21 edges that are not contractible to K₈ are the K₅(2)-cockades that have exactly 6n ? 20 edges.     

A degree condition for the existence of regular factors in K1, n-free graphs

A graph is called K_{1, n}-free if it contains no K_{1, n} as an induced subgraph. Let n(≥3), r be integers (if r is odd, r ≥ n − 1). We prove that every K_{1, n}-free connected graph G with r|V(G)| even has an r-factor if its minimum degree is at least. $ \left(n+{{n-1}\over{r}}\right) \left\lceil {n\over{2(n-1)}}r \right\rceil - {{n-1}\over{r}}\left(\left\lceil {n\over{2(n-1)}}r \right\rceil \right)^2+n-3. $ This degree condition is sharp. © 1996 John Wiley & Sons, Inc.     

A construction of a perfect set of Euler tours of K2k + I

In this article we define a perfect set of Euler tours of K_2k + I, I a 1-factor of K_2k, to be a set of Euler tours of K_2k + I that partition the 2-paths of K_2k, with the added condition that if ab ∈ I, then each Euler tour contains either the digon a b a or b a b. We prove for all k > 1 that K_2k + I has a perfect set of Euler tours, and, as a corollary, that L(K_2k) has a Hamilton decomposition. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 183–211, 1998     

Bipartite anti‐Ramsey numbers of cycles

We determine the maximum number of colors in a coloring of the edges of K_m,n such that every cycle of length 2k contains at least two edges of the same color. One of our main tools is a result on generalized path covers in balanced bipartite graphs. For positive integers q≤ a, let g(a,q) be the maximum number of edges in a spanning subgraph G of K_a,a such that the minimum number of vertex‐disjoint even paths and pairs of vertices from distinct partite sets needed to cover V(G) is q. We prove that g(a,q) = a² ? aq + max {a, 2q ? 2}. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 9–28, 2004     

Vertex Partitions of K4,4-Minor Free Graphs

 We prove that a 4-connected K _4,4-minor free graph on n vertices has at most 4n−8 edges and we use this result to show that every K _4,4-minor free graph has vertex-arboricity at most 4. This improves the case (n,m)=(7,3) of the following conjecture of Woodall: the vertex set of a graph without a K _n -minor and without a -minor can be partitioned in n−m+1 subgraphs without a K _m -minor and without a -minor. Received: January 7, 1998 Final version received: May 17, 1999     

The characterization of zero-sum (mod 2) bipartite Ramsey numbers

Let G be a bipartite graph, with k|e(G). The zero-sum bipartite Ramsey number B(G, Z_k) is the smallest integer t such that in every Z_k-coloring of the edges of K_t,t, there is a zero-sum mod k copy of G in K_t,t. In this article we give the first proof that determines B(G, Z₂) for all possible bipartite graphs G. In fact, we prove a much more general result from which B(G, Z₂) can be deduced: Let G be a (not necessarily connected) bipartite graph, which can be embedded in K_n,n, and let F be a field. A function f : E(K_n,n) → F is called G-stable if every copy of G in K_n,n has the same weight (the weight of a copy is the sum of the values of f on its edges). The set of all G-stable functions, denoted by U(G, K_n,n, F) is a linear space, which is called the K_n,n uniformity space of G over F. We determine U(G, K_n,n, F) and its dimension, for all G, n and F. Utilizing this result in the case F = Z₂, we can compute B(G, Z₂), for all bipartite graphs G. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 151–166, 1998     

On DRC‐covering of Kn by cycles

This paper considers the cycle covering of complete graphs motivated by the design of survivable WDM networks, where the requests are routed on INF‐networks which are protected independently from each other. The problem can be stated as follows: for a given graph G, find a cycle covering of the edge set of K_n, where V(K_n) = V(G), such that each cycle in the covering satisfies the disjoint routing constraint (DRC7rpar;, relatively to G, which can be stated as follows: to each edge of K_n we associate in G a path and all the paths associated to the edges of a cycle of the covering must be vertex disjoint. Here we consider the case where G = C_n, a ring of size n and we want to minimize the number of cycles in the covering. We give optimal solutions for the problem as well as for variations of the problem, namely, its directed version and the case when the cycle length is fixed to 4. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 100–112, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10040     

On the Crossing Numbers of Products of Stars and Graphs of Order Five

 There are several known exact results on the crossing numbers of Cartesian products of paths or cycles with “small” graphs. In this paper we extend these results to the Cartesian products of two specific 5-vertex graphs with the star K _{1, n} . In addition, we give the crossing number of the graph obtained by adding two edges to the graph K _{1,4, n} in such a way that these new edges join a vertex of degree n+1 of the graph K _{1,4, n} with two its vertices of the same degree. Received: December 8, 1997 Final version received: August 14, 1998     

A functional limit theorem for random graphs with applications to subgraph count statistics

We consider a random graph that evolves in time by adding new edges at random times (different edges being added at independent and identically distributed times). A functional limit theorem is proved for a class of statistics of the random graph, considered as stochastic processes. the proof is based on a martingale convergence theorem. the evolving random graph allows us to study both the random graph model K_{n, p}, by fixing attention to a fixed time, and the model K_{n, N}, by studying it at the random time it contains exactly N edges. in particular, we obtain the asymptotic distribution as n → ∞ of the number of subgraphs isomorphic to a given graph G, both for K_{n, p} (p fixed) and K_{n, N} (N/(ⁿ₂)→ p). the results are strikingly different; both models yield asymptotically normal distributions, but the variances grow as different powers of n (the variance grows slower for K_n, N; the powers of n usually differ by 1, but sometimes by 3). We also study the number of induced subgraphs of a given type and obtain similar, but more complicated, results. in some exceptional cases, the limit distribution is not normal.     

Multipartite Ramsey numbers for odd cycles

In this paper we study multipartite Ramsey numbers for odd cycles. We formulate the following conjecture: Let n≥5 be an arbitrary positive odd integer; then, in any two‐coloring of the edges of the complete 5‐partite graph K((n?1)/2, (n?1)/2, (n?1)/2, (n?1)/2, 1) there is a monochromatic C_n, a cycle of length n. This roughly says that the Ramsey number for C_n (i.e. 2n?1 ) will not change (somewhat surprisingly) if four large “holes” are allowed. Note that this would be best possible as the statement is not true if we delete from K_2n?1 the edges within a set of size (n+ 1)/2. We prove an approximate version of the above conjecture. © 2009 Wiley Periodicals, Inc. J Graph Theory 61:12‐21, 2009