𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Nearly uniform distribution of edges among k-subgraphs of a graph

✍ Scribed by Jozef Širáň; Zsolt Tuza

Book ID
102892377
Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
671 KB
Volume
16
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We investigate the behavior of the function f = f(n, k, e) defined as the smallest integer with the following property: If in a graph on n vertices, the numbers of edges in any two induced subgraphs on k vertices differ by at most e, then the graph or its complement has at most f edges. One of the results states that
. © 1929 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

The number of edges in a subgraph of a H
The number of edges in a subgraph of a Hamming graph
✍ R. Squier; B. Torrence; A. Vogt 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 363 KB

G be a subgraph of the Cartesian product Hamming graph (Kp)r with n vertices. Then the number of edges of G is at most (1/2)(p -1) log, n, with equality holding if and only G is isomorphic to (Kp)s for some s 5 r.