The total double geodetic number of a graph

Keywords: Geodetic number, Double geodetic number, Connected double geodetic number, Total double geodetic number

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 set of cardinality dg(G) is called a dg-set of G. A connected double geodetic set of G is a double geodetic set S such that the subgraph G[S] induced by S is connected. The mínimum cardinality of a connected double geodetic set of G is the connected double geodetic number of G and is denoted by dgc(G). A connected double geodetic set of cardinality dgc(G) is called a dgc-set of G. A total double geodetic set of a graph G is a double geodetic set S such that the subgraph G[S] induced by S has no isolated vertices. The minimum cardinality of a total double geodetic set of G is the total double geodetic number of G and is denoted by dgt(G). For positive integers r, d and k ≥ 4 with r ≤ d ≤ 2r, there exists a connected graph G with rad G = r, diam G = d and dgt(G) = k. It is shown that if n, a, b are positive integers such that 4 ≤ a ≤ b ≤ n, then there exists a connected graph G of order n with dgt(G) = a and dgc(G) = b. Also, for integers a, b with 4 ≤ a ≤ b and b ≤ 2a, there exists a connected graph G such that dg(G) = a and dgt(G) = b.

Author Biographies

A. P. Santhakumaran, Hindustan Institute of Technology and Science.
Dept. of Mathematics.
T. Jebaraj, Malankara Catholic College.
Dept. of Mathematics.

References

F. Buckley and F. Harary, Distance in graphs, Redwood City, CA: Addison-Wesley, 1990.

G. Chartrand, F. Harary and P. Zhang, “On the geodetic number of a graph”, Networks, vol. 39, no. 1, pp. 1-6, Nov. 2002, doi: 10.1002/net.10007.

G. Chartrand, F. Harary , H. C. Swart and P. Zhang, “Geodomination in graphs”, Bulletin of the ICA, vol. 31, pp. 51-59, 2001.

F. Harary, Graph theory, Reading, MA: Addision-Wesley, 1969.

F. Harary, E. Loukakis, and C. Tsouros, “The geodetic number of a graph”, Mathematical and computer modeling, vol. 17, no. 11, pp. 89-95, Jun. 1993, doi: 10.1016/0895-7177(93)90259-2.

R. Muntean and P. Zhang, “On geodomonation in graphs”, Congressus numerantium, vol. 143, pp. 161-174, 2000.

P. A. Ostrand, “Graphs with specified radius and diameter”, Discrete mathematics, vol. 4, no. 1, pp. 71-75, 1973, doi: 10.1016/0012-365X(73)90116-7.

A. P. Santhakumaran and T. Jebaraj, “Double geodetic number of a graph”, Discussiones mathematicae graph theory, vol. 32, no. 1, pp. 109-119, 2012. [On line]. Available: https://bit.ly/2Ocj0uW

A. P. Santhakumaran and T. Jebaraj, “The connected double geodetic number of a graph”, (communicated).

Published
2020-02-04
How to Cite
[1]
A. P. Santhakumaran and T. Jebaraj, “The total double geodetic number of a graph”, Proyecciones (Antofagasta, On line), vol. 39, no. 1, pp. 167-178, Feb. 2020.
Section
Artículos