✦ LIBER ✦

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

✍ Scribed by Peter Brass; Heiko Harborth; Hauke Nienborg

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 283 KB
Volume: 19
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190190104

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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

## 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

A list version of Dirac's theorem on the

A list version of Dirac's theorem on the number of edges in colour-critical graphs

✍ Alexandr V. Kostochka; Michael Stiebitz 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB

## Abstract One of the basic results in graph colouring is Brooks' theorem [R. L. Brooks, Proc Cambridge Phil Soc 37 (1941) 194–197], which asserts that the chromatic number of every connected graph, that is not a complete graph or an odd cycle, does not exceed its maximum degree. As an extension o

The maximum number of arc-disjoint arbor

The maximum number of arc-disjoint arborescences in a tournament

✍ Ma Chung-fan; Cai Mao-cheng 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB

## Abstract In this article, we give the maximum number of arc‐disjoint arborescences in a tournament or an oriented complete __r__‐partite graph by means of the indegrees of its vertices.

On the asymptotic behavior of the maximu

On the asymptotic behavior of the maximum number of spanning trees in circulant graphs

✍ Lonc, Zbigniew; Parol, Krzysztof; Wojciechowski, Jacek M. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 3 views

The following asymptotic estimation of the maximum number of spanning trees f k (n) in 2kregular circulant graphs ( k ú 1) on n vertices is the main result of this paper: )) , where

On the asymptotic distributions of subgr

On the asymptotic distributions of subgraph counts in a random tournament

✍ Pontus Andersson 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB 👁 2 views

A random tournament T is obtained by independently orienting the edges of n 1 the complete graph on n vertices, with probability for each direction. We study the 2 asymptotic distribution, as n tends to infinity, of a suitable normalization of the number of subgraphs of T that are isomorphic to a gi

Bounding the crossing number of a graph

Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree

✍ Enrique Garcia-Moreno; Gelasio Salazar 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 76 KB 👁 2 views