✦ LIBER ✦

On maximum internally stable sets of a graph

✍ Scribed by U. J. Nieminen

Publisher: John Wiley and Sons
Year: 1974
Tongue: English
Weight: 270 KB
Volume: 21
Category: Article
ISSN: 0894-069X
DOI: 10.1002/nav.3800210315

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The Cardinality of the Collection of Max

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

✍ Shu-Chu Chang; Yeong-Nan Yeh 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 226 KB

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

On the maximum number of cycles in a pla

On the maximum number of cycles in a planar graph

✍ R. E. L. Aldred; Carsten Thomassen 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 2 views

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__ − __p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__ − 1^ = __o__(2^__r__ − 1^) cycles. The planar result is best possib

The Relative Maximum Genus of a Graph

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

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

On minimum sets of 1-factors covering a

On minimum sets of 1-factors covering a complete multipartite graph

✍ David Cariolaro; Hung-Lin Fu 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB 👁 1 views

## Abstract We determine necessary and sufficient conditions for a complete multipartite graph to admit a set of 1‐factors whose union is the whole graph and, when these conditions are satisfied, we determine the minimum size of such a set. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:239‐250,

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