The connected forcing connected vertex detour number of a graph

A.P. Santhakumaran; P. Titus

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 3, page 461-473
  • ISSN: 2083-5892

Abstract

top
For any vertex x in a connected graph G of order p ≥ 2, a set S of vertices of V is an x-detour set of G if each vertex v in G lies on an x-y detour for some element y in S. A connected x-detour set of G is an x-detour set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected x-detour set of G is the connected x-detour number of G and is denoted by cdₓ(G). For a minimum connected x-detour set Sₓ of G, a subset T ⊆ Sₓ is called a connected x-forcing subset for Sₓ if the induced subgraph G[T] is connected and Sₓ is the unique minimum connected x-detour set containing T. A connected x-forcing subset for Sₓ of minimum cardinality is a minimum connected x-forcing subset of Sₓ. The connected forcing connected x-detour number of Sₓ, denoted by c f c d x ( S ₓ ) , is the cardinality of a minimum connected x-forcing subset for Sₓ. The connected forcing connected x-detour number of G is c f c d x ( G ) = m i n c f c d x ( S ₓ ) , where the minimum is taken over all minimum connected x-detour sets Sₓ in G. Certain general properties satisfied by connected x-forcing sets are studied. The connected forcing connected vertex detour numbers of some standard graphs are determined. It is shown that for positive integers a, b, c and d with 2 ≤ a < b ≤ c ≤ d, there exists a connected graph G such that the forcing connected x-detour number is a, connected forcing connected x-detour number is b, connected x-detour number is c and upper connected x-detour number is d, where x is a vertex of G.

How to cite

top

A.P. Santhakumaran, and P. Titus. "The connected forcing connected vertex detour number of a graph." Discussiones Mathematicae Graph Theory 31.3 (2011): 461-473. <http://eudml.org/doc/271053>.

