On intersection multigraphs of hypergraphs

The sum of the cardinalities of all the edges of a hypergraph is computed in two different ways. This result is used to treat the generalisation of the notion of cyclomatic number for hypergraphs. Among others the following result is obtained: The cyclomatic number of the hypergraph H vanishes if and only if some maximum forest of the weighted intersection graph of H has the property that for every vertex of H the subgraph of the forest induced by those edges containing that vertex is connected.     

Hypergraphs with cyclomatic number zero,triangulated graphs,and an inequality

A parameter μ for hypergraphs generalizing the cyclomatic number of graphs is defined. Theorem: a hypergraph has μ = 0 if and only if its edges maximal with respect to inclusion are the cliques of a triangulated graph. The equality μ = 0 immediately implies an inequality previously proved by L. Lovász and by P. Hansen and M. Las Vergnas for more restricted classes of hypergraphs.     

The Cartesian product of hypergraphs

We show that every simple, (weakly) connected, possibly directed and infinite, hypergraph has a unique prime factor decomposition with respect to the (weak) Cartesian product, even if it has infinitely many factors. This generalizes previous results for graphs and undirected hypergraphs to directed and infinite hypergraphs. The proof adopts the strategy outlined by Imrich and ?erovnik for the case of graphs and introduces the notion of diagonal‐free grids as a replacement of the chord‐free 4‐cycles that play a crucial role in the case of graphs. This leads to a generalization of relation Δ on the arc set, whose convex hull is shown to coincide with the product relation of the prime factorization. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Nombres de coloration de l'hypergrapheh-parti complet

Summary The chromatic index, the transversal number, the clique number, etc., have all been extensively studied in Graph Theory, and can be easily extended to Hypergraphs. The author determines these coefficients for the complete multipartite hypergraphs, which g,neralize the complete bipartite graphs, and appear also in the Theory of Designs.

---

---

Entrata in Redazione il 16 maggio 1973.     

Spectra of uniform hypergraphs

We present a spectral theory of uniform hypergraphs that closely parallels Spectral Graph Theory. A number of recent developments building upon classical work has led to a rich understanding of “symmetric hyperdeterminants” of hypermatrices, a.k.a. multidimensional arrays. Symmetric hyperdeterminants share many properties with determinants, but the context of multilinear algebra is substantially more complicated than the linear algebra required to address Spectral Graph Theory (i.e., ordinary matrices). Nonetheless, it is possible to define eigenvalues of a hypermatrix via its characteristic polynomial as well as variationally. We apply this notion to the “adjacency hypermatrix” of a uniform hypergraph, and prove a number of natural analogs of basic results in Spectral Graph Theory. Open problems abound, and we present a number of directions for further study.     

Volume entropy,weighted girths and stable balls on graphs

We prove new isoperimetric inequalities on graphs involving quantities linked with concepts from differential geometry. First, we bound from above the product of the volume entropy (defined as the log of the exponential growth rate of the universal cover) and the girth of weighted graphs in terms of their cyclomatic number. In a second part, we study a natural polyhedron associated to a weighted graph: the stable ball. In particular, we relate the volume of this polyhedron, the weight of the graph and its cyclomatic number. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 291–305, 2007     

Ramsey numbers of sparse hypergraphs

Chvátal, Rödl, Szemerédi and Trotter [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, The Ramsey number of a graph with a bounded maximum degree, J. Combinatorial Theory B 34 (1983), 239–243] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, 3-uniform hypergraphs of bounded degree have linear Ramsey numbers, submitted] and [B. Nagle, S. Olsen, V. Rödl and M. Schacht, On the Ramsey number of sparse 3-graphs, preprint] the same result was proved for 3-uniform hypergraphs. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, Embeddings and Ramsey numbers of sparse k-uniform hypergraphs, submitted] we extended this result to k-uniform hypergraphs for any integer $k\ge 3$. As in the 3-uniform case, the main new tool which we proved and used is an embedding lemma for k-uniform hypergraphs of bounded maximum degree into suitable k-uniform ‘quasi-random’ hypergraphs.     

The Number of Labeled Outerplanar <Emphasis Type="Italic">k</Emphasis>-Cyclic Graphs

A k-cyclic graph is a graph with cyclomatic number k. An explicit formula for the number of labeled connected outerplanar k-cyclic graphs with a given number of vertices is obtained. In addition, such graphs with fixed cyclomatic number k and a large number of vertices are asymptotically enumerated. As a consequence, it is found that, for fixed k, almost all labeled connected outerplanar k-cyclic graphs with a large number of vertices are cacti.     

基圈数为5的2-连通平图的构造

所有的2-连通平图可通过收缩2度点变换成无2度点的、基圈数不变的2-连通平图.本文给出了基圈数为5的、无2度点的所有2-连通平图.     

Hypergraphs with large transversal number and with edge sizes at least four

Let H be a hypergraph on n vertices and m edges with all edges of size at least four. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge. Lai and Chang [An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B, 1990, 50(1), 129–133] proved that τ(H) ≤ 2(n+m)/9, while Chvátal and McDiarmid [Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26] proved that τ(H) ≤ (n + 2m)/6. In this paper, we characterize the connected hypergraphs that achieve equality in the Lai-Chang bound and in the Chvátal-McDiarmid bound.     

On non-strong jumping numbers and density structures of hypergraphs

