The total double geodetic number of a graph
DOI:
https://doi.org/10.22199/issn.0717-6279-2020-01-0011Keywords:
Geodetic number, Double geodetic number, Connected double geodetic number, Total double geodetic numberAbstract
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.
Downloads
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).
Downloads
Published
Issue
Section
License
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.