𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On feedback vertex sets and nonseparating independent sets in cubic graphs

✍ Scribed by Ewald Speckenmeyer

Publisher
John Wiley and Sons
Year
1988
Tongue
English
Weight
341 KB
Volume
12
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be an undirected connected graph with n nodes. A subset F of nodes of G is a feedback vertex set (fvs) if G -F is a forest and a subset J of nodes of G is a nonseparating independent set (nsis) if no two nodes of J are adjacent and G -J is connected. f(G), z ( G ) denote the cardinalities of a minimum fvs and a maximum nsis, respectively, of G . The equation f ( G ) = -z ( G ) + 1 and two new upper bounds on f ( G ) are derived for cubic graphs G .

πŸ“œ SIMILAR VOLUMES

Primitivity and independent sets in dire
Primitivity and independent sets in direct products of vertex-transitive graphs
✍ Huajun Zhang πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 92 KB

We introduce the concept of the primitivity of independent set in vertex-transitive graphs, and investigate the relationship between the primitivity and the structure of maximum independent sets in direct products of vertex-transitive graphs. As a consequence of our main results, we positively solve

Independent sets of maximal size in tens
Independent sets of maximal size in tensor powers of vertex-transitive graphs
✍ Cheng Yeaw Ku; Benjamin B. McMillan πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 97 KB πŸ‘ 2 views

## Abstract Let __G__ be a connected, nonbipartite vertex‐transitive graph. We prove that if the only independent sets of maximal cardinality in the tensor product __G__ Γ— __G__ are the preimages of the independent sets of maximal cardinality in __G__ under projections, then the same holds for all

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

Projectivity and independent sets in pow
Projectivity and independent sets in powers of graphs
✍ Benoit Larose; Claude Tardif πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 95 KB πŸ‘ 1 views

## Abstract We investigate the relationship between projectivity and the structure of maximal independent sets in powers of circular graphs, Kneser graphs and truncated simplices. Β© 2002 Wiley Periodicals, Inc. J Graph Theory 40: 162–171, 2002