Independent sets in direct products of vertex-transitive graphs (Q414657): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(7 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Hua Jun Zhang / rank | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Ortrud R. Oellermann / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C69 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6033289 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
direct product | |||
Property / zbMATH Keywords: direct product / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
vertex transitive graphs | |||
Property / zbMATH Keywords: vertex transitive graphs / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
independence number | |||
Property / zbMATH Keywords: independence number / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Hua Jun Zhang / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1974993270 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1007.0797 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The intersection theorem for direct products / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Homomorphisms of 3-chromatic graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A short proof of a cross-intersection theorem of Hilton / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cross-intersecting families of permutations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Multiple cross-intersecting families of signed sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Erdös-Ko-Rado theorem for direct products / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2713636 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Independent sets of maximal size in tensor powers of vertex-transitive graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Intersecting families in the alternating group and direct product of symmetric groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Projectivity and independent sets in powers of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph products and the chromatic difference sequence of vertex-transitive graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Independence and coloring properties of direct products of some vertex-transitive graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3577602 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cross-intersecting families and primitivity of symmetric systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Primitivity and independent sets in direct products of vertex-transitive graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The fractional chromatic number of the direct product of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The fractional version of Hedetniemi's conjecture is true / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 05:11, 5 July 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
0 references