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).