Search

Your search keyword '"MUBAYI, DHRUV"' showing total 23 results
Start Over Author "MUBAYI, DHRUV" Journal journal of graph theory
23 results on '"MUBAYI, DHRUV"'

2. On a generalized Erdős–Rademacher problem.

Author

Liu, Xizhi and Mubayi, Dhruv

Subjects
*GRAPH coloring, *CHARTS, diagrams, etc., *TRIANGLES, *INTEGERS
Abstract

The triangle covering number of a graph is the minimum number of vertices that hit all triangles. Given positive integers s,t and an n‐vertex graph G with ⌊n2∕4⌋+t edges and triangle covering number s, we determine (for large n) sharp bounds on the minimum number of triangles in G and also describe the extremal constructions. Similar results are proved for cliques of larger size and color critical graphs. This extends classical work of Rademacher, Erdős, and Lovász–Simonovits whose results apply only to s≤t. Our results also address two conjectures of Xiao and Katona. We prove one of them and give a counterexample and prove a modified version of the other conjecture. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

4. Multiple vertex coverings by specified induced subgraphs

Author

Furedi, Zoltan, Mubayi, Dhruv, and West, Douglas B.

Subjects
05C35, 05C70, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Combinatorics (math.CO), Geometry and Topology
Abstract

Given graphs H_1,...,H_k, we study the minimum order of a graph G such that for each i, the induced copies of H_i in G cover V(G). We prove a general upper bound of twice the sum of the numbers m_i, where m_i is one less than the order of H_i. When k=2 and one graph is an independent set of size n, we determine the optimum within a constant. When k=2 and the graphs are a star and an independent set, we determine the answer exactly., 10 pages, 3 figures

Published
2000

8. Coloring Triple Systems with Local Conditions.

Author

Mubayi, Dhruv

Subjects
*HYPERGRAPHS, *GEOMETRIC vertices, *GRAPH coloring, *EDGES (Geometry), *MATHEMATICAL bounds
Abstract

We produce an edge-coloring of the complete 3-uniform hypergraph on n vertices with [ABSTRACT FROM AUTHOR]

Published
2016
Full Text
View/download PDF

23. How many disjoint 2‐edge paths must a cubic graph have?

Author

Kelmans, Alexander and Mubayi, Dhruv

Abstract

In this paper we show that every simple cubic graph on nvertices has a set of at least ⌈ n/4 ⌉ disjoint 2‐edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a set in a simple cubic graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 57–79, 2003

Published
2004
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results