Independent sets in direct products of vertex-transitive graphs (Q414657): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:13, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Independent sets in direct products of vertex-transitive graphs |
scientific article |
Statements
Independent sets in direct products of vertex-transitive graphs (English)
0 references
11 May 2012
0 references
Let \(G\) and \(H\) be graphs. The direct product of \(G\) and \(H\), denoted by \(G \times H\), has vertex set \(V(G) \times V(H)\) and edge set \(\{(u_1,v_1)(u_2,v_2):~ u_1u_2 \in E(G)\) and \(v_1v_2 \in E(H)\}\). For a graph \(F\), let \(\alpha(F)\) denote the independence number of \(F\). It is shown that if \(G\) and \(H\) are vertex transitive, then \(\alpha(G \times H) =\max\{\alpha(G)|V(H)|, \alpha(H)|V(G)|\}\). This settles an open problem posed by Tardif in 1998. The author also gives a complete description of the maximum independent sets for such direct products of graphs.
0 references
direct product
0 references
vertex transitive graphs
0 references
independence number
0 references