✦ LIBER ✦

On the cyclomatic number of a hypergraph

✍ Scribed by B.D. Acharya

Publisher: Elsevier Science
Year: 1979
Tongue: English
Weight: 572 KB
Volume: 27
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(79)90103-1

No coin nor oath required. For personal study only.

✦ Synopsis

This note generalizes the notion of cyclomatic number (or cycle rank) from Graph Theory to

Hypergraph Theory and links it up with the concept of planarity in hypergraphs which was recently introducea by R.P. Jones. Sharp bounds are obtained for the cyclomatic number of the planar hypergraphs and, further, it is shown that the upper bound is attainable if, ?nd only if the hypergraph satisfies Krewera's condition.

📜 SIMILAR VOLUMES

A lower bound on the independence number

A lower bound on the independence number of arbitrary hypergraphs

✍ Thiele, Torsten 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB 👁 3 views

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies α(H) ≥ v∈V f (d

The chromatic numbers of random hypergra

The chromatic numbers of random hypergraphs

✍ Michael Krivelevich; Benny Sudakov 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 1 views

For a pair of integers 1 F ␥r, the ␥-chromatic number of an r-uniform Ž . hypergraph H s V, E is the minimal k, for which there exists a partition of V into subsets < < T, . . . , T such that e l T F ␥ for every e g E. In this paper we determine the asymptotic 1 k i Ž . behavior of the ␥-chromatic n

On the maximum number of edges in a hype

On the maximum number of edges in a hypergraph whose linegraph contains no cycle

✍ J.-C. Bermond; P. Frankl; F. Sterboul 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 122 KB

Soit H = (X. ~1 un hypergraphe h-uniforme avec IX] = net soit L h ~(H! le graphe Jont les sommets reprdsentent les arates de H, deux sommets 6lant reli6s si et seulement si t~s z~r6tes qu'ils reprdsen!ent intersectent en h -1 sommet,=. Nous montrons que sif,, t(H) ne contienl pas de cycle, alors I~[

The largest transversal numbers of unifo

The largest transversal numbers of uniform hypergraphs

✍ Qingchuan Zhu 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 492 KB

If H is an r-uniform hypergraph of order p without (r + 1)-cliques, then the transversal number of H has an upper bound in terms of the parameter c = p -2r. As corollaries of the main theorem, lower bounds for the largest order of r-uniform hypergraphs with specified transversal number and for the s

On the independence number of the Erdős-

On the independence number of the Erdős-Rényi and projective norm graphs and a related hypergraph

✍ Dhruv Mubayi; Jason Williford 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

## Abstract The Erdős‐Rényi and Projective Norm graphs are algebraically defined graphs that have proved useful in supplying constructions in extremal graph theory and Ramsey theory. Their eigenvalues have been computed and this yields an upper bound on their independence number. Here we show that

On testing the ‘pseudo-randomness’ of a

On testing the ‘pseudo-randomness’ of a hypergraph

✍ Julie Haviland; Andrew Thomason 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 405 KB

Haviland, J. and A. Thomason, On testing the 'pseudo-randomness' of a hypergraph, Discrete Mathematics 103 (1992) 321-327. By Haviland and Thomason (1989) a definition for a pseudo-random hypergraph was proposed, and the resemblance between these pseudo-random hypergraphs and random hypergraphs was