Showing 1–13 of 13 results for author: Reddy, P V S

Integer Linear Programming Formulations for Triple and Quadruple Roman Domination Problems

Authors: Sanath Kumar Vengaldas, Adarsh Reddy Muthyala, Bharath Chaitanya Konkati, P. Venkata Subba Reddy

Abstract: Roman domination is a well researched topic in graph theory. Recently two new variants of Roman domination, namely triple Roman domination and quadruple Roman domination problems have been introduced, to provide better defense strategies. However, triple Roman domination and quadruple Roman domination problems are NP-hard. In this paper, we have provided genetic algorithm for solving triple and qu… ▽ More Roman domination is a well researched topic in graph theory. Recently two new variants of Roman domination, namely triple Roman domination and quadruple Roman domination problems have been introduced, to provide better defense strategies. However, triple Roman domination and quadruple Roman domination problems are NP-hard. In this paper, we have provided genetic algorithm for solving triple and quadruple Roman domination problems. Programming (ILP) formulations for triple Roman domination and quadruple Roman domination problems have been proposed. The proposed models are implemented using IBM CPLEX 22.1 optimization solvers and obtained results for random graphs generated using NetworkX Erdos-Renyi model. △ Less

Submitted 1 May, 2023; originally announced May 2023.

Chaotic Variational Auto encoder-based Adversarial Machine Learning

Authors: Pavan Venkata Sainadh Reddy, Yelleti Vivek, Gopi Pranay, Vadlamani Ravi

Abstract: Machine Learning (ML) has become the new contrivance in almost every field. This makes them a target of fraudsters by various adversary attacks, thereby hindering the performance of ML models. Evasion and Data-Poison-based attacks are well acclaimed, especially in finance, healthcare, etc. This motivated us to propose a novel computationally less expensive attack mechanism based on the adversarial… ▽ More Machine Learning (ML) has become the new contrivance in almost every field. This makes them a target of fraudsters by various adversary attacks, thereby hindering the performance of ML models. Evasion and Data-Poison-based attacks are well acclaimed, especially in finance, healthcare, etc. This motivated us to propose a novel computationally less expensive attack mechanism based on the adversarial sample generation by Variational Auto Encoder (VAE). It is well known that Wavelet Neural Network (WNN) is considered computationally efficient in solving image and audio processing, speech recognition, and time-series forecasting. This paper proposed VAE-Deep-Wavelet Neural Network (VAE-Deep-WNN), where Encoder and Decoder employ WNN networks. Further, we proposed chaotic variants of both VAE with Multi-layer perceptron (MLP) and Deep-WNN and named them C-VAE-MLP and C-VAE-Deep-WNN, respectively. Here, we employed a Logistic map to generate random noise in the latent space. In this paper, we performed VAE-based adversary sample generation and applied it to various problems related to finance and cybersecurity domain-related problems such as loan default, credit card fraud, and churn modelling, etc., We performed both Evasion and Data-Poison attacks on Logistic Regression (LR) and Decision Tree (DT) models. The results indicated that VAE-Deep-WNN outperformed the rest in the majority of the datasets and models. However, its chaotic variant C-VAE-Deep-WNN performed almost similarly to VAE-Deep-WNN in the majority of the datasets. △ Less

Submitted 24 February, 2023; originally announced February 2023.

Comments: 24 pages, 6 figures and 5 tables

MSC Class: 68T01; 68M25 ACM Class: I.2.6; K.6.5

Algorithmic Complexity of Isolate Secure Domination in Graphs

Authors: Jakkepalli Pavan Kumar, P. Venkata Subba Reddy

Abstract: A dominating set $S$ is an Isolate Dominating Set (IDS) if the induced subgraph $G[S]$ has at least one isolated vertex. In this paper, we initiate the study of new domination parameter called, isolate secure domination. An isolate dominating set $S\subseteq V$ is an isolate secure dominating set (ISDS), if for each vertex $u \in V \setminus S$, there exists a neighboring vertex $v$ of $u$ in $S$… ▽ More A dominating set $S$ is an Isolate Dominating Set (IDS) if the induced subgraph $G[S]$ has at least one isolated vertex. In this paper, we initiate the study of new domination parameter called, isolate secure domination. An isolate dominating set $S\subseteq V$ is an isolate secure dominating set (ISDS), if for each vertex $u \in V \setminus S$, there exists a neighboring vertex $v$ of $u$ in $S$ such that $(S \setminus \{v\}) \cup \{u\}$ is an IDS of $G$. The minimum cardinality of an ISDS of $G$ is called as an isolate secure domination number, and is denoted by $γ_{0s}(G)$. Given a graph $ G=(V,E)$ and a positive integer $ k,$ the ISDM problem is to check whether $ G $ has an isolate secure dominating set of size at most $ k.$ We prove that ISDM is NP-complete even when restricted to bipartite graphs and split graphs. We also show that ISDM can be solved in linear time for graphs of bounded tree-width. △ Less

