Abstract

Let G be a finite, simple graph and let S (G) denote the subdivision graph obtained by inserting one new vertex into each edge of G. A hub set of a graph H is a vertex set D⊆V(H) such that every two non-adjacent vertices of V(H)-D are connected by a path whose internal vertices all belong to D. The minimum cardinality of a hub set of H is the hub number h(H). In this paper, we study the hub number of subdivision graphs. We first record basic structural observations for hub sets and then obtain exact formulas for subdivisions of trees, paths, cycles, and stars. We also derive general bounds for h(S(G)) in terms of the order and size of G, give Nordhaus–Gaddum-type inequalities for subdivision graphs and their complements under natural connectedness assumptions, and discuss how complete and complete bipartite source graphs lead to extremal subgraph problems. Several examples are included to illustrate the results.