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

preprint2012arXivOpen access

Abstract

A set of vertices SS of a graph GG is a geodetic set of GG if every vertex v∉Sv\not\in S lies on a shortest path between two vertices of SS. The minimum cardinality of a geodetic set of GG is the geodetic number of GG and it is denoted by g(G)g(G). A Steiner set of GG is a set of vertices WW of GG such that every vertex of GG belongs to the set of vertices of a connected subgraph of minimum size containing the vertices of WW. The minimum cardinality of a Steiner set of GG is the Steiner number of GG and it is denoted by s(G)s(G). Let GG and HH be two graphs and let nn be the order of GG. The corona product G⊙HG\odot H is defined as the graph obtained from GG and HH by taking one copy of GG and nn copies of HH and joining by an edge each vertex from the ithi^{th}-copy of HH with the ithi^{th}-vertex of GG. We study the geodetic number and the Steiner number of corona product graphs. We show that if GG is a connected graph of order n≥2n\ge 2 and HH is a non complete graph, then g(G⊙H)≤s(G⊙H)g(G\odot H)\le s(G\odot H), which partially solve the open problem presented in [\emph{Discrete Mathematics} \textbf{280} (2004) 259--263] related to characterize families of graphs GG satisfying that g(G)≤s(G)g(G)\le s(G).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.