Independent Sets in Direct Products of Vertex-transitive Graphs

Details Independent Sets in Direct Products of Vertex-transitive Graphs Independent Sets in Direct Products of Vertex-transitive Graphs

2010-07-06

arxiv.org/abs/1007.0797v1

Mathematics

Combinatorics

11 pages

Scientific paper

The direct product $G\times H$ of graphs $G$ and $H$ is defined by: \[V(G\times H)=V(G)\times V(H)\] and \[E(G\times H)=\left\{[(u_1,v_1),(u_2,v_2)]: (u_1,u_2)\in E(G) \mbox{\ and\ } (v_1,v_2)\in E(H)\right\}.\] In this paper, we will prove that the equality $$\alpha(G\times H)=\max\{\alpha(G)|H|, \alpha(H)|G|\}$$ holds for all vertex-transitive graphs $G$ and $H$, which provides an affirmative answer to a problem posed by Tardif (Discrete Math. 185 (1998) 193-200). Furthermore, the structure of all maximum independent sets of $G\times H$ are determined.

Affiliated with

Also associated with

No associations

Rating

Independent Sets in Direct Products of Vertex-transitive Graphs 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 Direct Products of Vertex-transitive Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Independent Sets in Direct Products of Vertex-transitive Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-215878