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

Abstract

top
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 ] D x is the smallest x-detour convex set containing S. A set S is an x-detour hull set if [ S ] D x = 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.

How to cite

top

A.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. [1] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Reading MA, 1990). Zbl0688.05017
  2. [2] G. Chartrand, H. Escuadro and P. Zhang, Detour distance in graphs, J. Combin. Math. Combin. Comput. 53 (2005) 75-94. Zbl1074.05029
  3. [3] G. Chartrand, G.L. Johns and P. Zhang, Detour number of a graph, Util. Math. 64 (2003) 97-113. Zbl1033.05032
  4. [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. [5] G. Chartrand, L. Nebesky and P. Zhang, A survey of Hamilton colorings of graphs, preprint. Zbl1064.05054
  6. [6] G. Chartrand and P. Zhang, Introduction to Graph Theory (Tata McGraw- Hill Edition, New Delhi, 2006). 
  7. [7] W. Hale, Frequency Assignment, in: Theory and Applications, Proc. IEEE 68 (1980) 1497-1514, doi: 10.1109/PROC.1980.11899. 
  8. [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. [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. [10] A.P. Santhakumaran and S.V. Ullas Chandran, The detour hull number of a graph, communicated. Zbl1293.05090

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.