Independent sets in tensor graph powers

Noga Alon, Eyal Lubetzky

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

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 uu′ ∈ E(G) and vv′ ∈ E(H). Let A(G) denote the limit of the independence ratios of tensor powers of G, lim α(Gn)/|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.

Original languageEnglish (US)
Pages (from-to)73-87
Number of pages15
JournalJournal of Graph Theory
Volume54
Issue number1
DOIs
StatePublished - Jan 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Independence ratio
  • Tensor graph powers
  • Vertex transitive graphs

Fingerprint

Dive into the research topics of 'Independent sets in tensor graph powers'. Together they form a unique fingerprint.

Cite this