2011/11/15 by Ismael G. Yero, Yero, Ismael G., Juan A. Rodríguez‐Velázquez +1
Computer Science · #05C12 #05C69 #05C76 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1111.3512
openalex publication_date 2011/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set of vertices S of a graph G is a geodetic set of G if every vertex\nv not\∈ S lies on a shortest path between two vertices of S. The minimum\ncardinality of a geodetic set of G is the geodetic number of G and it is\ndenoted by g(G). A Steiner set of G is a set of vertices W of G such\nthat every vertex of G belongs to the set of vertices of a connected subgraph\nof minimum size containing the vertices of W. The minimum cardinality of a\nSteiner set of G is the Steiner number of G and it is denoted by s(G).\nLet G and H be two graphs and let n be the order of G. The corona\nproduct G odot H is defined as the graph obtained from G and H by taking\none copy of G and n copies of H and joining by an edge each vertex from\nthe ith-copy of H with the ith-vertex of G. We study the geodetic\nnumber and the Steiner number of corona product graphs. We show that if G is\na connected graph of order n\≥ 2 and H is a non complete graph, then\ng(G odot H)\≤ s(G odot H), which partially solve the open problem presented\nin [\Discrete Mathematics \280 (2004) 259--263] related to\ncharacterize families of graphs G satisfying that g(G)\≤ s(G).\n