✦ LIBER ✦

Sharp bounds on the order, size, and stability number of graphs

✍ Scribed by Pierre Hansen; Maolin Zheng

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 276 KB
Volume: 23
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230230204

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We consider graphs G = (V,E) with order ρ = |V|, size e = |E|, and stability number β~0~. We collect or determine upper and lower bounds on each of these parameters expressed as functions of the two others. We prove that all these bounds are sharp. © 1993 by John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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

Sharp bounds for the number of 3-indepen

Sharp bounds for the number of 3-independent partitions and the chromaticity of bipartite graphs

✍ F. M. Dong; K. M. Koh; K. L. Teo; C. H. C. Little; M. D. Hendy 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB

## Abstract Given a graph __G__ and an integer __k__ ≥ 1, let α(__G, k__) denote the number of __k__‐independent partitions of __G__. Let 𝒦^−s^(__p,q__) (resp., 𝒦~2~^−s^(__p,q__)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph __K~p,q

Bounds on the number of Hadamard designs

Bounds on the number of Hadamard designs of even order

✍ Clement Lam; Sigmund Lam; Vladimir D. Tonchev 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB

## Abstract A new lower bound on the number of non‐isomorphic Hadamard symmetric designs of even order is proved. The new bound improves the bound on the number of Hadamard designs of order 2__n__ given in [12] by a factor of 8__n__ − 1 for every odd __n__ > 1, and for every even __n__ such that 4_

New bounds for the chromatic number of g

New bounds for the chromatic number of graphs

✍ Manouchehr Zaker 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract In this article we first give an upper bound for the chromatic number of a graph in terms of its degrees. This bound generalizes and modifies the bound given in 11. Next, we obtain an upper bound of the order of magnitude ${\cal O}({n}^{{1}-\epsilon})$ for the coloring number of a graph

Sharp Bounds on the Number of Scattering

Sharp Bounds on the Number of Scattering Poles in the Two Dimensional Case

✍ Georgi Vodev 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 458 KB

Lower bounds on the number of triangles

Lower bounds on the number of triangles in a graph

✍ David C. Fisher 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 1 views