BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We propose new bounds on the domination number and on the independence number of a graph and show that our bounds compare favorably to recent ones. Our bounds are obtained by using the Bhatia-Davis inequality linking the variance, the expected value, the minimum, and the maximum of a random variable with bounded distribution.
In the early 1980s, Erdős and Sós initiated the study of the classical Turán problem with a uniformity condition: the uniform Turán density of a hypergraph H is the infimum over all d for which any sufficiently large hypergraph with the property that all its linear-size subhyperghraphs have density at least d contains H. In particular, they raise the questions of determining the uniform Turán densities of K4(3)− and K4(3). The former question was solved only recently in [Israel J. Math. 211 (2016), 349-366] and [J. Eur. Math. Soc. 20 (2018), 1139-1159], while the latter still remains open for almost 40 years. In addition to K4(3)−, the only 3-uniform hypergraphs whose uniform Turán density is known are those with zero uniform Turán density classified by Reiher, Rödl and Schacht [J. London Math. Soc. 97 (2018), 77-97] and a specific family with uniform Turán density equal to 1/27. We develop new tools for embedding hypergraphs in host hypergraphs with positive uniform density and apply them to completely determine the uniform Turán density of a fundamental family of 3-uniform hypergraphs, namely tight cycles Cℓ(3). The uniform Turán density of Cℓ(3), ℓ≥5, is equal to 4/27 if ℓ is not divisible by three, and is equal to zero otherwise. The case ℓ=5 resolves a problem suggested by Reiher.
A 3-connected graph G is essentially 4-connected if, for any 3-cut S⊆V(G) of G, at most one component of G−S contains at least two vertices. We prove that every essentially 4-connected maximal planar graph G on n vertices contains a cycle of length at least 32(n+4); moreover, this bound is sharp.
In the model of randomly perturbed graphs we consider the union of a deterministic graph Gα with minimum degree αn and the binomial random graph G(n,p). This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac's theorem and the results by Posá and Koršunov on the threshold in G(n,p). In this note we extend this result in Gα∪G(n,p) to sparser graphs with α=o(1). More precisely, for any ε>0 and α:N↦(0,1) we show that a.a.s. Gα∪G(n,β/n) is Hamiltonian, where β=−(6+ε)log(α). If α>0 is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if α=O(1/n) the random part G(n,p) is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into G(n,p).
A graph is 1-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1-planar. For a 3-connected locally maximal 1-planar graph G, we show the existence of a spanning 3-connected planar subgraph and prove that G is hamiltonian if G has at most three 3-vertex-cuts, and that G is traceable if G has at most four 3-vertex-cuts. Moreover, infinitely many non-traceable 5-connected 1-planar graphs are presented.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.