✦ LIBER ✦

Primitivity and independent sets in direct products of vertex-transitive graphs

✍ Scribed by Huajun Zhang

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 92 KB
Volume: 67
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20526

No coin nor oath required. For personal study only.

✦ Synopsis

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 an open problem related to the structure of independent sets in powers of vertex-transitive graphs.

📜 SIMILAR VOLUMES

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

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

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

Triangles and Neighbourhoods of Independ

Triangles and Neighbourhoods of Independent Sets in Graphs

✍ Andrew M. Robertshaw; Douglas R. Woodall 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 124 KB

It is proved that a graph of order n contains a triangle if |N(X )| > 1 3 (n+|X |) for every independent set X of vertices. This bound is sharp.

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,

Constraints on the number of maximal ind

Constraints on the number of maximal independent sets in graphs

✍ Jiuqiang Liu 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 387 KB 👁 2 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__. Let __i(G)__ denote the number of maximal independent sets of __G__. Here, we prove two conjectures, suggested by P. Erdös, that the maximum number of m