✦ LIBER ✦

The Cardinality of the Collection of Maximum Independent Sets of a Functional Graph

✍ Scribed by Shu-Chu Chang; Yeong-Nan Yeh

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 226 KB
Volume: 18
Category: Article
ISSN: 0196-8858
DOI: 10.1006/aama.1996.0509

No coin nor oath required. For personal study only.

✦ Synopsis

An independent set or stable set of a graph G V, E is a subset S of the Ž . vertices set V in which no two are adjacent. Let G be the number of vertices in Ž . a stable set of maximum cardinality; G is called the stability number of G. Stability numbers of a graph have been well studied, but little has been done on the number of independent subsets whose cardinality is the stability number. In this paper we will provide an algorithm to find the number of independent subsets whose cardinality is the stability number.

📜 SIMILAR VOLUMES

On maximum internally stable sets of a g

On maximum internally stable sets of a graph

✍ U. J. Nieminen 📂 Article 📅 1974 🏛 John Wiley and Sons 🌐 English ⚖ 270 KB

On the Maximum Number of Independent Cyc

On the Maximum Number of Independent Cycles in a Bipartite Graph

✍ Hong Wang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 404 KB

Let G=(V 1 , V 2 ; E ) be a bipartite graph with |V 1 |= |V 2 | =n 2k, where k is a positive integer. Suppose that the minimum degree of G is at least k+1. We show that if n>2k, then G contains k vertex-disjoint cycles. We also show that if n=2k, then G contains k&1 quadrilaterals and a path of orde

Maximum independent sets of circular-arc

Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs

✍ Zheng, S. Q. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 421 KB 👁 2 views

We present a simple optimal algorithm for the problem of finding maximum independent sets of circular-arc graphs. Given an intersection model S of a circular-arc graph G , our algorithm computes a maximum independent set of G in O ( n ) space and O ( n ) or O(n log n ) time, depending on whether the

The number of maximal independent sets i

The number of maximal independent sets in connected graphs

✍ Zoltán Füredi 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB 👁 2 views

Generalizing a theorem of Moon and Moser. we determine the maximum number of maximal independent sets in a connected graph on n vertices for n sufficiently large, e.g., n > 50. = I .32. . .). Example 1.2. Let b, = i(C,), where C,z denotes the circuit of length n. Then b, = 3, 6, = 2, b, = 5, and b,

The Relative Maximum Genus of a Graph

✍ C.P. Bonnington 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 422 KB

On the Cardinality of Intersection Sets

On the Cardinality of Intersection Sets in Inversive Planes

✍ Marcus Greferath; Cornelia Rößing 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 115 KB

Intersection sets and blocking sets play an important role in contemporary finite geometry. There are cryptographic applications depending on their construction and combinatorial properties. This paper contributes to this topic by answering the question: how many circles of an inversive plane will b