The detour hull number of a graph

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

Algebra and discrete mathematics, Tome 14 (2012) no. 2, pp. 307-322.

Résumé

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.

Détail

Keywords: detour number, detour hull number.
Mots-clés : detour, detour convex set, detour extreme vertex

Bibliographie

[1] F. Buckley, F. Harary, Distance in Graphs, Addison-Wesley, Reading, MA, 1990 | MR

[2] G. Chartrand, H. Escuadro, P. Zhang, “Detour Distance in Graphs”, J. Combin. Math. Combin. Comput., 53 (2005), 75–94 | MR

[3] G. Chartrand, F. Harary, P. Zhang, “On the hull number of a graph”, Ars Combin., 57 (2000), 129–138 | MR

[4] G. Chartrand, P. Zhang, “Extreme geodesic graphs”, Czechoslovak Mathematical Journal, 52:127 (2002), 771–780 | DOI | MR

[5] G. Chartrand, F. Harary, P. Zhang, “On the Geodetic Number of a Graph”, Networks, 39:1 (2002), 1–6 | DOI | MR

[6] G. Chartrand, J. F. Fink, P. Zhang, “On the hull Number of an oriented graph”, Int. J. Math. Math Sci., 36 (2003), 2265–2275 | DOI | MR

[7] G. Chartrand, G. L. Johns, P. Zhang, “Detour Number of a Graph”, Util. Math., 64 (2003), 97–113 | MR

[8] G. Chartrand, L. Nebesky, P. Zhang, A Survey of Hamilton Colorings of Graphs, Preprint | MR

[9] G. Chartrand, P. Zhang, Introduction to Graph Theory, Tata McGraw-Hill Edition, New Delhi, 2006

[10] M. Grötschel, “Hypohamiltonian facets of the symmetric travelling salesman polytope”, Zeitschrift für Angewandte Mathematik und Mechanik, 58 (1977), 469–471 | MR

[11] M. G. Everett, S. B. Seidman, “The hull number of a graph”, Discrete Math., 57 (1985), 217–223 | DOI | MR

[12] W. Hale, “Frequency Assignment; Theory and Applications”, Proc. IEEE, 68 (1980), 1497–1514 | DOI

[13] T. Mansour, M. Schork, “Wiener, hyper-Wiener detour and hyper-detour indices of bridge and chain graphs”, J. Math. Chem., 47 (2010), 72–98 | DOI | MR

[14] A. P. Santhakumaran, S. Athisayanathan, “Connected detour number of a graph”, J. Combin. Math. Combin. Comput., 69 (2009), 205–218 | MR