Chvátal–Erdös Type Conditions for Hamiltonicity of Claw-Free Graphs

For a graph H, let \(\alpha (H)\) and \(\alpha ^{\prime }(H)\) denote the independence number and the matching number, respectively. Let \(k\ge 2\) and \(r>0\) be given integers. We prove that if H is a k-connected claw-free graph with \(\alpha (H)\le r\), then either H is Hamiltonian or the Ryjá c? ek’s closure \(cl(H)=L(G)\) where G can be contracted to a k-edge-connected \(K_3\)-free graph \(G_0^{\prime }\) with \(\alpha ^{\prime }(G_0^{\prime })\le r\) and \(|V(G_0^{\prime })|\le \max \{3r-5, 2r+1\}\) if \(k\ge 3\) or \(|V(G_0^{\prime })|\le \max \{4r-5, 2r+1\}\) if \(k=2\) and \(G_0^{\prime }\) does not have a dominating closed trail containing all the vertices that are obtained by contracting nontrivial subgraphs. As corollaries, we prove the following:

1. (a)
   A 2-connected claw-free graph H with \(\alpha (H)\le 3\) is either Hamiltonian or \(cl(H)=L(G)\) where G is obtained from \(K_{2,3}\) by adding at least one pendant edge on each degree 2 vertex;
    
2. (b)
   A 3-connected claw-free graph H with \(\alpha (H)\le 7\) is either Hamiltonian or \(cl(H)=L(G)\) where G is a graph with \(\alpha ^{\prime }(G)=7\) that is obtained from the Petersen graph P by adding some pendant edges or subdividing some edges of P.
    

Case (a) was first proved by Xu et al. [19]. Case (b) is an improvement of a result proved by Flandrin and Li [12]. For a given integer \(r>0\), the number of graphs of order at most \(\max \{4r-5, 2r+1\}\) is fixed. The main result implies that improvements to case (a) or (b) by increasing the value of r and by enlarging the collection of exceptional graphs can be obtained with the help of a computer. Similar results involved degree or neighborhood conditions are also discussed.

     

The Erdős–Pósa Property for Odd Cycles in Graphs of Large Connectivity

Dedicated to the memory of Paul Erdős A graph G is k-linked if G has at least 2k vertices, and, for any vertices , , ..., , , , ..., , G contains k pairwise disjoint paths such that joins for i = 1, 2, ..., k. We say that G is k-parity-linked if G is k-linked and, in addition, the paths can be chosen such that the parities of their lengths are prescribed. We prove the existence of a function g(k) such that every g(k)-connected graph is k-parity-linked if the deletion of any set of less than 4k-3 vertices leaves a nonbipartite graph. As a consequence, we obtain a result of Erdős–Pósa type for odd cycles in graphs of large connectivity. Also, every -connected graph contains a totally odd -subdivision, that is, a subdivision of in which each edge of corresponds to an odd path, if and only if the deletion of any vertex leaves a nonbipartite graph. Received May 13, 1999/Revised June 19, 2000     

The Chen–Chvátal conjecture for metric spaces induced by distance-hereditary graphs

A classical theorem of Euclidean geometry asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvátal conjectured a generalization of this result to arbitrary finite metric spaces, with a particular definition of lines in a metric space. We prove it for metric spaces induced by connected distance-hereditary graphs—a graph $G$ is called distance-hereditary if the distance between two vertices $u$ and $v$ in any connected induced subgraph $H$ of $G$ is equal to the distance between $u$ and $v$ in $G$.     

Chvátal closures for mixed integer programming problems

Chvátal introduced the idea of viewing cutting planes as a system for proving that every integral solution of a given set of linear inequalities satisfies another given linear inequality. This viewpoint has proven to be very useful in many studies of combinatorial and integer programming problems. The basic ingredient in these cutting-plane proofs is that for a polyhedronP and integral vectorw, if max(wx|x P, wx integer} =t, thenwx t is valid for all integral vectors inP. We consider the variant of this step where the requirement thatwx be integer may be replaced by the requirement that be integer for some other integral vector . The cutting-plane proofs thus obtained may be seen either as an abstraction of Gomory's mixed integer cutting-plane technique or as a proof version of a simple class of the disjunctive cutting planes studied by Balas and Jeroslow. Our main result is that for a given polyhedronP, the set of vectors that satisfy every cutting plane forP with respect to a specified subset of integer variables is again a polyhedron. This allows us to obtain a finite recursive procedure for generating the mixed integer hull of a polyhedron, analogous to the process of repeatedly taking Chvátal closures in the integer programming case. These results are illustrated with a number of examples from combinatorial optimization. Our work can be seen as a continuation of that of Nemhauser and Wolsey on mixed integer cutting planes.Supported by Sonderforschungsbereich 303 (DFG) and by NSF Grant Number ECS-8611841.Supported by NSF Grant Number ECS-8418392 and Sonderforschungsbereich 303 (DFG), Institut für Ökonometrie und Operations Research, Universität Bonn, FR Germany.     

The Chvátal closure of generalized stable sets in bidirected graphs

We consider the set of integral solutions of $Ax⩽b$, $x⩾0$, where A is the edge-vertex incidence matrix of a bidirected graph. We characterize its corner polyhedron, i.e. the convex hull of the points satisfying all the constraints except the non-negativity of the basic variables. We show that the non-trivial inequalities necessary to describe this polyhedron can be derived as fractional Gomory cuts. It follows in particular that the split closure is equal to the Chvátal closure in this case.     

