Double geodetic number of a graph

A.P. Santhakumaran; T. Jebaraj

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 1, page 109-119
  • ISSN: 2083-5892

Abstract

top
For a connected graph G of order n, a set S of vertices is called a double geodetic set of G if for each pair of vertices x,y in G there exist vertices u,v ∈ S such that x,y ∈ I[u,v]. The double geodetic number dg(G) is the minimum cardinality of a double geodetic set. Any double godetic of cardinality dg(G) is called dg-set of G. The double geodetic numbers of certain standard graphs are obtained. It is shown that for positive integers r,d such that r < d ≤ 2r and 3 ≤ a ≤ b there exists a connected graph G with rad G = r, diam G = d, g(G) = a and dg(G) = b. Also, it is proved that for integers n, d ≥ 2 and l such that 3 ≤ k ≤ l ≤ n and n-d-l+1 ≥ 0, there exists a graph G of order n diameter d, g(G) = k and dg(G) = l.

How to cite

top

A.P. Santhakumaran, and T. Jebaraj. "Double geodetic number of a graph." Discussiones Mathematicae Graph Theory 32.1 (2012): 109-119. <http://eudml.org/doc/270828>.

@article{A2012,
abstract = {For a connected graph G of order n, a set S of vertices is called a double geodetic set of G if for each pair of vertices x,y in G there exist vertices u,v ∈ S such that x,y ∈ I[u,v]. The double geodetic number dg(G) is the minimum cardinality of a double geodetic set. Any double godetic of cardinality dg(G) is called dg-set of G. The double geodetic numbers of certain standard graphs are obtained. It is shown that for positive integers r,d such that r < d ≤ 2r and 3 ≤ a ≤ b there exists a connected graph G with rad G = r, diam G = d, g(G) = a and dg(G) = b. Also, it is proved that for integers n, d ≥ 2 and l such that 3 ≤ k ≤ l ≤ n and n-d-l+1 ≥ 0, there exists a graph G of order n diameter d, g(G) = k and dg(G) = l.},
author = {A.P. Santhakumaran, T. Jebaraj},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {geodetic number; weak-extreme vertex; double geodetic set; double geodetic number},
language = {eng},
number = {1},
pages = {109-119},
title = {Double geodetic number of a graph},
url = {http://eudml.org/doc/270828},
volume = {32},
year = {2012},
}

TY - JOUR
AU - A.P. Santhakumaran
AU - T. Jebaraj
TI - Double geodetic number of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 1
SP - 109
EP - 119
AB - For a connected graph G of order n, a set S of vertices is called a double geodetic set of G if for each pair of vertices x,y in G there exist vertices u,v ∈ S such that x,y ∈ I[u,v]. The double geodetic number dg(G) is the minimum cardinality of a double geodetic set. Any double godetic of cardinality dg(G) is called dg-set of G. The double geodetic numbers of certain standard graphs are obtained. It is shown that for positive integers r,d such that r < d ≤ 2r and 3 ≤ a ≤ b there exists a connected graph G with rad G = r, diam G = d, g(G) = a and dg(G) = b. Also, it is proved that for integers n, d ≥ 2 and l such that 3 ≤ k ≤ l ≤ n and n-d-l+1 ≥ 0, there exists a graph G of order n diameter d, g(G) = k and dg(G) = l.
LA - eng
KW - geodetic number; weak-extreme vertex; double geodetic set; double geodetic number
UR - http://eudml.org/doc/270828
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, F. Harary and P. Zhang, On the geodetic number of a graph, Networks 39 (2002) 1-6, doi: 10.1002/net.10007. Zbl0987.05047
  3. [3] G. Chartrand, F. Harary, H.C. Swart and P. Zhang, Geodomination in graphs, Bulletin ICA 31 (2001) 51-59. Zbl0969.05048
  4. [4] F. Harary, Graph Theory (Addision-Wesely, 1969). 
  5. [5] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph, Math. Comput. Modeling 17 (1993) 89-95, doi: 10.1016/0895-7177(93)90259-2. Zbl0825.68490
  6. [6] R. Muntean and P. Zhang, On geodomonation in graphs, Congr. Numer. 143 (2000) 161-174. Zbl0969.05047
  7. [7] P.A. Ostrand, Graphs with specified radius and diameter, Discrete Math. 4 (1973) 71-75, doi: 10.1016/0012-365X(73)90116-7. Zbl0265.05123

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.