✦ LIBER ✦

An upper bound on the independence number of a graph computable in polynomial-time

✍ Scribed by Carlos J. Luz

Book ID: 107918317
Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 450 KB
Volume: 18
Category: Article
ISSN: 0167-6377
DOI: 10.1016/0167-6377(95)00042-9

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An upper bound on the number of cliques

An upper bound on the number of cliques in a graph

✍ Martin Farber; Mihály Hujter; Zsolt Tuza 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 1 views

A lower bound on the independence number

A lower bound on the independence number of a graph

✍ Jochen Harant 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 210 KB

A new lower bound on the independence number of a graph is established and an accompanying efficient algorithm constructing an independent vertex set the cardinality of which is at least this lower bound is given. (~

Upper bound for the number of independen

Upper bound for the number of independent sets in graphs

✍ A. A. Sapozhenko 📂 Article 📅 2007 🏛 SP MAIK Nauka/Interperiodica 🌐 English ⚖ 175 KB

Improving an Upper Bound on the Stabilit

Improving an Upper Bound on the Stability Number of a Graph

✍ Carlos J. Luz 📂 Article 📅 2005 🏛 Springer US 🌐 English ⚖ 494 KB

A polynomial bound on the number of ligh

A polynomial bound on the number of light cycles in an undirected graph

✍ Ashok Subramanian 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 386 KB

An upper bound for the path number of a

An upper bound for the path number of a graph

✍ Alan Donald 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 529 KB

## Abstract The path number of a graph __G__, denoted __p(G)__, is the minimum number of edge‐disjoint paths covering the edges of __G.__ Lovász has proved that if __G__ has __u__ odd vertices and __g__ even vertices, then __p(G)__ ≤ 1/2 __u__ + __g__ ‐ 1 ≤ __n__ ‐ 1, where __n__ is the total numbe