# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## The Vertex Detour Hull Number of a Graph

 A.P. Santhakumaran Department of Mathematics St. Xavier's College (Autonomous) Palayamkottai - 627 002, India S.V. Ullas Chandran Department of Mathematics Amrita Vishwa Vidyapeetham UniversityAmritapuri Campus, Clappana Kollam - 690 525, India

## 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), ID[S] = ∪x,y ∈ SID[x,y]. A set S of vertices is a detour convex set if ID[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 ID[y]x, the set of all vertices distinct from x that lie on some x −y detour of G; while for S ⊆ V(G), ID[S]x = ∪y ∈ SID[y]x. For x ∉ S, S is an x-detour convex set if ID[S]x = S. The x-detour convex hull of S, [S]xD is the smallest x-detour convex set containing S. A set S is an x-detour hull set if [S]xD = V(G) −{x} and the minimum cardinality of x-detour hull sets is the x-detour hull number dhx(G) of G. For x ∉ S, S is an x-detour set of G if ID[S]x = V(G) −{x} and the minimum cardinality of x-detour sets is the x-detour number dx(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 dhx(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 dhx(G) = a and the detour eccentricity of x, eD(x) = b. We determine bounds for dhx(G) and characterize graphs G which realize these bounds.

Keywords: detour, detour number, detour hull number, x-detour number, x-detour hull number

2010 Mathematics Subject Classification: 05C12.

## References

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