zbMATH — the first resource for mathematics

Independent sets in tensor graph powers. (English) Zbl 1108.05068
Authors’ abstract: The tensor product of two graphs, \(G\) and \(H\), has a vertex set \(V(G) \times V(H)\) and an edge between \((u,v)\) and \((u',v')\) if and only if both \(u\, u'\in E(G)\) and \(v\, v'\in E(H)\). Let \(A(G)\) denote the limit of the independence ratios of tensor powers of \(G, \lim \alpha (G^n)/|V(G^n)|\). This parameter was introduced in [J. I. Brown, R. J. Nowakowski and D. Rall, SIAM J. Discrete Math. 9, No. 2, 290–300 (1996; Zbl 0848.05036)], where it was shown that \(A(G)\) is lower bounded by the vertex expansion ratio of independent sets of \(G\). In this article 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.

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Zbl 0848.05036
Full Text: DOI arXiv
[1] Alon, Geometric Funct Anal 14 pp 913– (2004)
[2] , , and , The isoperimetric constant of the random graph process: Random structores and algorithms (to appear).
[3] Bollobás, Proc Amer Math Soc 83 pp 433– (1981)
[4] Random Graphs, 2nd Edition, Cambridge University Press, Cambridge, 2001.
[5] Brown, SIAM J Disc Math 9 pp 290– (1996)
[6] Füredi, Combinatorica 1 pp 233– (1981)
[7] Homomorphisms of graphs and automata, University of Michigan Technical Report 03105-44-T, 1966.
[8] Friedman, Combinatorica 11 pp 331– (1991)
[9] Greenwell, Acta Math Acad Sci Hungar 25 pp 335– (1974)
[10] Larose, Combinatorica 20 pp 531– (2000)
[11] and , Matching Theory, North-Holland, Amsterdam, 1986.
[12] Shamir, Israel J Math 39 pp 296– (1981)
[13] The fractional chromatic number of the categorical product of graphs, Combinatorica, to appear.
[14] Tardif, Comment Math Univ Carolin 42 pp 353– (2001)
[15] Wormald, Ann Appl Probability 5 pp 1217– (1995)
[16] Zhu, Glasgow Mathematical J 44 pp 103– (2002)
[17] Zhu, Taiwanese J Math 2 pp 1– (1998)
[18] Zhu, J Graph Theory 16 pp 557– (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.