Submitted 12 February, 2020; originally announced February 2020.

Comments: arXiv admin note: substantial text overlap with arXiv:2002.00002; text overlap with arXiv:2001.11250

MSC Class: 05C69; 68Q25

Algorithmic Aspects of 2-Secure Domination in Graphs

Authors: J. Pavan Kumar, P. Venkata Subba Reddy

Abstract: Let $G(V,E)$ be a simple, undirected and connected graph. A dominating set $S \subseteq V(G)$ is called a $2$-\textit{secure dominating set} ($2$-SDS) in $G$, if for every pair of distinct vertices $u_1,u_2 \in V(G)$ there exists a pair of distinct vertices $v_1,v_2 \in S$ such that $v_1 \in N[u_1]$, $v_2 \in N[u_2]$ and $(S \setminus \{v_1,v_2\}) \cup \{u_1,u_2 \}$ is a dominating set in $G$. The… ▽ More Let $G(V,E)$ be a simple, undirected and connected graph. A dominating set $S \subseteq V(G)$ is called a $2$-\textit{secure dominating set} ($2$-SDS) in $G$, if for every pair of distinct vertices $u_1,u_2 \in V(G)$ there exists a pair of distinct vertices $v_1,v_2 \in S$ such that $v_1 \in N[u_1]$, $v_2 \in N[u_2]$ and $(S \setminus \{v_1,v_2\}) \cup \{u_1,u_2 \}$ is a dominating set in $G$. The $2$\textit{-secure domination number} denoted by $γ_{2s}(G)$, equals the minimum cardinality of a $2$-SDS in $G$. Given a graph $ G$ and a positive integer $ k,$ the $ 2 $-Secure Domination ($ 2 $-SDM) problem is to check whether $ G $ has a $ 2 $-secure dominating set of size at most $ k.$ It is known that $ 2 $-SDM is NP-complete for bipartite graphs. In this paper, we prove that the $ 2 $-SDM problem is NP-complete for planar graphs and doubly chordal graphs, a subclass of chordal graphs. We strengthen the NP-complete result for bipartite graphs, by proving this problem is NP-complete for some subclasses of bipartite graphs namely, star convex bipartite, comb convex bipartite graphs. We prove that $ 2 $-SDM is linear time solvable for bounded tree-width graphs. We also show that the $ 2 $-SDM is W[2]-hard even for split graphs. The Minimum $ 2 $-Secure Dominating Set (M2SDS) problem is to find a $ 2 $-secure dominating set of minimum size in the input graph. We propose a $ Δ(G)+1 $ $ - $ approximation algorithm for M2SDS, where $ Δ(G) $ is the maximum degree of the input graph $ G $ and prove that M2SDS cannot be approximated within $ (1 - ε) \ln(| V | ) $ for any $ ε> 0 $ unless $ NP \subseteq DTIME(| V |^{ O(\log \log | V | )}) $. % even for bipartite graphs. A secure dominating set of a graph \textit{defends} one attack at any vertex of the graph. Finally, we show that the M2SDS is APX-complete for graphs with $Δ(G)=4.$ △ Less

Submitted 5 February, 2020; originally announced February 2020.

Comments: arXiv admin note: substantial text overlap with arXiv:2001.11250, arXiv:2002.00002

MSC Class: 05C69; 68Q25

Algorithmic Complexity of Secure Connected Domination in Graphs

Authors: Jakkepalli Pavan Kumar, P. Venkata Subba Reddy, S. Arumugam

