A note on the least number of edges of 3-uniform hypergraphs with upper chromatic number 2

The upper chromatic number of a hypergraph H=(X,E) is the maximum number k for which there exists a partition of X into non-empty subsets X=X₁∪X₂∪?∪X_k such that for each edge at least two vertices lie in one of the partite sets. We prove that for every n?3 there exists a 3-uniform hypergraph with n vertices, upper chromatic number 2 and ⌈n(n-2)/3⌉ edges which implies that a corresponding bound proved in [K. Diao, P. Zhao, H. Zhou, About the upper chromatic number of a co-hypergraph, Discrete Math. 220 (2000) 67-73] is best-possible.     

A note on the edge cover number and independence number in hypergraphs

Consider a hypergraph of rank r>2 with m edges, independence number α and edge cover number ρ. We prove the inequality

     

Edge-deletable IM-extendable graphs with minimum number of edges

A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F⊆E(G) with |F|=k, G−F is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅K_k+2,k+2, or k=4r−2 for some integer r≥3 and G≅C₅[N_2r], where N_2r is the empty graph on 2r vertices and C₅[N_2r] is the graph obtained from C₅ by replacing each vertex with a graph isomorphic to N_2r.     

A note on hypergraphs with the Helly-property

Let H be a hypergraph and t a natural number. The sets which can be written and the union of different edges of H form a new hypergraph which is denoted by H′. Let us suppose that H has the Helly property and we want to state something similar for H′. We prove a conjecture of C, Berge and two negative results.     

Graphs of diameter 3 with the minimum number of edges

The graphG is called a porcupine, ifGA is a complete graph for some setA, every other vertex has degree one, and its only edge is joined toA. In this paper a conjecture of Bollobás is settled almost completely. Namely, it is proved that ifG is a graph onn vertices of diameter 3 with maximum degreeD, D > 2.31 ,D (n – 1)/2 and it has the mimimum number of edges, then it is a porcupine.This paper was written while the author visited the Departments of Mathematics, Tel-Aviv University, whose hospitality is gratefully acknowledged.     

The maximum spectral radius of uniform hypergraphs with given number of pendant edges

In this paper, we introduce the operations of grafting an edge and subdividing an edge on hypergraphs, and consider how spectral radius of a hypergraph behaves by grafting an edge or subdividing an edge. As an application, we determine the unique hypergraphs with the maximum spectral radius among all the uniform supertrees and all the connected uniform unicyclic hypergraphs with given number of pendant edges, respectively. Moreover, we determine the unique uniform supertree which attains the maximum spectral radius among all the uniform supertrees with given number of pendant vertices.     

Primitive graphs with given exponents and minimum number of edges

A graph G = (V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp(G), of G. In this paper, we find the minimum number, h(n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h(n, k) edges when k is 3 or even.     

On hypergraphs without two edges intersecting in a given number of vertices

Let X be a finite set of n-melements and suppose t ? 0 is an integer. In 1975, P. Erdös asked for the determination of the maximum number of sets in a family $\text{F}$ = {F₁,…, F_m}, F_i ? X, such that ∥F_i ∩ F_j∥ ≠ t for 1 ? i ≠ j ? m. This problem is solved for n ? n₀(t). Let us mention that the case t = 0 is trivial, the answer being 2^{n ? 1}. For t = 1 the problem was solved in [3]. For the proof a result of independent interest (Theorem 1.5) is used, which exhibits connections between linear algebra and extremal set theory.     

Coloring uniform hypergraphs with few edges

A hypergraph is b‐simple if no two distinct edges share more than b vertices. Let m(r, t, g) denote the minimum number of edges in an r‐uniform non‐t‐colorable hypergraph of girth at least g. Erd?s and Lovász proved that A result of Szabó improves the lower bound by a factor of r^2?? for sufficiently large r. We improve the lower bound by another factor of r and extend the result to b‐simple hypergraphs. We also get a new lower bound for hypergraphs with a given girth. Our results imply that for fixed b, t, and ? > 0 and sufficiently large r, every r‐uniform b‐simple hypergraph with maximum edge‐degree at most t^rr^1?? is t‐colorable. Some results hold for list coloring, as well. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On the minimum number of edges of two-connected graphs with given diameter

We answer the following question: what is the minimum number of edges of a 2-connected graph with a given diameter? This problem stems from survivable telecommunication network design with grade-of-service constraints. In this paper, we prove tight bounds for 2-connected graphs and for 2-edge-connected graphs. The bound for 2-connected graphs was a conjecture of B. Bollobás (AMH 75–80) [3].     

Color critical hypergraphs with many edges

We show that for all k ≥ 3, r > l ≥ 2 there exists constant c = c(k, r, l) such that for large enough n there exists a k‐color‐critical r‐uniform hypergraph on less than n vertices, having more than cn^l edges, and having no l‐set of vertices occuring in more than one edge. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 56–74, 2006     

The minimum number of triangles covering the edges of a graph

Suppose that a connected graph G has n vertices and m edges, and each edge is contained in some triangle of G. Bounds are established here on the minimum number t_min(G) of triangles that cover the edges of G. We prove that ?(n - 1)/2? ? t_min(G) with equality attained only by 3-cactii and by strongly related graphs. We obtain sharp upper bounds: if G is not a 4-clique, then. The triangle cover number t_min(G) is also bounded above by Γ(G) = m - n + c, the cyclomatic number of a graph G of order n with m edges and c connected components. Here we give a combinatorial proof for t_min(G) ? Γ(G) and characterize the family of all extremal graphs satisfying equality.     

A note on node packing polytopes on hypergraphs

A facial structure of the node packing polytope, i.e., of the convex hull of integer solutions of the node packing problem, on hypergraphs is studied. First, the results extracted by Chvàtal and by Balas and Zemel on canonical facets of the node packing polytopes on graphs are generalized to derive some specific hypergraphs having canonical facets. Second, it is shown that the facial structure of the node packing polytope on a hypergraph, named a fat graph, has a very close relationship to the facial structures of the node packing polytope and also of the convex hull of integer solutions of an integer linear program, which are defined on a specific graph corresponding to the fat graph.