Well-Covered Powers: Cartesian Products and Cayley Graphs

Abstract

We study graphs whose powers are well-covered, with an emphasis on Cartesian products and Cayley graphs. We first establish necessary conditions and sufficient criteria for Cartesian products, provide examples showing that a factor need not be well-covered and that two noncomplete factors can have the well-covered powers property, and classify several structured product families. In particular, we construct graphs satisfying the well-covered powers property for arbitrarily large diameters. We then show that the Cartesian square of a connected abelian Cayley graph is well-covered exactly when the graph is complete. We classify the well-covered-power graphs among connected circulant graphs of degree at most four. For Cartesian products of any number of complete graphs, we also prove that the recursive alphabet-size inequalities in the final conjecture are sufficient for all powers to be well-covered, prove partial converses for arbitrarily many factors, and give explicit obstructions for every binary prefix followed by one complete factor.

On graphs whose powers are well-covered
My Hanh Pham, Thanh Vu
arXiv7 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
S_n-equivariant L-classes of Cartesian powers of Witt spaces and the Hodge index conjecture for symmetric products
Mohammadali Aligholi
arXiv2 Nov 2026PreprintCC BY 4.0Full textAlgebra & number theory Geometry & topologyarXiv
The Pairing-Hamiltonian property in Cartesian products of graphs
Federico Romaniello
arXiv18 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Heat kernels on Cayley graphs of free products of finite groups
Kamila Kashaeva
arXiv23 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theory Analysis & PDEsarXiv
Covering Families for DP-Coloring of Cartesian Products with Complete Bipartite Graphs
Hemanshu Kaul, Jeffrey A. Mudrock, Emily A. Psyhogios +3
arXiv27 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{ma2026wellcovered,
  title = {{Well-Covered Powers: Cartesian Products and Cayley Graphs}},
  author = {Haobo Ma and Thanh Vu and Wenlin Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.03956},
  eprint = {2611.03956},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03956},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Well-Covered Powers: Cartesian Products and Cayley Graphs
AU  - Haobo Ma
AU  - Thanh Vu
AU  - Wenlin Zhang
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2611.03956
UR  - https://arxiv.org/abs/2611.03956
AB  - We study graphs whose powers are well-covered, with an emphasis on Cartesian products and Cayley graphs. We first establish necessary conditions and sufficient criteria for Cartesian products, provide examples showing that a factor need not be well-covered and that two noncomplete factors can have the well-covered powers property, and classify several structured product families. In particular, we construct graphs satisfying the well-covered powers property for arbitrarily large diameters. We then show that the Cartesian square of a connected abelian Cayley graph is well-covered exactly when the graph is complete. We classify the well-covered-power graphs among connected circulant graphs of degree at most four. For Cartesian products of any number of complete graphs, we also prove that the recursive alphabet-size inequalities in the final conjecture are sufficient for all powers to be well-covered, prove partial converses for arbitrarily many factors, and give explicit obstructions for every binary prefix followed by one complete factor.
ER  -

Abstract

Related

Cite