Abstract: Let $G = (V,E)$ be a simple, undirected and connected graph. A connected (total) dominating set $S \subseteq V$ is a secure connected (total) dominating set of $G$, if for each $ u \in V \setminus S$, there exists $v \in S$ such that $uv \in E$ and $(S \setminus \lbrace v \rbrace) \cup \lbrace u \rbrace $ is a connected (total) dominating set of $G$. The minimum cardinality of a secure connected (… ▽ More Let $G = (V,E)$ be a simple, undirected and connected graph. A connected (total) dominating set $S \subseteq V$ is a secure connected (total) dominating set of $G$, if for each $ u \in V \setminus S$, there exists $v \in S$ such that $uv \in E$ and $(S \setminus \lbrace v \rbrace) \cup \lbrace u \rbrace $ is a connected (total) dominating set of $G$. The minimum cardinality of a secure connected (total) dominating set of $G$ denoted by $ γ_{sc} (G) (γ_{st}(G))$, is called the secure connected (total) domination number of $G$. In this paper, we show that the decision problems corresponding to secure connected domination number and secure total domination number are NP-complete even when restricted to split graphs or bipartite graphs. The NP-complete reductions also show that these problems are w[2]-hard. We also prove that the secure connected domination problem is linear time solvable in block graphs and threshold graphs. △ Less

Submitted 3 February, 2020; originally announced February 2020.

MSC Class: 05C69; 68Q25

Algorithmic Aspects of Some Variants of Domination in Graphs

Authors: Jakkepalli Pavan Kumar, P. Venkata Subba Reddy

Abstract: A set $S \subseteq V$ is a dominating set in G if for every u \in V \ S, there exists $v \in S$ such that $(u,v) \in E$, i.e., $N[S] = V$. A dominating set $S$ is an Isolate Dominating Set} (IDS) if the induced subgraph $G[S]$ has at least one isolated vertex. It is known that Isolate Domination Decision problem (IDOM) is NP-complete for bipartite graphs. In this paper, we extend this by showing t… ▽ More A set $S \subseteq V$ is a dominating set in G if for every u \in V \ S, there exists $v \in S$ such that $(u,v) \in E$, i.e., $N[S] = V$. A dominating set $S$ is an Isolate Dominating Set} (IDS) if the induced subgraph $G[S]$ has at least one isolated vertex. It is known that Isolate Domination Decision problem (IDOM) is NP-complete for bipartite graphs. In this paper, we extend this by showing that the IDOM is NP-complete for split graphs and perfect elimination bipartite graphs, a subclass of bipartite graphs. A set $S \subseteq V$ is an independent set if G[S] has no edge. A set S \subseteq V is a secure dominating set of $G$ if, for each vertex $u \in V \setminus S$, there exists a vertex $v \in S$ such that $ (u,v) \in E $ and $(S \ \{v\}) \cup \{u\}$ is a dominating set of $G$. In addition, we initiate the study of a new domination parameter called, independent secure domination. A set $S\subseteq V$ is an Independent Secure Dominating Set (InSDS) if $S$ is an independent set and a secure dominating set of $G$. The minimum size of an InSDS in $G$ is called the independent secure domination number of $G$ and is denoted by $γ_{is}(G)$. Given a graph $ G$ and a positive integer $ k,$ the InSDM problem is to check whether $ G $ has an independent secure dominating set of size at most $ k.$ We prove that InSDM is NP-complete for bipartite graphs and linear time solvable for bounded tree-width graphs and threshold graphs, a subclass of split graphs. The MInSDS problem is to find an independent secure dominating set of minimum size, in the input graph. Finally, we prove that the MInSDS problem is APX-hard for graphs with maximum degree $5.$ △ Less

Submitted 12 February, 2020; v1 submitted 30 January, 2020; originally announced February 2020.

Comments: arXiv admin note: text overlap with arXiv:2001.11250

MSC Class: 05C69; 68Q25

Algorithmic Aspects of Secure Connected Domination in Graphs

Authors: Jakkepalli Pavan Kumar, P. Venkata Subba Reddy

