Search

A graph G is k-edge-Hamiltonian if any collection of vertex-disjoint paths with at most k edges altogether belong to a Hamiltonian cycle in G. A graph G is k-Hamiltonian if for all S ⊆ V (G) with | S | ≤ k , the subgraph induced by V (G) ∖ S has a Hamiltonian cycle. These two concepts are classical extensions of the usual Hamiltonian graphs. In this paper, we present some spectral sufficient conditions for a graph to be k-edge-Hamiltonian and k-Hamiltonian in terms of the adjacency spectral radius as well as the signless Laplacian spectral radius. Our results could be viewed as slight extensions of the recent theorems proved by Li and Ning [Linear Multilinear Algebra. 2016;64:2252–2269], Nikiforov [Czechoslovak Math J. 2016;66:925–940] and Li et al. [Linear Multilinear Algebra. 2018;66:2011–2023]. Moreover, we shall prove a stability result for graphs being k-Hamiltonian, which could be regarded as a complement of two recent results of Füredi et al. [Discrete Math. 2017;340:2688–2690] and [Discrete Math. 2019;342:1919–1923]. [ABSTRACT FROM AUTHOR]

In 1965, Motzkin–Straus established the connection between the maximum cliques and the Lagrangian of a graph, the maximum value of a quadratic function determined by a graph in the standard simplex. This connection gave a proof of the Turán’s classical result on Turán densities of complete graphs. In 1980’s, Sidorenko and Frankl–Füredi further developed this method for hypergraph Turán problems. However, the connection between the Lagrangian and the maximum cliques of a graph cannot be extended to hypergraphs. In 2009, S. Rota Bulò and M. Pelillo defined a homogeneous polynomial function of degree r determined by an r -uniform hypergraph and gave the connection between the minimum value of this polynomial function and the maximum cliques of an r -uniform hypergraph. In this paper, we provide a connection between the local (global) minimizers of non-homogeneous polynomial functions to the maximal (maximum) cliques of hypergraphs whose edges containing r − 1 and r vertices. This connection can be applied to obtain an upper bound on the Turán densities of complete { r − 1 , r } -type hypergraphs. [ABSTRACT FROM AUTHOR]

Motzkin and Straus established a remarkable connection between the maximum clique and the Graph-Lagrangian of a graph in (Can. J. Math. 17:533-540, ). This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we provide upper bounds on the Graph-Lagrangian of a hypergraph containing dense subgraphs when the number of edges of the hypergraph is in certain ranges. These results support a pair of conjectures introduced by Peng and Zhao (Graphs Comb. 29:681-694, ) and extend a result of Talbot (Comb. Probab. Comput. 11:199-216, ). [ABSTRACT FROM AUTHOR]

The Graph-Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. In most applications, we need an upper bound for the Graph-Lagrangian of a hypergraph. Frankl and Füredi conjectured that the $${r}$$ -graph with $$m$$ edges formed by taking the first $$\textit{m}$$ sets in the colex ordering of the collection of all subsets of $${\mathbb N}$$ of size $${r}$$ has the largest Graph-Lagrangian of all $$r$$ -graphs with $$m$$ edges. In this paper, we show that the largest Graph-Lagrangian of a class of left-compressed $$3$$ -graphs with $$m$$ edges is at most the Graph-Lagrangian of the $$\mathrm 3 $$ -graph with $$m$$ edges formed by taking the first $$m$$ sets in the colex ordering of the collection of all subsets of $${\mathbb N}$$ of size $${3}$$ . [ABSTRACT FROM AUTHOR]

The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. In most applications, we need an upper bound for the Lagrangian of a hypergraph. Frankl and Füredi conjectured that the -graph with edges formed by taking the first sets in the colex ordering of has the largest Lagrangian of all -graphs with edges. Talbot in Talbot (2002) provided some evidences for Frankl and Füredi’s conjecture. In this paper, we prove that the -graph with edges formed by taking the first sets in the colex ordering of has the largest Lagrangian of all -uniform graphs on vertices with edges when where under some conditions. As an implication, we also derive that Frankl and Füredi’s conjecture holds for 3-uniform graphs with edges where . [ABSTRACT FROM AUTHOR]

A number $${\alpha\in [0, 1)}$$ is a jump for an integer r ≥ 2 if there exists a constant c > 0 such that for any family $${{\mathcal F}}$$ of r-uniform graphs, if the Turán density of $${{\mathcal F}}$$ is greater than α, then the Turán density of $${{\mathcal F}}$$ is at least α + c. A fundamental result in extremal graph theory due to Erdős and Stone implies that every number in [0, 1) is a jump for r = 2. Erdős also showed that every number in [0, r!/ r r) is a jump for r ≥ 3. However, not every number in [0, 1) is a jump for r ≥ 3. In fact, Frankl and Rödl showed the existence of non-jumps for r ≥ 3. By a similar approach, more non-jumps were found for some r ≥ 3 recently. But there are still a lot of unknowns regarding jumps for hypergraphs. In this note, we show that if $${c\cdot{\frac{r!}{r^r}}}$$ is a non-jump for r ≥ 3, then for every p ≥ r, $${c\cdot{\frac{p!}{p^p}}}$$ is a non-jump for p. [ABSTRACT FROM AUTHOR]

Abstract: Estimating Turán densities of hypergraphs is believed to be one of the most challenging problems in extremal set theory. The concept of ‘jump’ concerns the distribution of Turán densities. A number is a jump for -uniform graphs if there exists a constant such that for any family of -uniform graphs, if the Turán density of is greater than , then the Turán density of is at least . A fundamental result in extremal graph theory due to Erdős and Stone implies that every number in is a jump for graphs. Erdős also showed that every number in is a jump for -uniform hypergraphs. Furthermore, Frankl and Rödl showed the existence of non-jumps for hypergraphs. Recently, more non-jumps were found in for -uniform hypergraphs. But there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we propose a new but related concept–strong-jump and describe several sequences of non-strong-jumps. It might help us to understand the distribution of Turán densities for hypergraphs better by finding more non-strong-jumps. [Copyright &y& Elsevier]

Abstract: Let be an integer. A real number is a jump for r if there is a constant such that for any and any integer m where , there exists an integer such that any r-uniform graph with vertices and density contains a subgraph with m vertices and density . It follows from a fundamental theorem of Erdős and Stone that every is a jump for . Erdős asked whether the same is true for . Frankl and Rödl gave a negative answer by showing some non-jumping numbers for every . In this paper, we provide a recursive formula to generate more non-jumping numbers for every based on the current known non-jumping numbers. [Copyright &y& Elsevier]

Abstract: Let be an integer. The real number is a jump for r if there exists such that for every positive ϵ and every integer , every r-uniform graph with vertices and at least edges contains a subgraph with m vertices and at least edges. A result of Erdős, Stone and Simonovits implies that every is a jump for . For , Erdős asked whether the same is true and showed that every is a jump. Frankl and Rödl gave a negative answer by showing that is not a jump for r if and . Another well-known question of Erdős is whether is a jump for and what is the smallest non-jumping number. In this paper we prove that is not a jump for . We also describe an infinite sequence of non-jumping numbers for . [Copyright &y& Elsevier]