Kemeny's constant and Braess cliques in graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.04150
curl -X POST /api/v1/records/arxiv/2608.04150/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.04150/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'