{"id":"arxiv/2608.04150","url":"https://arxiv.org/abs/2608.04150","tags":["math.CO","math.RA"],"score":0,"title":"Kemeny's constant and Braess cliques in graphs","domain":"math.CO","source":"arxiv","authors":["Jane Breen","Emma deBlieck","Kevin N. Vander Meulen"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-04","reactions":{}}