- Tytuł:
- The vertex detour hull number of a graph
- Autorzy:
-
Santhakumaran, A.
Ullas Chandran, S. - Powiązania:
- https://bibliotekanauki.pl/articles/743332.pdf
- Data publikacji:
- 2012
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
detour
detour number
detour hull number
x-detour number
x-detour hull number - Opis:
- For vertices x and y in a connected graph G, the detour distance D(x,y) is the length of a longest x - y path in G. An x - y path of length D(x,y) is an x - y detour. The closed detour interval I_D[x,y] consists of x,y, and all vertices lying on some x -y detour of G; while for S ⊆ V(G), $I_D[S] = ⋃_{x,y ∈ S} I_D[x,y]$. A set S of vertices is a detour convex set if $I_D[S] = S$. The detour convex hull $[S]_D$ is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among subsets S of V(G) with $[S]_D = V(G)$. Let x be any vertex in a connected graph G. For a vertex y in G, denoted by $I_D[y]^x$, the set of all vertices distinct from x that lie on some x - y detour of G; while for S ⊆ V(G), $I_D[S]^x = ⋃_{y ∈ S} I_D[y]^x$. For x ∉ S, S is an x-detour convex set if $I_D[S]^x = S$. The x-detour convex hull of S, $[S]^x_D$ is the smallest x-detour convex set containing S. A set S is an x-detour hull set if $[S]^x_D = V(G) -{x}$ and the minimum cardinality of x-detour hull sets is the x-detour hull number dhₓ(G) of G. For x ∉ S, S is an x-detour set of G if $I_D[S]^x = V(G) - {x}$ and the minimum cardinality of x-detour sets is the x-detour number dₓ(G) of G. Certain general properties of the x-detour hull number of a graph are studied. It is shown that for each pair of positive integers a,b with 2 ≤ a ≤ b+1, there exist a connected graph G and a vertex x such that dh(G) = a and dhₓ(G) = b. It is proved that every two integers a and b with 1 ≤ a ≤ b, are realizable as the x-detour hull number and the x-detour number respectively. Also, it is shown that for integers a,b and n with 1 ≤ a ≤ n -b and b ≥ 3, there exist a connected graph G of order n and a vertex x such that dhₓ(G) = a and the detour eccentricity of x, $e_D(x) = b$. We determine bounds for dhₓ(G) and characterize graphs G which realize these bounds.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2012, 32, 2; 321-330
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł