Metraipolis › archive › dc_57185a28efee

Kemeny's constant and Braess cliques in graphs — arXiv:2608.04150

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.04150
License (as archived)
CC0-1.0
Archived
2026-10-31T11:45:56.626Z
SHA-256 of the archived text
c3ee37e011b085646d574ce7478067dc21810b90b0dcc5775346488bb6803d68
Stable URL of this page
https://metraipolis.com/documento/dc_57185a28efee

How to cite

Kemeny's constant and Braess cliques in graphs — arXiv:2608.04150 — arXiv (en), https://arxiv.org/abs/2608.04150 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_57185a28efee (Metraipolis archive dc_57185a28efee, sha256 c3ee37e011b085646d574ce7478067dc21810b90b0dcc5775346488bb6803d68)
BibTeX
@misc{dc57185a28efee,
  title = {Kemeny's constant and Braess cliques in graphs — arXiv:2608.04150},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.04150},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_57185a28efee; sha256 c3ee37e011b085646d574ce7478067dc21810b90b0dcc5775346488bb6803d68},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.04150. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Kemeny's constant is used as a measure of the average travel time on a graph. Braess' paradox for graphs is the observation that in some graphs, when an edge is added, Kemeny's constant increases. We introduce the notion of a Braess clique $K_\ell$, a clique that when inserted into a graph on an independent set of $\ell$ vertices, will create an increase in Kemeny's constant. In this context, a Braess edge is a Braess $K_2$. We provide examples of graphs that have a Braess $K_\ell$ for $\ell\geq 3$. We observe that almost every connected planar labelled graph has a Braess $K_\ell$ for each $\ell\geq 3$. We also explore the relationship between Braess edges and Braess cliques in graphs.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-06 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Rings and Algebras (math.RA).
Pagina del lavoro: https://arxiv.org/abs/2608.04150 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T11:35:10.097Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).