𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Number of Edges of Quadrilateral-Free Graphs

✍ Scribed by Zoltán Füredi

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
247 KB
Volume
68
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

If a graph has q 2 +q+1 vertices (q>13), e edges and no 4-cycles then e 1 2 q(q+1) 2 . Equality holds for graphs obtained from finite projective planes with polarities. This partly answers a question of Erdo s from the 1930's.

1996 Academic Press, Inc.

1. Results

Let f (n) denote the maximum number of edges in a (simple) graph on n vertices without four-cycles, (i.e., quadrilateral-free). Erdo s [6] proposed the problem of determining f (n) more than 50 years ago, and still no formula appears to be known. McCuaig [15] calculated f (n) for n 21. Clapham, Flockart and Sheehan [4] determined all the extremal graphs for n 21. This analysis was extended to n 31 by Yuansheng and Rowlinson [18] by an extensive computer search. Asymptotically f (n)t 1 2 n 3Â2 (see Brown [2] and Erdo s, Re nyi and T. So s [10]).

If q is a prime power and n=q 2 +q+1, then a graph with n vertices and article no. 0052

📜 SIMILAR VOLUMES

Saturated graphs with minimal number of
Saturated graphs with minimal number of edges
✍ L. Kászonyi; Zs. Tuza 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB

Let F = {F,, . . .} be a given class of forbidden graphs. A graph G is called F-saturated if no F, E F is a subgraph of G but the addition of an arbitrary new edge gives a forbidden subgraph. In this paper the minimal number of edges in F-saturated graphs is examined. General estimations are given a

The Number of Removable Edges in 3-Conne
The Number of Removable Edges in 3-Connected Graphs
✍ Su Jianji 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 147 KB

An edge of a 3-connected graph G is said to be removable if G&e is a subdivision of a 3-connected graph. Holton et al. (1990) proved that every 3-connected graph of order at least five has at least W(|G| +10)Â6X removable edges. In this paper, we prove that every 3-connected graph of order at least

On the Number of 3-Edge Colorings of Cub
On the Number of 3-Edge Colorings of Cubic Graphs
✍ Christian Szegedy 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 127 KB

In this paper we present a short algebraic proof for a generalization of a formula of R. Penrose, Some applications of negative dimensional tensors, in: Combinatorial Mathematics and its Applications Welsh (ed.), Academic Press, 1971, pp. 221-244 on the number of 3-edge colorings of a plane cubic gr

The number of connected sparsely edged g
The number of connected sparsely edged graphs
✍ E. M. Wright 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 472 KB

## Abstract An (__n, q__) graph has __n__ labeled points, __q__ edges, and no loops or multiple edges. The number of connected (__n, q__) graphs is __f(n, q)__. Cayley proved that __f(n, n__^‐1^) = __n__^n−2^ and Renyi found a formula for __f(n, n)__. Here I develop two methods to calculate the exp

Numbers of edges in supermagic graphs
Numbers of edges in supermagic graphs
✍ Svetlana Drajnová; Jaroslav Ivančo; Andrea Semaničová 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB

## Abstract A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper we establish some bounds for the number of edges in sup

A sharp edge bound on the interval numbe
A sharp edge bound on the interval number of a graph
✍ Balogh, J�zsef; Pluh�r, Andr�s 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB 👁 2 views

The interval number of a graph G, denoted by i(G), is the least natural number t such that G is the intersection graph of sets, each of which is the union of at most t intervals. Here we settle a conjecture of Griggs and West about bounding i(G) in terms of e, that is, the number of edges in G. Name