✦ LIBER ✦

Disjoint cliques and disjoint maximal independent sets of vertices in graphs

✍ Scribed by Paul Erdös; Arthur M. Hobbs; C. Payan

Publisher: Elsevier Science
Year: 1982
Tongue: English
Weight: 548 KB
Volume: 42
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(82)90053-x

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Largest and smallest maximal sets of pai

Largest and smallest maximal sets of pairwise disjoint partitions

✍ Melvyn B Nathanson 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 314 KB

Maximal independent sets in bipartite gr

Maximal independent sets in bipartite graphs

✍ Jiuqiang Liu 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 458 KB 👁 1 views

## Abstract A maximal independent set of a graph __G__ is an independent set that is not contained properly in any other independent set of __G.__ In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order __n__ and the extremal graphs as well as

Generalizations of Grillet's theorem on

Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs

✍ Wenan Zang 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 639 KB

The maximal size of graphs with at most

The maximal size of graphs with at most k edge-disjoint paths connecting any two adjacent vertices

✍ Mao-cheng Cai 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 502 KB

Let n and k be positive integers satisfying k + 1 s n s 3k -1, and G a simple graph of order n and size e(G) with at most k edge-disjoint paths connecting any two adjacent vertices. In this paper we prove that e(G) s l(n + k)\*/8], and give complete characterizations of the extremal graphs and the e

Clique polynomials and independent set p

Clique polynomials and independent set polynomials of graphs

✍ Cornelis Hoede; Xueliang Li 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 492 KB

This paper introduces two kinds of graph polynomials, clique polynomial and independent set polynomial. The paper focuses on expansions of these polynomials. Some open problems are mentioned.

Maximal matchings in graphs with large n

Maximal matchings in graphs with large neighborhoods of independent vertices

✍ I. Rinsma; C. H. C. Little; D. R. Woodall 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract We obtain lower bounds on the size of a maximum matching in a graph satisfying the condition |__N(X)__| ≥ __s__ for every independent set __X__ of __m__ vertices, thus generalizing results of Faudree, Gould, Jacobson, and Schelp for the case __m__ = 2.