Abstract: Let $G = (V,E)$ be a simple, undirected and connected graph. A connected dominating set $S \subseteq V$ is a secure connected dominating set of $G$, if for each $ u \in V\setminus S$, there exists $v\in S$ such that $(u,v) \in E$ and the set $(S \setminus \{ v \}) \cup \{ u \} $ is a connected dominating set of $G$. The minimum size of a secure connected dominating set of $G$ denoted by… ▽ More Let $G = (V,E)$ be a simple, undirected and connected graph. A connected dominating set $S \subseteq V$ is a secure connected dominating set of $G$, if for each $ u \in V\setminus S$, there exists $v\in S$ such that $(u,v) \in E$ and the set $(S \setminus \{ v \}) \cup \{ u \} $ is a connected dominating set of $G$. The minimum size of a secure connected dominating set of $G$ denoted by $ γ_{sc} (G)$, is called the secure connected domination number of $G$. Given a graph $ G$ and a positive integer $ k,$ the Secure Connected Domination (SCDM) problem is to check whether $ G $ has a secure connected dominating set of size at most $ k.$ In this paper, we prove that the SCDM problem is NP-complete for doubly chordal graphs, a subclass of chordal graphs. We investigate the complexity of this problem for some subclasses of bipartite graphs namely, star convex bipartite, comb convex bipartite, chordal bipartite and chain graphs. The Minimum Secure Connected Dominating Set (MSCDS) problem is to find a secure connected dominating set of minimum size in the input graph. We propose a $ (Δ(G)+1) $ - approximation algorithm for MSCDS, where $ Δ(G) $ is the maximum degree of the input graph $ G $ and prove that MSCDS cannot be approximated within $ (1 -ε) ln(| V |)$ for any $ ε> 0 $ unless $ NP \subseteq DTIME(| V |^{O(log log | V |)})$ even for bipartite graphs. Finally, we show that the MSCDS is APX-complete for graphs with $Δ(G)=4$. △ Less

Submitted 30 January, 2020; originally announced January 2020.

MSC Class: 05C69; 68Q25

Conditional and Unique Coloring of Graphs (revised resubmission)

Authors: P. V. Subba Reddy, K. V. Iyer

Abstract: For integers $k>0$ and $0<r \leq Δ$ (where $r \leq k$), a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to vertices with at least $\min\{r, d(v)\}$ differently colored neighbors. The smallest integer $k$ for which a graph $G$ has a conditional $(k,r)$-coloring is called the $r$th order cond… ▽ More For integers $k>0$ and $0<r \leq Δ$ (where $r \leq k$), a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to vertices with at least $\min\{r, d(v)\}$ differently colored neighbors. The smallest integer $k$ for which a graph $G$ has a conditional $(k,r)$-coloring is called the $r$th order conditional chromatic number, denoted by $χ_r(G)$. For different values of $r$ we first give results (exact values or bounds for $χ_r(G)$ depending on $r$) related to the conditional coloring of graphs. Then we obtain $χ_r(G)$ of certain parameterized graphs viz., windmill graph, line graph of windmill graph, middle graph of friendship graph, middle graph of a cycle, line graph of friendship graph, middle graph of complete $k$-partite graph, middle graph of a bipartite graph and gear graph. Finally we introduce \emph{unique conditional colorability} and give some related results. △ Less

Submitted 30 January, 2012; originally announced January 2012.

Comments: Was submitted and withdrawn from Utilitas Mathematica prior to submission to Graphs and Combinatorics where the paper in this version is now under review

MSC Class: 68R10; 05C15

Conditional and Unique Coloring of Graphs

Authors: P. Venkata Subba Reddy, K. Viswanathan Iyer

Abstract: For integers $k, r > 0$, a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to at least $\min\{r, d(v)\}$ differently colored vertices. Given $r$, the smallest integer $k$ for which $G$ has a conditional $(k,r)$-coloring is called the $r$th order conditional chromatic number $χ_r(G)$ of $G$. W… ▽ More For integers $k, r > 0$, a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to at least $\min\{r, d(v)\}$ differently colored vertices. Given $r$, the smallest integer $k$ for which $G$ has a conditional $(k,r)$-coloring is called the $r$th order conditional chromatic number $χ_r(G)$ of $G$. We give results (exact values or bounds for $χ_r(G)$, depending on $r$) related to the conditional coloring of some graphs. We introduce \emph{unique conditional colorability} and give some related results. (Keywords. cartesian product of graphs; conditional chromatic number; gear graph; join of graphs.) △ Less

Submitted 17 June, 2011; originally announced June 2011.

Comments: Under review in International Journal of Computer Mathematics

MSC Class: 68R10; 05C15

Conditional coloring of some parameterized graphs

Authors: P. Venkata Subba Reddy, K. Viswanathan Iyer

Abstract: For integers k>0 and r>0, a conditional (k,r)-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex v of degree d(v) in G is adjacent to vertices with at least min{r,d(v)} different colors. The smallest integer k for which a graph G has a conditional (k,r)-coloring is called the rth order conditional chromatic number, denoted by $χ_r(G)$. For different values of… ▽ More For integers k>0 and r>0, a conditional (k,r)-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex v of degree d(v) in G is adjacent to vertices with at least min{r,d(v)} different colors. The smallest integer k for which a graph G has a conditional (k,r)-coloring is called the rth order conditional chromatic number, denoted by $χ_r(G)$. For different values of r we obtain $χ_r(G)$ of certain parameterized graphs viz., Windmill graph, line graph of Windmill graph, middle graph of Friendship graph, middle graph of a cycle, line graph of Friendship graph, middle graph of complete k-partite graph and middle graph of a bipartite graph. △ Less

