Advances and Applications in Discrete Mathematics
Volume 23, Issue 2, Pages 85 - 101
(March 2020) http://dx.doi.org/10.17654/DM023020085 |
|
STRONG k-GEODETIC PROBLEM IN GRAPHS: COMPUTATIONAL COMPLEXITY AND SOME RESULTS
D. Antony Xavier, Bino Infanta L. G. and Santiagu Theresal
|
Abstract: Let be a graph. A set is a strong k-geodetic set if each vertex lies on a fixed k-geodesic between some pair of vertices of S. The minimum cardinality of a strong k-geodetic set is the strong k-geodetic number of G and is denoted by In this paper we have derived some results on the strong k-geodetic number. Also we prove that the strong k-geodetic problem is NP-complete for general graphs, bipartite graphs, chordal graphs and chordal bipartite graphs. |
Keywords and phrases: geodetic set, strong geodetic set, k-geodetic set, strong k-geodetic set.
|
|
Number of Downloads: 206 | Number of Views: 641 |
|