Currently displaying 1 – 4 of 4

Showing per page

Order by Relevance | Title | Year of publication

Maximum Hypergraphs without Regular Subgraphs

Jaehoon KimAlexandr V. Kostochka — 2014

Discussiones Mathematicae Graph Theory

We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2n−1+r−2 edges. We conjecture that if n > r, then every n-vertex hypergraph with no r-regular subgraphs having the maximum number of edges contains a full star, that is, 2n−1 distinct edges containing a given vertex. We prove this conjecture for n ≥ 425. The condition that n > r cannot be weakened.

Chvátal's Condition cannot hold for both a graph and its complement

Alexandr V. KostochkaDouglas B. West — 2006

Discussiones Mathematicae Graph Theory

Chvátal’s Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that d i > i or d n - i n - i . We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.

Page 1

Download Results (CSV)