Independent sets in tensor graph powers

DOI10.1002/JGT.20194MaRDI QIDQ3418735zbMATH OpenOpenAlexFDO

Authors Noga Alon, Eyal Lubetzky

Publication date 24 January 2007

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

independence ratiotensor product

Mathematics Subject Classification ID

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

Abstract: The tensor product of two graphs, $G$ and $H$, has a vertex set $V(G)imesV(H)$ and an edge between $(u,v)$ and $(u^{\prime },v^{\prime })$ iff both $u{u}^{\prime }inE(G)$ and $v{v}^{\prime }inE(H)$. Let $A(G)$ denote the limit of the independence ratios of tensor powers of $G$, $limalpha(G^n)/|V(G^n)|$. This parameter was introduced by Brown, Nowakowski and Rall, who showed that $A(G)$ is lower bounded by the vertex expansion ratio of independent sets of $G$. In this note we study the relation between these parameters further, and ask whether they are in fact equal. We present several families of graphs where equality holds, and discuss the effect the above question has on various open problems related to tensor graph products.

Recommendations

• Independent sets of maximal size in tensor powers of vertex-transitive graphs
• Measure preserving homomorphisms and independent sets in tensor graph powers
• scientific article; zbMATH DE number 2192126
• Independent sets in tensor products of three vertex-transitive graphs
• Independence ratios of graph powers

Cited in

(32)

• Measure preserving homomorphisms and independent sets in tensor graph powers
• A note on the connectivity of Kronecker products of graphs
• Reformulated reciprocal degree distance of graph operations
• On edge connectivity of direct products of graphs
• Harary index of product graphs
• Linear-time algorithms for tree root problems
• On maximum independent set of categorical product and ultimate categorical ratios of graphs
• Perfect fractional matchings in \(k\)-out hypergraphs
• Independent sets in graph powers are almost contained in juntas
• On independent domination in direct products
• High dimensional Hoffman bound and applications in extremal combinatorics
• Super connectivity of Kronecker product of complete bipartite graphs and complete graphs
• On the super connectivity of Kronecker products of graphs
• The super edge connectivity of Kronecker product graphs
• Reformulated reciprocal product degree distance of strong product of graphs
• Reciprocal degree distance of product graphs
• Topological efficiency of some product graphs
• Vertex isoperimetry and independent set stability for tensor powers of cliques
• The restricted edge-connectivity of Kronecker product graphs
• Wiener index of the tensor product of cycles
• SUPER EDGE CONNECTIVITY OF KRONECKER PRODUCTS OF GRAPHS
• Reformulated reciprocal product degree distance of strong product of graphs
• Isolated scattering number of split graphs and graph products
• Further properties on the degree distance of graphs
• Wiener and vertex \(PI\) indices of Kronecker products of graphs
• A Heuristic for Direct Product Graph Decomposition
• Mapping connectivity patterns: degree-based topological indices of corona product graphs
• Unimodality of the independence polynomial of G (K_p K_q)
• On the ultimate categorical independence ratio
• On some topological indices of the tensor products of graphs
• Super connectivity of Kronecker products of graphs
• Vertex vulnerability parameters of Kronecker products of complete graphs

This page was built for publication: Independent sets in tensor graph powers

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