✦ LIBER ✦

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

✍ Scribed by J.-C. Bermond; P. Frankl; F. Sterboul

Publisher: Elsevier Science
Year: 1980
Tongue: English
Weight: 122 KB
Volume: 30
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(80)90237-x

No coin nor oath required. For personal study only.

✦ Synopsis

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~[<(h~!~)/h-1. la borne t~tant cxacte pour h = 2 et poar des vatears de a pour h = 3. Ce probl~me m6ne ~ une conjecture sur les "presque syst~'me~ de Steinc:".

Let H = (X, ~) be a h-uniform hypergraph, with [X I = n ;wd let L h _ 1(HI be the graph, whose vertices are the edges of /4, two vertices being joined if and only if the edges they r.'present intersect in I~ -1 vertices. We prove that, if Lh_a(H) contains no cycle, then I~[< (~,!' ;t/h -1: moreover the bound is exact for h = 2 and with some values of n for h = 3. This probhm~ leads to a conjecture on "almost Steiner systems"

📜 SIMILAR VOLUMES

The number of edges in a maximum cycle—d

The number of edges in a maximum cycle—distributed graph

✍ Yongbing Shi 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 288 KB

Shi, Y., The number of edges in a maximum cycle-distributed graph, Discrete Mathematics 104 (1992) 205-209. Let f(n) (f\*(n)) be the maximum possible number of edges in a graph (2-connected simple graph) on n vertices in which no two cycles prove that, for every integer n > 3, f(n) 3 n + k + [i( [~(

On the maximum number of cycles in a pla

On the maximum number of cycles in a planar graph

✍ R. E. L. Aldred; Carsten Thomassen 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 2 views

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__ − __p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__ − 1^ = __o__(2^__r__ − 1^) cycles. The planar result is best possib

On the maximum number of edges in a c4-f

On the maximum number of edges in a c4-free subgraph of qn

✍ Peter Brass; Heiko Harborth; Hauke Nienborg 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 283 KB 👁 2 views

For the maximum number f ( n ) of edges in a C4-free subgraph of the n-dimensional cube-graph 0, w e prove f(n) 2 i ( n + f i ) 2 " -' for n = 4f, and f ( n ) 2 i ( n + 0.9,h)2"-' for all n 2 9. This disproves one version of a conjecture of P. Erdos.

On the Maximum Number of Independent Cyc

On the Maximum Number of Independent Cycles in a Bipartite Graph

✍ Hong Wang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 404 KB

Let G=(V 1 , V 2 ; E ) be a bipartite graph with |V 1 |= |V 2 | =n 2k, where k is a positive integer. Suppose that the minimum degree of G is at least k+1. We show that if n>2k, then G contains k vertex-disjoint cycles. We also show that if n=2k, then G contains k&1 quadrilaterals and a path of orde

On the equivalence in complexity among t

On the equivalence in complexity among three computation problems on maximum number of edge-disjoint s−t paths in a probabilistic graph

✍ Pen Cheng; Shigeru Masuyama 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 396 KB