# The vertex detour hull number of a graph

A.P. Santhakumaran; S.V. Ullas Chandran

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 2, page 321-330
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topA.P. Santhakumaran, and S.V. Ullas Chandran. "The vertex detour hull number of a graph." Discussiones Mathematicae Graph Theory 32.2 (2012): 321-330. <http://eudml.org/doc/270957>.

@article{A2012,

abstract = {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 ID[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.},

author = {A.P. Santhakumaran, S.V. Ullas Chandran},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {detour; detour number; detour hull number; x-detour number; x-detour hull number; -detour number; -detour hull number},

language = {eng},

number = {2},

pages = {321-330},

title = {The vertex detour hull number of a graph},

url = {http://eudml.org/doc/270957},

volume = {32},

year = {2012},

}

TY - JOUR

AU - A.P. Santhakumaran

AU - S.V. Ullas Chandran

TI - The vertex detour hull number of a graph

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 2

SP - 321

EP - 330

AB - 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 ID[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.

LA - eng

KW - detour; detour number; detour hull number; x-detour number; x-detour hull number; -detour number; -detour hull number

UR - http://eudml.org/doc/270957

ER -

## References

top- [1] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Reading MA, 1990). Zbl0688.05017
- [2] G. Chartrand, H. Escuadro and P. Zhang, Detour distance in graphs, J. Combin. Math. Combin. Comput. 53 (2005) 75-94. Zbl1074.05029
- [3] G. Chartrand, G.L. Johns and P. Zhang, Detour number of a graph, Util. Math. 64 (2003) 97-113. Zbl1033.05032
- [4] G. Chartrand, G.L. Johns and P. Zhang, On the detour number and geodetic number of a graph, Ars Combin. 72 (2004) 3-15. Zbl1073.05022
- [5] G. Chartrand, L. Nebesky and P. Zhang, A survey of Hamilton colorings of graphs, preprint. Zbl1064.05054
- [6] G. Chartrand and P. Zhang, Introduction to Graph Theory (Tata McGraw- Hill Edition, New Delhi, 2006).
- [7] W. Hale, Frequency Assignment, in: Theory and Applications, Proc. IEEE 68 (1980) 1497-1514, doi: 10.1109/PROC.1980.11899.
- [8] A.P. Santhakumaran and S. Athisayanathan, Connected detour number of a graph, J. Combin. Math. Combin. Comput. 69 (2009) 205-218. Zbl1200.05072
- [9] A.P. Santhakumaran and P. Titus, The vertex detour number of a graph, AKCE J. Graphs. Combin. 4 (2007) 99-112. Zbl1144.05028
- [10] A.P. Santhakumaran and S.V. Ullas Chandran, The detour hull number of a graph, communicated. Zbl1293.05090

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.