Estimating Turán densities of hypergraphs is believed to be one of the most challenging problems in extremal set theory. The concept of ‘jump’ concerns the distribution of Turán densities. A number α∈[0,1) is a jump for r-uniform graphs if there exists a constant c>0 such that for any family F of r-uniform graphs, if the Turán density of F is greater than α, then the Turán density of F is at least α+c. A fundamental result in extremal graph theory due to Erd?s and Stone implies that every number in [0,1) is a jump for graphs. Erd?s also showed that every number in [0,r!/r^r) is a jump for r-uniform hypergraphs. Furthermore, Frankl and Rödl showed the existence of non-jumps for hypergraphs. Recently, more non-jumps were found in [r!/r^r,1) for r-uniform hypergraphs. But there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we propose a new but related concept-strong-jump and describe several sequences of non-strong-jumps. It might help us to understand the distribution of Turán densities for hypergraphs better by finding more non-strong-jumps.     

The circular chromatic number of hypergraphs

A generalization of the circular chromatic number to hypergraphs is discussed. In particular, it is indicated how the basic theory, and five equivalent formulations of the circular chromatic number of graphs, can be carried over to hypergraphs with essentially the same proofs.     

Constructing isospectral non‐isomorphic digraphs from hypergraphs

We explore the “oriented line graph” construction associated with a hypergraph, leading to a construction of pairs of strongly connected directed graphs whose adjacency operators have the same spectra. We give conditions on a hypergraph so that a hypergraph and its dual give rise to isospectral, but non‐isomorphic, directed graphs. The proof of isospectrality comes from an argument centered around hypergraph zeta functions as defined by Storm. To prove non‐isomorphism, we establish a Whitney‐type result by showing that the oriented line graphs are isomorphic if and only if the hypergraphs are. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 231–242, 2010     

Constructions of non-principal families in extremal hypergraph theory

A family F of k-graphs is called non-principal if its Turán density is strictly smaller than that of each individual member. For each k?3 we find two (explicit) k-graphs F and G such that {F,G} is non-principal. Our proofs use stability results for hypergraphs. This completely settles the question posed by Mubayi and Rödl [On the Turán number of triple systems, J. Combin. Theory A, 100 (2002) 135-152].Also, we observe that the demonstrated non-principality phenomenon holds also with respect to the Ramsey-Turán density as well.     

Semiharmonic bicyclic graphs

Classification of harmonic and semiharmonic graphs according to their cyclomatic number became of interest recently. All finite harmonic graphs with up to four independent cycles, as well as all finite semiharmonic graphs with at most one cycle were determined. Here, we determine all finite semiharmonic bicyclic graphs. Besides that, we present several methods for constructing semiharmonic graphs from existing ones, and we apply one of these constructions to show that the number of semiharmonic graphs with fixed cyclomatic number $k$ is infinite for every $k$.     

Matchings in hypergraphs of large minimum degree

It is well known that every bipartite graph with vertex classes of size n whose minimum degree is at least n/2 contains a perfect matching. We prove an analog of this result for hypergraphs. We also prove several related results that guarantee the existence of almost perfect matchings in r‐uniform hypergraphs of large minimum degree. Our bounds on the minimum degree are essentially best possible. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 269–280, 2006     

Series-parallel chromatic hypergraphs

In this paper two-terminal series-parallel chromatic hypergraphs are introduced and for this class of hypergraphs it is shown that the chromatic polynomial can be computed with polynomial complexity. It is also proved that h-uniform multibridge hypergraphs θ(h;a₁,a₂,…,a_k) are chromatically unique for h≥3 if and only if h=3 and a₁=a₂=?=a_k=1, i.e., when they are sunflower hypergraphs having a core of cardinality 2 and all petals being singletons.     

反超图的笛卡儿积的上色数

讨论反超图的笛卡儿积的着色理论 ,求出了满足一定条件的反超图的笛卡儿积的上色数 .     

Counting acyclic hypergraphs

Acyclic hypergraphs are analogues of forests in graphs. They are very useful in the design of databases. The number of distinct acyclic uniform hypergraphs withn labeled vertices is studied. With the aid of the principle of inclusion-exclusion, two formulas are presented. One is the explicitformula for strict (d)-connected acyclic hypergraphs, the other is the recurrence formula for linear acyclic hypergraphs.     

Connection between the clique number and the Lagrangian of 3-uniform hypergraphs

There is a remarkable connection between the clique number and the Lagrangian of a 2-graph proved by Motzkin and Straus (J Math 17:533–540, 1965). It would be useful in practice if similar results hold for hypergraphs. However, the obvious generalization of Motzkin and Straus’ result to hypergraphs is false. Frankl and Füredi conjectured that the r-uniform hypergraph with m edges formed by taking the first m sets in the colex ordering of \({\mathbb N}^{(r)}\) has the largest Lagrangian of all r-uniform hypergraphs with m edges. For \(r=2\), Motzkin and Straus’ theorem confirms this conjecture. For \(r=3\), it is shown by Talbot that this conjecture is true when m is in certain ranges. In this paper, we explore the connection between the clique number and Lagrangians for 3-uniform hypergraphs. As an application of this connection, we confirm that Frankl and Füredi’s conjecture holds for bigger ranges of m when \(r=3\). We also obtain two weaker versions of Turán type theorem for left-compressed 3-uniform hypergraphs.