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 conduct a quantitative analysis of how many random edges need to be added to a base graph H in order to significantly increase natural minor-monotone graph parameters of the resulting graph R. Specifically, we show that if R is obtained from a connected graph H by adding only a few random edges, the tree-width, genus, and Hadwiger number of R become very large, irrespective of the structure of H.
A family F is t-intersecting if any two members have at least t common elements. Erd\H os, Ko, and Rado proved that the maximum size of a t-intersecting family of subsets of size k is equal to (k−tn−t) if n≥n0(k,t). Alon, Aydinian, and Huang considered families generalizing intersecting families, and proved the same bound. In this paper, we give a strengthening of their result by considering families generalizing t-intersecting families for all t≥1. In 2004, Talbot generalized Bollobás's Two Families Theorem to t-intersecting families. In this paper, we proved a slight generalization of Talbot's result by using the probabilistic method.
An r-matching in a graph G is a collection of edges in G such that the distance between any two edges is at least r. A 2-matching is also called an induced matching. In this paper, we estimate the maximum number of r-matchings in a tree of fixed order. We also prove that the n-vertex path has the maximum number of induced matchings among all n-vertex trees.
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.