✦ LIBER ✦

Independent sets of maximal size in tensor powers of vertex-transitive graphs

✍ Scribed by Cheng Yeaw Ku; Benjamin B. McMillan

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 97 KB
Volume: 60
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20359

No coin nor oath required. For personal study only.

✦ Synopsis

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 finite tensor powers of G, thus providing an affirmative answer to a question raised by Larose and Tardif (J Graph Theory 40(3) (2002), 162–171). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 295‐301, 2009

📜 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

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

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