Counting $P_3$-convex sets in graphs

Mitre C. Dourado; Luciano N. Grippo; Min Chih Lin; Fábio Protti

Counting $P_3$-convex sets in graphs

Mitre C. Dourado, Luciano N. Grippo, Min Chih Lin, Fábio Protti

arXivarxiv/2603.04706Mar 5, 2026math.COscore 0

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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2603.04706
curl -X POST /api/v1/records/arxiv/2603.04706/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.04706/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'