Search

For a connected graph G(V,E), let S ⊆ V(G) be a minimum strong geodetic set of G then a non-extreme vertex v ∈ S is said to be S-extreme vertex if v is not geodominated by any pair of vertices of G. A strong geodetic set S of vertices in a connected graph G is an strong open geodetic set if for each vertex v ∈ G, either v is a S-extreme vertex of G and v ∈ S or v is an internal vertex of an x — y geodesic for some x,y ∈ S. A strong open geodetic set of minimum cardinality is a minimum strong open geodetic set and this cardinality is the strong open geodetic number of a graph G, denoted by sog(G). In this paper we have discussed about some results related to open geodetic sets. Also, mainly we have the complexity property of strong open geodetic set problem for general graphs, chordal graphs, chordal bipartite graphs. Further few general results and some bounds are given to the strong open geodetic number of some graphs.

Let G = (V, E) be a graph. A vertex v is k–geodominated by a pair x,y ⊆ V(G), if v lies on an x – y geodesic of G of length exactly k. A set S ⊆ V(G) is a strong (k, r)geodetic set if each vertex v ∈ G/S lies on at least r distinct fixed k–geodesics between the pair of vertices in S. The minimum cardinality of the strong (k, r) geodetic set is a strong (k, r) geodetic number and is denoted by sg(k,r)(G). In this paper we prove that the strong (k, r) geodetic set is NP–complete for general graphs, bipartite graphs, chordal graphs and chordal bipartite graphs. Also we derived some results on strong (2,2) geodetic number.

For a graph G(V(G),E(G)), the set Z ⊆ V(G) is called a geodetic propagation set if Z is both a geodetic set as well as a propagating set. The cardinality of the minimum geodetic propagation set is called the geodetic propagation number. Few general results and also the computational complexity part of this concept for general,bipartite and chordal graphs are derived.

Geodetic number of a graph is one of the widely studied graph theoretic parameters concerning geodesic convexity in graphs. In this paper, we introduce a variant of this parameter namely, doubly geodetic number of a graph. For a connected graph G, a setSof vertices of Gis called a doubly geodetic set ofGif each vertex inV − Slies on atleast two distinct geodesics of vertices in S.The doubly geodetic numberd g G of G is the minimum cardinality of a doubly geodetic set. Any doubly geodetic set of cardinality d g G is called d g-set of G. In this paper, the doubly geodetic number of certain standard graphs is determined.

In this paper, we propose a new graph namely Sierpi_nski Gasket Rhombus SRn based on triangular graph like Sierpi_nski Gasket graph. Sierpi_nski Gasket Rhombus SRn is obtained by identifying two copies of Sierpi_nski Gasket graph along their side edges. Further we study some basic properties of Sierpi_nski Gasket Rhombus SRn and find hamiltonicity, pancyclicity and chromatic number of SRn.