
RESEARCH ARTICLE
The detour hull number of a graph
A. P. Santhakumaran^{a}, S. V. Ullas Chandran^{b} ^{a} Department of Mathematics, Hindustan University, Hindustan Institute of Technology and Science, Chennai603 103, India
^{b} Department of Mathematics, Amrita Vishwa Vidyapeetham University, Amritapuri Campus, Kollam690 525, India
Abstract:
For vertices $u$ and $v$ in a connected graph $G=(V, E)$, the set $I_D[u,v]$ consists of all those vertices lying on a $uv$ longest path in $G$. Given a set $S$ of vertices of $G$, the union of all sets $I_D[u,v]$ for $u,v\in S$, is denoted by $I_D[S]$. A set $S$ is a detour convex set if $I_D[S]=S$. The detour convex hull $[S]_D$ of $S$ in $G$ is the smallest detour convex set containing $S$. The detour hull number $d_h(G)$ is the minimum cardinality among the subsets $S$ of $V$ with $[S]_D=V$. A set $S$ of vertices is called a detour set if $I_D[S]=V$. The minimum cardinality of a detour set is the detour number $dn(G)$ of $G$. A vertex $x$ in $G$ is a detour extreme vertex if it is an initial or terminal vertex of any detour containing $x$. Certain general properties of these concepts are studied. It is shown that for each pair of positive integers $r$ and $s$, there is a connected graph $G$ with $r$ detour extreme vertices, each of degree $s$. Also, it is proved that every two integers $a$ and $b$ with $2\leq a\leq b$ are realizable as the detour hull number and the detour number respectively, of some graph. For each triple $D,k$ and $n$ of positive integers with $2\leq k\leq nD+1$ and $D\geq 2$, there is a connected graph of order $n$, detour diameter $D$ and detour hull number $k$. Bounds for the detour hull number of a graph are obtained. It is proved that $dn(G)=dh(G)$ for a connected graph $G$ with detour diameter at most $4$. Also, it is proved that for positive integers $a,b$ and $k\geq 2$ with $a< b\leq 2a$, there exists a connected graph $G$ with detour radius $a$, detour diameter $b$ and detour hull number $k$. Graphs $G$ for which ${d}_{h}(G)=n1$ or $d_h(G)=n2$ are characterized.
Keywords:
detour, detour convex set, detour number, detour extreme vertex, detour hull number.
Full text:
PDF file (266 kB)
References:
PDF file
HTML file
Bibliographic databases:
MSC: 05C12 Received: 16.03.2011 Revised: 03.01.2012
Language:
Citation:
A. P. Santhakumaran, S. V. Ullas Chandran, “The detour hull number of a graph”, Algebra Discrete Math., 14:2 (2012), 307–322
Citation in format AMSBIB
\Bibitem{SanUll12}
\by A.~P.~Santhakumaran, S.~V.~Ullas Chandran
\paper The detour hull number of a graph
\jour Algebra Discrete Math.
\yr 2012
\vol 14
\issue 2
\pages 307322
\mathnet{http://mi.mathnet.ru/adm101}
\mathscinet{http://www.ams.org/mathscinetgetitem?mr=3099977}
\zmath{https://zbmath.org/?q=an:1255.05066}
Linking options:
http://mi.mathnet.ru/eng/adm101 http://mi.mathnet.ru/eng/adm/v14/i2/p307
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles

Number of views: 
This page:  147  Full text:  72  References:  20  First page:  1 
