Article ID Journal Published Year Pages File Type
418825 Discrete Applied Mathematics 2009 10 Pages PDF
Abstract

For a connected graph GG of order p≥2p≥2, a set S⊆V(G)S⊆V(G) is a geodetic set of GG if each vertex v∈V(G)v∈V(G) lies on an x–yx–y geodesic for some elements xx and yy in SS. The minimum cardinality of a geodetic set of GG is defined as the geodetic number of GG, denoted by g(G)g(G). A geodetic set of cardinality g(G)g(G) is called a gg-set of GG. A connected geodetic set of GG is a geodetic set SS such that the subgraph G[S]G[S] induced by SS is connected. The minimum cardinality of a connected geodetic set of GG is the connected geodetic number of GG and is denoted by gc(G)gc(G). A connected geodetic set of cardinality gc(G)gc(G) is called a gcgc-set of GG. A connected geodetic set SS in a connected graph GG is called a minimal connected geodetic set if no proper subset of SS is a connected geodetic set of GG. The upper connected geodetic number gc+(G) is the maximum cardinality of a minimal connected geodetic set of GG. We determine bounds for gc+(G) and determine the same for some special classes of graphs. For positive integers r,dr,d and n≥d+1n≥d+1 with r≤d≤2rr≤d≤2r, there exists a connected graph GG with radG=r, diamG=d and gc+(G)=n. Also, for any positive integers 2≤a

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,