Counting P_3-Convex Sets in Graphs

The convexity P_3 is generated by the set of all three-vertex paths of a graph. In this work, we consider the P_3-convex set count problem of a graph G. We proved that this problem is #P-complete, even for split graphs. We investigate the problem of maximizing the number of P_3-convex sets in graphs with n vertices, characterizing the extreme graphs (connected or not) that reach the maximum count, equal to 2^n. By restricting the scope to connected graphs, we proved that the star K_{1,n−1} maximizes this count by setting the upper bound of 2^{n−1} + n, which is also achieved by the paths P_4 and P_5. In addition to characterizing the extreme structures, we describe a dynamic linear time programming algorithm for trees, demonstrating that trees with n vertices naturally have more P_3-convex sets than graphs with n vertices containing cycles. We also compared the exponential growth of the count in stars versus paths.