Bounds on the P 3 -Carathéodory number

The P 3 -convex hull H ( S ) of a set S ⊆ V ( G ) is the smallest set containing S such that, for every pair of vertices u , v ∈ S , all vertices on any path of three vertices between them are also included in the set. The P 3 -Carathéodory number c ( G ) is the smallest integer c such that, for every set S and every v ∈ H ( S ) , there exists a subset S ′ ⊆ S of size at most c , such that v ∈ H ( S ′ ) . In 2014, Barbosa et al. proved that, for a given graph G and a positive integer k , the problem of deciding whether c ( G ) ≥ k is NP-complete. In this paper, we present upper bounds on the P 3 -Carathéodory number of graphs with diameter two, and establish that: c ( G ) = 2 for graphs with cut-vertex; c ( G ) ≤ 5 + 8 Δ − 15 2 for biconnected graphs; and c ( G ) ≤ 4 for biconnected C 6 -free graphs. Moreover, we show a polynomial-time algorithm for biconnected diameter-two graphs, that constructs a special path from which we compute an upper bound for the Carathéodory number. These results also provide supporting evidence for the conjecture that the P 3 -Carathéodory number is bounded by a constant in graphs with a limited diameter.