کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649737 | 1342465 | 2009 | 6 صفحه PDF | دانلود رایگان |
For an oriented graph DD, let ID[u,v]ID[u,v] denote the set of all vertices lying on a u–vu–v geodesic or a v–uv–u geodesic. For S⊆V(D)S⊆V(D), let ID[S]ID[S] denote the union of all ID[u,v]ID[u,v] for all u,v∈Su,v∈S. Let [S]D[S]D denote the smallest convex set containing SS. The geodetic number g(D)g(D) of an oriented graph DD is the minimum cardinality of a set SS with ID[S]=V(D)ID[S]=V(D) and the hull number h(D)h(D) of an oriented graph DD is the minimum cardinality of a set SS with [S]D=V(D)[S]D=V(D). For a connected graph GG, let O(G)O(G) be the set of all orientations of GG, define g−(G)=min{g(D):D∈O(G)}g−(G)=min{g(D):D∈O(G)}, g+(G)=max{g(D):D∈O(G)}g+(G)=max{g(D):D∈O(G)}, h−(G)=min{h(D):D∈O(G)}h−(G)=min{h(D):D∈O(G)}, and h+(G)=max{h(D):D∈O(G)}h+(G)=max{h(D):D∈O(G)}. By the above definitions, h−(G)≤g−(G)h−(G)≤g−(G) and h+(G)≤g+(G)h+(G)≤g+(G). In the paper, we prove that g−(G)
Journal: Discrete Mathematics - Volume 309, Issue 8, 28 April 2009, Pages 2134–2139