Analogies between the geodetic number and the Steiner number of some classes of graphs

Identifier:  imarina:5128966

Handle: https://hdl.handle.net/20.500.11797/imarina5128966

Authors:  Yero, Ismael G; Rodriguez-Velazquez, Juan A

Abstract:
A set of vertices S of a graph G is a geodetic set of G if every vertex v  S lies on a shortest path between two vertices of S. The minimum cardinality of a geodetic set of G is the geodetic number of G and it is denoted by 1(G). A Steiner set of G is a set of vertices W of G such that every vertex of G belongs to the set of vertices of a connected subgraph of minimum size containing the vertices of W. The minimum cardinality of a Steiner set of G is the Steiner number of G and it is denoted by s(G). Let G and H be two graphs and let n be the order of G. The corona product G ¿ H is defined as the graph obtained from G and H by taking one copy of G and n copies of H and joining by an edge each vertex from the ith-copy of H to the ith-vertex of G. We study the geodetic number and the Steiner number of corona product graphs. We show that if G is a connected graph of order n ≥ 2 and H is a non complete graph, then g(G ¿ H) ≤ s(G ¿ H), which partially solve the open problem presented in [Discrete Mathematics 280 (2004) 259-263] related to characterize families of graphs G satisfying that g(G) ≤ s(G).