Independent sets in direct products of vertex-transitive graphs

DOI10.1016/J.JCTB.2011.12.005MaRDI QIDQ414657zbMATH OpenOpenAlexFDO

Authors Hua Jun Zhang

Publication date 11 May 2012

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

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

zbMATH Keywords

direct productindependence numbervertex transitive graphs

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(23)

• Intersecting k-uniform families containing all the k-subsets of a given set
• On maximum independent set of categorical product and ultimate categorical ratios of graphs
• On maximum intersecting sets in direct and wreath product of groups
• The \(k\)-independence number of direct products of graphs and Hedetniemi's conjecture
• Fractional chromatic numbers of tensor products of three graphs
• Structure of independent sets in direct products of some vertex-transitive graphs
• On the strong metric dimension of Cartesian and direct products of graphs
• The fractional version of Hedetniemi's conjecture is true
• Vertex-transitive direct products of graphs
• scientific article; zbMATH DE number 773194 (Why is no real title available?)
• Independent sets in direct product of vertex-transitive graphs
• Maximum independent sets in direct products of cycles or trees with arbitrary graphs
• Intersecting \(k\)-uniform families containing a given family
• Isoperimetry, stability, and irredundance in direct products
• Independent sets in tensor products of three vertex-transitive graphs
• Paley-type graphs of order a product of two distinct primes
• Independence and coloring properties of direct products of some vertex-transitive graphs
• Intersecting families in symmetric unions of direct products of set families
• Independence in direct-product graphs
• Primitivity and independent sets in direct products of vertex-transitive 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)