Independent sets in direct products of vertex-transitive graphs

DOI10.1016/J.JCTB.2011.12.005zbMATH Open1251.05130arXiv1007.0797OpenAlexW1974993270MaRDI QIDQ414657FDOQ414657

Hua Jun Zhang

Publication date: 11 May 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: The direct product $GimesH$ of graphs $G$ and $H$ is defined by: [V(G imes H)=V(G) imes V(H)] and [E(G imes 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) ight}.] In this paper, we will prove that the equality ${\displaystyle }$alpha(G imes H)=max{alpha(G)|H|, alpha(H)|G|}${\displaystyle }$ 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 $GimesH$ are determined.

Full work available at URL: https://arxiv.org/abs/1007.0797

Recommendations

• Independent sets in direct product of vertex-transitive graphs
• Structure of independent sets in direct products of some vertex-transitive graphs
• Primitivity and independent sets in direct products of vertex-transitive graphs
• Independence and coloring properties of direct products of some vertex-transitive graphs
• Independent sets in tensor products of three vertex-transitive graphs
• Independence in direct-product graphs
• scientific article; zbMATH DE number 5593359
• On \(k\)-independent sets in special products of graphs
• scientific article; zbMATH DE number 1792619
• scientific article; zbMATH DE number 528857

zbMATH Keywords

direct productindependence numbervertex transitive graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Homomorphisms of 3-chromatic graphs
• Graph products and the chromatic difference sequence of vertex-transitive graphs
• Independence and coloring properties of direct products of some vertex-transitive graphs
• An Erdös-Ko-Rado theorem for direct products
• Independence in direct-product graphs
• Primitivity and independent sets in direct products of vertex-transitive graphs
• Projectivity and independent sets in powers of graphs
• Title not available (Why is that?)
• Independent sets of maximal size in tensor powers of vertex-transitive graphs
• The fractional chromatic number of the direct product of graphs
• Cross-intersecting families and primitivity of symmetric systems
• Intersecting families in the alternating group and direct product of symmetric groups
• The fractional version of Hedetniemi's conjecture is true
• Multiple cross-intersecting families of signed sets
• A short proof of a cross-intersection theorem of Hilton
• The intersection theorem for direct products
• Cross-intersecting families of permutations

Cited In (19)

• On maximum independent set of categorical product and ultimate categorical ratios of graphs
• Intersecting \(k\)-uniform families containing all the \(k\)-subsets of a given set
• On maximum intersecting sets in direct and wreath product of groups
• Fractional chromatic numbers of tensor products of three graphs
• The \(k\)-independence number of direct products of graphs and Hedetniemi's conjecture
• Structure of independent sets in direct products of some vertex-transitive graphs
• Intersecting Families in Symmetric Unions of Direct Products of Set Families
• On the strong metric dimension of Cartesian and direct products of graphs
• Title not available (Why is that?)
• The fractional version of Hedetniemi's conjecture is true
• Title not available (Why is that?)
• Maximum independent sets in direct products of cycles or trees with arbitrary graphs
• Intersecting \(k\)-uniform families containing a given family
• Independent sets in tensor products of three vertex-transitive graphs
• Independence and coloring properties of direct products of some vertex-transitive graphs
• Independence in direct-product graphs
• Independent sets of maximal size in tensor powers of vertex-transitive graphs
• Non-trivially intersecting multi-part families
• On 3-colorings of direct products of graphs

This page was built for publication: Independent sets in direct products of vertex-transitive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414657)