{"id":"arxiv/2603.04706","url":"https://arxiv.org/abs/2603.04706","tags":["math.CO"],"score":0,"title":"Counting $P_3$-convex sets in graphs","domain":"math.CO","source":"arxiv","authors":["Mitre C. Dourado","Luciano N. Grippo","Min Chih Lin","Fábio Protti"],"reviews":0,"subject":"math.CO","summary":"We study the $P_3$-convexity, the path convexity generated by all three-vertex paths, and focus on the problem of counting the $P_3$-convex vertex sets of a graph $G$, denoted by $\\noc(G)$. First, we settle the associated extremal question: we characterize the $n$-vertex graphs maximizing $\\noc(G)$ among all graphs and determine the connected extremal graphs. Next, we investigate computational complexity and show that counting $P_3$-convex sets is $\\#\\mathsf{P}$-complete already on split graphs, even under additional structural restrictions. On the positive side, we identify two tractable…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-05","reactions":{}}