𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Independent Vertex Sets in Subclasses of

✍ Scribed by Andreas Brandstädt; Tilo Klembt; Vadim V. Lozin; Raffaele Mosca

Book ID
106148904
Publisher
Springer
Year
2008
Tongue
English
Weight
344 KB
Volume
56
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On feedback vertex sets and nonseparatin
On feedback vertex sets and nonseparating independent sets in cubic graphs
✍ Ewald Speckenmeyer 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 341 KB

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

On locally optimal independent sets and
On locally optimal independent sets and vertex covers
✍ Gang Yu; Olivier Goldschmidt 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 665 KB

In this paper, we introduce a new notion of local optimality and demonstrate its application to the problem of finding optimal independent sets and vertex covers in k-claw free graphs. The maximum independent set problem in k-claw free graphs has interesting applications in the design of electronic

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