3 citations · 6 across the 11 of their papers we have counts for
11 papers
Short Cycles Decide P-versus-NPC Status ofHamiltonicity on Bisplit Graphs
Mahendra Kumar R, Renjith P, Aadhavan S +1
A connected graph G is said to be a bisplit graph if the vertex set of G can be partitioned into a stable set and a complete bipartite graph. We establish the following dichotomy w…
On Convexity in Split graphs: Complexity of Steiner tree and Domination
A Mohanapriya, P Renjith, N Sadagopan
Given a graph with a terminal set , the Steiner tree problem (STREE) asks for a set such that the graph induced on is…
Steiner Tree in -star Caterpillar Convex Bipartite Graphs -- A Dichotomy
Aneesh D H, A. Mohanapriya, P. Renjith +1
The class of -star caterpillar convex bipartite graphs generalizes the class of convex bipartite graphs. For a bipartite graph with partitions and , we associate a -st…
Hamiltonicity in Convex Bipartite Graphs
P. Kowsika, V. Divya, N. Sadagopan
For a connected graph, the Hamiltonian cycle (path) is a simple cycle (path) that spans all the vertices in the graph. It is known from \cite{muller,garey} that HAMILTONIAN CYCLE (…
On -free Chordal bipartite graphs
S Aadhavan, P Renjith, N Sadagopan
A bipartite graph is chordal bipartite if every cycle of length at least 6 has a chord in it. In this paper, we investigate the structure of -free chordal bipartite graphs and…
Hamiltonian Path in Split Graphs- a Dichotomy
P. Renjith, N. Sadagopan
In this paper, we investigate Hamiltonian path problem in the context of split graphs, and produce a dichotomy result on the complexity of the problem. Our main result is a deep in…
FO and MSO approach to Some Graph Problems: Approximation and Poly time Results
Kona Harshita, Sounaka Mishra, Renjith. P +1
The focus of this paper is two fold. Firstly, we present a logical approach to graph modification problems such as minimum node deletion, edge deletion, edge augmentation problems…
The Hamiltonian Cycle in -free Split Graphs -- A Dichotomy
P. Renjith, N. Sadagopan
In this paper, we investigate the well-studied Hamiltonian cycle problem (HCYCLE), and present an interesting dichotomy result on split graphs. T. Akiyama et al. (1980) have shown…
Spanning Trees in 2-trees
P. Renjith, N. Sadagopan, Douglas B. West
A spanning tree of a graph is a connected acyclic spanning subgraph of . We consider enumeration of spanning trees when is a -tree, meaning that is obtained from…
2-Trees: Structural Insights and the study of Hamiltonian Paths
P. Renjith, N. Sadagopan
For a connected graph, a path containing all vertices is known as \emph{Hamiltonian path}. For general graphs, there is no known necessary and sufficient condition for the existenc…
Complexity of Steiner Tree in Split Graphs - Dichotomy Results
Madhu Illuri, P. Renjith, N. Sadagopan
Given a connected graph and a terminal set , {\em Steiner tree} asks for a tree that includes all of with at most edges for some integer . I…