Shannon Capacity and Related Graph Invariants for Lexicographic Products
This paper studies the Shannon capacity of lexicographic products of finite simple graphs, together with the Lovász theta function and the fractional Haemers number. The Shannon capacity is proved to be supermultiplicative under lexicographic products in either order, and these products are compared with the strong product. We explicitly construct three countably infinite families of lexicographic powers based on the Schläfli graph, the McLaughlin graph, and its second subconstituent; in each family, pairing each member with its complement yields strict supermultiplicativity and arbitrarily…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.06573
curl -X POST /api/v1/records/arxiv/2608.06573/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.06573/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'