The Edge-to-Vertex Geodetic Number of a Graph
A. P. Santhakumaran · Journal of Advanced Mathematics and Applications · 2015
Let G D .V; E/ be a connected graph with at least three vertices.For vertices u and v in G; the distance d.u; v/ is the length of a shortest u v path in G: A u v path of length d.u; v/ is called a u v geodesic.For subsets A and B of V; the distance d.A; B/; is defined as d.A; B/ D mi n fd.x; y/ W x 2 A; y 2 Bg.A u v path of length d.A; B/ is called an A B geodesic joining the sets A; B Â V; where u 2 A and v 2 B: A vertex x is said to lie on an A B geodesic if x is a vertex of an A B geodesic.A set S Â E is called an edge-to-vertex geodetic set if every vertex of G is either incident with an edge of S or lies on a geodesic joining a pair of edges of S: The edge-to-vertex geodetic number g ev .G/ of G is the minimum cardinality of its edge-to-vertex geodetic sets and any edge-to-vertex geodetic set of cardinality g ev .G/ is an edge-to-vertex geodetic basis of G: Any edge-to-vertex geodetic basis is also called a g ev -set of G: It is shown that if G is a connected graph of size q and diameter d; then g ev .G/ Ä q d C 2: It is proved that, for a tree T with q 2; g ev .T / D q d C 2 if and only if T is a caterpillar.For positive integers r; d and l 2 with r Ä d Ä 2r; there exists a connected graph G with rad G D r; d iam G D d and g ev .G/ D l: Also graphs G for which g ev .G/ D q; q 1 or q 2 are characterized.