The number of connected sets in Apollonian networks.

A vertex subset in a graph that induces a connected subgraph is referred to as a connected set. Counting the number of connected sets N (G) in a graph G is generally a #P-complete problem. In our recent work [Graphs Combin. (2024)], a linear recursive algorithm was designed to count N (G) in any Apollonian network. In this paper we extend our research by establishing a tight upper bound on N (G) in Apollonian networks with an order of n ≥ 3 , along with a characterization of the graphs that reach this upper bound. Our approach primarily utilizes linear programming techniques. Moreover, we propose a conjecture regarding the lower bound on N (G) in Apollonian networks with a given order. • Establishing a tight upper bound on the number of connected sets in Apollonian networks of a fixed order. • Using linear programming techniques to gain insights into the connectivity properties of Apollonian networks. • Proposing a conjecture concerning the lower bound on the number of connected sets in Apollonian networks. [ABSTRACT FROM AUTHOR]