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
In this paper, we prove that for every k and every graph H with m edges and no isolated vertices, the Ramsey number R(Ck,H) is at most 2m+⌊2k−1⌋, provided m is sufficiently large with respect to k. This settles a problem of Erdős, Faudree, Rousseau and Schelp.
A set of vertices in a graph is a Hamiltonian subset if it induces a subgraph containing a Hamiltonian cycle. Kim, Liu, Sharifzadeh and Staden proved that among all graphs with minimum degree d, Kd+1 minimises the number of Hamiltonian subsets. We prove a near optimal lower bound that takes also the order and the structure of a graph into account. For many natural graph classes, it provides a much better bound than the extremal one (≈2d+1). Among others, our bound implies that an n-vertex C4-free graphs with minimum degree d contains at least n2d2−o(1) Hamiltonian subsets.
The Sudoku number has been defined under various names, indicating it is a natural concept. There are four variants of this parameter, that can be related to the maximum and minimum size of a critical set in a graph colouring problem. For each of these four related parameters, we present some simple characterizations of the graphs attaining the maximum possible values. As a main result, we answer a question by Cooper and Kirkpatrick, showing that there is monotone behaviour in the number of colours for only two of the four parameters. We investigate the monotone behaviour for the subgraph-order as well. For Latin squares and the Sudoku, we solve some variants for hypergraph colouring.
The first degree-based entropy of a graph is the Shannon entropy of its degree sequence normalized by the degree sum. Its correct interpretation as a measure of uniformity of the degree sequence requires the determination of its extremal values given natural constraints. In this paper, we prove that the graphs with given size that minimize the first degree-based entropy are the colex graphs.
In 1984, Plesník determined the minimum total distance for given order and diameter and characterized the extremal graphs and digraphs. We prove the analog for given order and radius, when the order is sufficiently large compared to the radius. This confirms asymptotically a conjecture of Chen et al. We also state an analog of the conjecture of Chen et al for digraphs and prove it for sufficiently large order.
We characterize the bipartite graphs that minimize the (first-degree based) entropy, among all bipartite graphs of given size, or given size and (upper bound on the) order. The extremal graphs turn out to be complete bipartite graphs, or nearly complete bipartite. Here we make use of an equivalent representation of bipartite graphs by means of Young tableaux, which make it easier to compare the entropy of related graphs. We conclude that the general characterization of the extremal graphs is a difficult problem, due to its connections with number theory, but they are easy to find for specific values of the order n and size m. We also give a direct argument to characterize the graphs maximizing the entropy given order and size. We indicate that some of our ideas extend to other degree-based topological indices as well.
In 1967, Vizing determined the maximum size of a graph with given order and radius. In 1973, Fridman answered the same question for digraphs with given order and outradius. We investigate that question when restricting to biconnected digraphs. Biconnected digraphs are the digraphs with a finite total distance and hence the interesting ones, as we want to note a connection between minimizing the total distance and maximizing the size under the same constraints. We characterize the extremal digraphs maximizing the size among all biconnected digraphs of order n and outradius 3, as well as when the order is sufficiently large compared to the outradius. As such, we solve a problem of Dankelmann asymptotically. We also consider these questions for bipartite digraphs and solve a second problem of Dankelmann partially.
The first degree-based entropy of a graph is the Shannon entropy of its degree sequence normalized by the degree sum. In this paper, we characterize the connected graphs with given order n and size m that minimize the first degree-based entropy whenever n−1≤m≤2n−3, thus extending and proving a conjecture by Yan.
Extending the methods of Metrebian (2018), we prove that any symmetric punctured interval tiles Z3. This solves two questions of Metrebian and completely resolves a question of Gruslys, Leader and Tan. We also pose a question that asks whether there is a relation between the genus g (number of holes) in a one-dimensional tile T and a uniform bound d such that T tiles Zd. An affirmative answer would generalize a conjecture of Gruslys, Leader and Tan (2016).
We study lattice-theoretical extensions of the celebrated Sauer-Shelah-Perles Lemma. We conjecture that a general Sauer-Shelah-Perlem Lemma holds for a lattice L if and only if L is relatively complemented, and prove partial results towards this conjecture.
Fix d≥3. We show the existence of a constant c>0 such that any graph of diameter at most d has average distance at most d−cnd3/2, where n is the number of vertices. Moreover, we exhibit graphs certifying sharpness of this bound up to the choice of c. This constitutes an asymptotic solution to a longstanding open problem of Plesník. Furthermore we solve the problem exactly for digraphs if the order is large compared with the diameter.
Motivated by a Gan-Loh-Sudakov-type problem, we introduce the regular Turán numbers, a natural variation on the classical Turán numbers for which the host graph is required to be regular. Among other results, we prove a striking supersaturation version of Mantel's theorem in the case of a regular host graph of odd order. We also characterise the graphs for which the regular Turán numbers behave classically or otherwise.
Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number χ contains a rainbow independent set of size ⌈21χ⌉. This is sharp up to a factor 2. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number χ contains an induced cycle of length Ω(χlogχ) as χ→∞. Even if one only demands an induced path of length Ω(χlogχ), the conclusion would be sharp up to a constant multiple. We prove it for regular girth 5 graphs and for girth 21 graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some c>0 such that for every forest H on D vertices, every triangle-free and induced H-free graph has chromatic number at most cD/logD. We prove this assertion with `triangle-free' replaced by `regular girth 5'.
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.