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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-05 Page: https://delphi.science/r/arxiv/2603.04706 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…