@article{A2011,
abstract = {For any vertex x in a connected graph G of order p ≥ 2, a set S of vertices of V is an x-detour set of G if each vertex v in G lies on an x-y detour for some element y in S. A connected x-detour set of G is an x-detour set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected x-detour set of G is the connected x-detour number of G and is denoted by cdₓ(G). For a minimum connected x-detour set Sₓ of G, a subset T ⊆ Sₓ is called a connected x-forcing subset for Sₓ if the induced subgraph G[T] is connected and Sₓ is the unique minimum connected x-detour set containing T. A connected x-forcing subset for Sₓ of minimum cardinality is a minimum connected x-forcing subset of Sₓ. The connected forcing connected x-detour number of Sₓ, denoted by $cf_\{cdx\}(Sₓ)$, is the cardinality of a minimum connected x-forcing subset for Sₓ. The connected forcing connected x-detour number of G is $cf_\{cdx\}(G) = mincf_\{cdx\}(Sₓ)$, where the minimum is taken over all minimum connected x-detour sets Sₓ in G. Certain general properties satisfied by connected x-forcing sets are studied. The connected forcing connected vertex detour numbers of some standard graphs are determined. It is shown that for positive integers a, b, c and d with 2 ≤ a < b ≤ c ≤ d, there exists a connected graph G such that the forcing connected x-detour number is a, connected forcing connected x-detour number is b, connected x-detour number is c and upper connected x-detour number is d, where x is a vertex of G.},
author = {A.P. Santhakumaran, P. Titus},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {vertex detour number; connected vertex detour number; upper connected vertex detour number; forcing connected vertex detour number; connected forcing connected vertex detour number},
language = {eng},
number = {3},
pages = {461-473},
title = {The connected forcing connected vertex detour number of a graph},
url = {http://eudml.org/doc/271053},
volume = {31},
year = {2011},
}

TY - JOUR
AU - A.P. Santhakumaran
AU - P. Titus
TI - The connected forcing connected vertex detour number of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 3
SP - 461
EP - 473
AB - For any vertex x in a connected graph G of order p ≥ 2, a set S of vertices of V is an x-detour set of G if each vertex v in G lies on an x-y detour for some element y in S. A connected x-detour set of G is an x-detour set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected x-detour set of G is the connected x-detour number of G and is denoted by cdₓ(G). For a minimum connected x-detour set Sₓ of G, a subset T ⊆ Sₓ is called a connected x-forcing subset for Sₓ if the induced subgraph G[T] is connected and Sₓ is the unique minimum connected x-detour set containing T. A connected x-forcing subset for Sₓ of minimum cardinality is a minimum connected x-forcing subset of Sₓ. The connected forcing connected x-detour number of Sₓ, denoted by $cf_{cdx}(Sₓ)$, is the cardinality of a minimum connected x-forcing subset for Sₓ. The connected forcing connected x-detour number of G is $cf_{cdx}(G) = mincf_{cdx}(Sₓ)$, where the minimum is taken over all minimum connected x-detour sets Sₓ in G. Certain general properties satisfied by connected x-forcing sets are studied. The connected forcing connected vertex detour numbers of some standard graphs are determined. It is shown that for positive integers a, b, c and d with 2 ≤ a < b ≤ c ≤ d, there exists a connected graph G such that the forcing connected x-detour number is a, connected forcing connected x-detour number is b, connected x-detour number is c and upper connected x-detour number is d, where x is a vertex of G.
LA - eng
KW - vertex detour number; connected vertex detour number; upper connected vertex detour number; forcing connected vertex detour number; connected forcing connected vertex detour number
UR - http://eudml.org/doc/271053
ER -

References

top
  1. [1] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Redwood City, CA, 1990). Zbl0688.05017
  2. [2] G. Chartrand, H. Escuadro and P. Zang, Detour Distance in Graphs, J. Combin. Math. Combin. Comput. 53 (2005) 75-94. Zbl1074.05029
  3. [3] G. Chartrand, F. Harary and P. Zang, On the geodetic number of a graph, Networks 39 (2002) 1-6, doi: 10.1002/net.10007. Zbl0987.05047
  4. [4] G. Chartrand, G.L. Johns and P. Zang, The Detour Number of a Graph, Utilitas Mathematica 64 (2003) 97-113. Zbl1033.05032
  5. [5] G. Chartrand, G.L. Johns and P. Zang, On the Detour Number and Geodetic Number of a Graph, Ars Combinatoria 72 (2004) 3-15. Zbl1073.05022
  6. [6] F. Harary, Graph Theory (Addison-Wesley, 1969). 
  7. [7] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph, Math. Comput. Modeling 17 (1993) 87-95, doi: 10.1016/0895-7177(93)90259-2. Zbl0825.68490
  8. [8] T. Mansour and M. Schork, Wiener, hyper-Wiener detour and hyper-detour indices of bridge and chain graphs, J. Math. Chem. 47 (2010) 72-98, doi: 10.1007/s10910-009-9531-7. Zbl05676518
  9. [9] A.P. Santhakumaran and P. Titus, Vertex Geodomination in Graphs, Bulletin of Kerala Mathematics Association 2 (2005) 45-57. 
  10. [10] A.P. Santhakumaran and P. Titus, On the Vertex Geodomination Number of a Graph, Ars Combinatoria, to appear. Zbl1265.05203
  11. [11] A.P. Santhakumaran and P. Titus, The Vertex Detour Number of a Graph, AKCE International Journal of Graphs and Combinatorics 4 (2007) 99-112. Zbl1144.05028
  12. [12] A.P. Santhakumaran and P. Titus, The Connected Vertex Geodomination Number of a Graph, Journal of Prime Research in Mathematics 5 (2009) 101-114. Zbl1194.05034
  13. [13] A.P. Santhakumaran and P. Titus, The Connected Vertex Detour Number of a Graph, communicated. Zbl1229.05097
  14. [14] A.P. Santhakumaran and P. Titus, The Upper Connected Vertex Detour Number of a Graph, communicated. Zbl1289.05142

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.