✦ LIBER ✦

Independent sets in tensor graph powers

✍ Scribed by Alon, Noga (author);Lubetzky, Eyal (author)

Publisher: Wiley-Liss Inc.
Year: 2006
Tongue: English
Weight: 154 KB
Volume: 54
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20194

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The tensor product of two graphs, G and H, has a vertex set V(G) × V(H) and an edge between (u,v) and (u′,v′) iff both u u′ ∈ E(G) and v v′ ∈ E(H). Let A(G) denote the limit of the independence ratios of tensor powers of G, lim, α(G^n^)/|V(G^n^)|. This parameter was introduced in [Brown, Nowakowski, Rall, SIAM J Discrete Math 9 (1996), 290–300], where it was shown that A(G) is lower bounded by the vertex expansion ratio of independent sets of G. In this article we study the relation between these parameters further, and ask whether they are in fact equal. We present several families of graphs where equality holds, and discuss the effect the above question has on various open problems related to tensor graph products. © 2006 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Independent sets in tensor graph powers

✍ Alon, Noga (author);Lubetzky, Eyal (author) 📂 Article 📅 2006 🏛 Wiley-Liss Inc. 🌐 English ⚖ 154 KB

Independent sets in tensor graph powers

✍ Alon, Noga (author);Lubetzky, Eyal (author) 📂 Article 📅 2006 🏛 Wiley-Liss Inc. 🌐 English ⚖ 154 KB

Independent sets in tensor graph powers

✍ Alon, Noga (author);Lubetzky, Eyal (author) 📂 Article 📅 2006 🏛 Wiley-Liss Inc. 🌐 English ⚖ 154 KB

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

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

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