|
Algebra and Discrete Mathematics, 2012, Volume 14, Issue 2, Pages 307–322
(Mi adm101)
|
|
|
|
RESEARCH ARTICLE
The detour hull number of a graph
A. P. Santhakumarana, S. V. Ullas Chandranb a Department of Mathematics, Hindustan University, Hindustan Institute of Technology and Science, Chennai-603 103, India
b Department of Mathematics, Amrita Vishwa Vidyapeetham University, Amritapuri Campus, Kollam-690 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 $u-v$ 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 n-D+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)=n-1$ or $d_h(G)=n-2$ are characterized.
Keywords:
detour, detour convex set, detour number, detour extreme vertex, detour hull number.
Received: 16.03.2011 Revised: 03.01.2012
Citation:
A. P. Santhakumaran, S. V. Ullas Chandran, “The detour hull number of a graph”, Algebra Discrete Math., 14:2 (2012), 307–322
Linking options:
https://www.mathnet.ru/eng/adm101 https://www.mathnet.ru/eng/adm/v14/i2/p307
|
Statistics & downloads: |
Abstract page: | 219 | Full-text PDF : | 109 | References: | 29 | First page: | 1 |
|