Submitted 10 December, 2010; originally announced December 2010.

Comments: Communicated to Utilitas Mathematica

MSC Class: 68R10; 05C15

On conditional coloring of some graphs

Authors: P. Venkata Subba Reddy, K. Viswanathan Iyer

Abstract: For integers r and k > 0(k>r),a conditional (k, r)-coloring of a graph G is a proper k-coloring of G such that every vertex v of G has at least min{r,d(v)} differently colored neighbors, where d(v) is the degree of v. In this note, for different values of r we obtain the conditional chromatic number of a grid $G(2,n) \cong P_2 \ \Box \ P_n$, $C_n^2$ and the strong product of $P_n$ and $P_m$ (n,m b… ▽ More For integers r and k > 0(k>r),a conditional (k, r)-coloring of a graph G is a proper k-coloring of G such that every vertex v of G has at least min{r,d(v)} differently colored neighbors, where d(v) is the degree of v. In this note, for different values of r we obtain the conditional chromatic number of a grid $G(2,n) \cong P_2 \ \Box \ P_n$, $C_n^2$ and the strong product of $P_n$ and $P_m$ (n,m being positive integers). Also, for integers $n \geq 3$ and $t \geq 1$ the second order conditional chromatic number (also known as dynamic chromatic number) of the (t,n)-web graph is obtained. △ Less

Submitted 23 November, 2010; originally announced November 2010.

Comments: 9 pages: accepted for the 76th annual conference of the Indian Mathematical Society,27-30 December 2010,Surat,India

MSC Class: 05C12; 05C30; 05C85

Algorithms for enumerating and counting D2CS of some graphs

Authors: P. Venkata Subba Reddy, K. Viswanathan Iyer

Abstract: A D2CS of a graph G is a set $S \subseteq V(G)$ with $diam(G[S]) \leq 2$. We study the problem of counting and enumerating D2CS of a graph. First we give an explicit formula for the number of D2CS in a complete k-ary tree, Fibonacci tree, binary Fibonacci tree and the binomial tree. Next we give an algorithm for enumerating and counting D2CS of a graph. We then give a linear time algorithm for fin… ▽ More A D2CS of a graph G is a set $S \subseteq V(G)$ with $diam(G[S]) \leq 2$. We study the problem of counting and enumerating D2CS of a graph. First we give an explicit formula for the number of D2CS in a complete k-ary tree, Fibonacci tree, binary Fibonacci tree and the binomial tree. Next we give an algorithm for enumerating and counting D2CS of a graph. We then give a linear time algorithm for finding all maximal D2CS in a strongly chordal graph. △ Less

Submitted 19 November, 2010; originally announced November 2010.

Comments: Six pages: Accepted for 15th annual conference of Gwalior academy of mathematical sciences,Dec.12-14, 2010,New Delhi

MSC Class: 05C12; 05C30; 05C85

Fuzzy Modeling and Natural Language Processing for Panini's Sanskrit Grammar

Authors: P. Venkata Subba Reddy

Abstract: Indian languages have long history in World Natural languages. Panini was the first to define Grammar for Sanskrit language with about 4000 rules in fifth century. These rules contain uncertainty information. It is not possible to Computer processing of Sanskrit language with uncertain information. In this paper, fuzzy logic and fuzzy reasoning are proposed to deal to eliminate uncertain informati… ▽ More Indian languages have long history in World Natural languages. Panini was the first to define Grammar for Sanskrit language with about 4000 rules in fifth century. These rules contain uncertainty information. It is not possible to Computer processing of Sanskrit language with uncertain information. In this paper, fuzzy logic and fuzzy reasoning are proposed to deal to eliminate uncertain information for reasoning with Sanskrit grammar. The Sanskrit language processing is also discussed in this paper. △ Less

Submitted 14 June, 2010; originally announced June 2010.

Comments: Submitted to Journal of Computer Science and Engineering, see http://sites.google.com/site/jcseuk/volume-1-issue-1-may-2010

Journal ref: Journal of Computer Science and Engineering, Volume 1, Issue 1, p99-101, May 2010