Independent sets in tensor graph powers

Details Independent sets in tensor graph powers Independent sets in tensor graph powers

2006-08-03

arxiv.org/abs/math/0608090v1

Mathematics

Combinatorics

Scientific paper

The tensor product of two graphs, $G$ and $H$, has a vertex set $V(G)\times V(H)$ and an edge between $(u,v)$ and $(u',v')$ iff both $u u' \in E(G)$ and $v v' \in E(H)$. Let $A(G)$ denote the limit of the independence ratios of tensor powers of $G$, $\lim \alpha(G^n)/|V(G^n)|$. This parameter was introduced by Brown, Nowakowski and Rall, who showed that $A(G)$ is lower bounded by the vertex expansion ratio of independent sets of $G$. In this note 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.

Affiliated with

Also associated with

No associations

Rating

Independent sets in tensor graph powers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Independent sets in tensor graph powers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Independent sets in tensor graph powers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-50864