A Chvátal-Erdös condition for hamilton cycles in digraphs

We obtain a sufficient condition for a digraph to be hamiltonian in terms of its connectivity and independence number.     

The Erdős–Pósa Property for Odd Cycles in Highly Connected Graphs

Dedicated to the memory of Paul Erdős In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we will show that the above statement is still valid for 576k-connected graphs which is essentially best possible. Received November 17, 1999 RID="*" ID="*" This work was supported by a post-doctoral DONET grant. RID="†" ID="†" This work was supported by an NSF-CNRS collaborative research grant. RID="‡" ID="‡" This work was performed while both authors were visiting the LIRMM, Université de Montpellier II, France.     

A hybrid inequality of Erdös–Turán–Koksma for digital sequences

For bases $\mathbf{b}=(b_1, \ldots , b_s)$ of $s$ not necessarily distinct integers $b_i\ge 2$ , we prove a version of the inequality of Erdös–Turán–Koksma for the hybrid function system composed of the Walsh functions in base $\mathbf{b}^{(1)}=(b_1, \ldots , b_{s_1})$ and, as second component, the $\mathbf{b}^{(2)}$ -adic functions, $\mathbf{b}^{(2)}=(b_{s_1+1}, \ldots , b_s)$ , with $s=s_1+s_2$ , $s_1$ and $s_2$ not both equal to 0. Further, we point out why this choice of a hybrid function system covers all possible cases of sequences that employ addition of digit vectors as their main construction principle.     

Pancyclism in Chvátal-Erdös's graphs

LetG = (X, E) be a simple graph of ordern, of stability numberα and of connectivityk withα ≤ k. The Chvátal-Erdös's theorem [3] proves thatG is hamiltonian. We have investigated under these conditions what can be said about the existence of cycles of lengthl. We have obtained several results:

1. IfG ≠ K _k,k andG ≠ C ₅,G has aC _n?1 .
2. IfG ≠ C ₅, the girth ofG is at most four.
3. Ifα = 2 and ifG ≠ C ₄ orC ₅,G is pancyclic.
4. Ifα = 3 and ifG ≠ K _3,3,G has cycles of any length between four andn.
5. IfG has noC ₃,G has aC _n?2 .

     

On the Chvátal–Gomory closure of a compact convex set

In this paper, we show that the Chvátal–Gomory closure of any compact convex set is a rational polytope. This resolves an open question of Schrijver (Ann Discret Math 9:291–296, 1980) for irrational polytopes, and generalizes the same result for the case of rational polytopes (Schrijver in Ann Discret Math 9:291–296, 1980), rational ellipsoids (Dey and Vielma in IPCO XIV, Lecture Notes in Computer Science, vol 6080. Springer, Berlin, pp 327–340, 2010) and strictly convex bodies (Dadush et al. in Math Oper Res 36:227–239, 2011).     

Further discrepancy bounds and an Erdös–Turán–Koksma inequality for hybrid sequences

We consider hybrid sequences, that is, sequences in a multidimensional unit cube that are composed from lower-dimensional sequences of two different types. We establish nontrivial deterministic discrepancy bounds for five kinds of hybrid sequences as well as a new version of the Erdös–Turán–Koksma inequality which is suitable for hybrid sequences.     

Erdős–Gyárfás conjecture for some families of Cayley graphs

The Paul Erd?s and András Gyárfás conjecture states that every graph of minimum degree at least 3 contains a simple cycle whose length is a power of two. In this paper, we prove that the conjecture holds for Cayley graphs on generalized quaternion groups, dihedral groups, semidihedral groups and groups of order \(p^3\).     

The de Bruijn–Erd?s theorem for hypergraphs

Fix integers n ≥ r ≥ 2. A clique partition of ${{[n] \choose r}}$ is a collection of proper subsets ${A_1, A_2, \ldots, A_t \subset [n]}$ such that ${\bigcup_i{A_i \choose r}}$ is a partition of ${{[n]\choose r}}$ . Let cp(n, r) denote the minimum size of a clique partition of ${{[n] \choose r}}$ . A classical theorem of de Bruijn and Erd?s states that cp(n, 2) =?n. In this paper we study cp(n, r), and show in general that for each fixed r ≥ 3, $${\rm cp}(n, r) \geq (1 + o(1))n^{r/2} \quad \quad {\rm as} \, \, n \rightarrow \infty.$$ We conjecture cp(n, r) =?(1 +?o(1))n ^r/2. This conjecture has already been verified (in a very strong sense) for r = 3 by Hartman–Mullin–Stinson. We give further evidence of this conjecture by constructing, for each r ≥ 4, a family of (1?+?o(1))n ^r/2 subsets of [n] with the following property: no two r-sets of [n] are covered more than once and all but o(n ^r ) of the r-sets of [n] are covered. We also give an absolute lower bound ${{\rm cp}(n, r) \geq {n \choose r}/{q + r - 1 \choose r}}$ when n =?q ² + q +?r ? 1, and for each r characterize the finitely many configurations achieving equality with the lower bound. Finally we note the connection of cp(n, r) to extremal graph theory, and determine some new asymptotically sharp bounds for the Zarankiewicz problem.