Communications in Combinatorics and Optimization
Volume:10 Issue: 2, Spring 2025

Let $G=(V, E)$ be a simple connected graph. A nonempty set $S\subseteq V$ is a secure set if every attack on $S$ is defendable. In this paper, $k$-secure sets are introduced as a generalization of secure sets. For any integer $k\geq 0$, a nonempty subset $S$ of $V$ is a $k$-secure set if, for each attack on $S$, there is a defense of $S$ such that for every $v\in S$, the defending set of $v$ contains at least $k$ more elements than that of the attacking set of $v$, whenever the vertex $v$ has neighbors outside $S$. The cardinality of a minimum $k$-secure set in $G$ is the $k$-security number of $G$. Some properties of $k$-secure sets are discussed and a characterization of $k$-secure sets is obtained. Also, 1-security numbers of certain classes of graphs are determined.

The extremal Gutman index is a concept that studies the maximum or minimum value of the Gutman index for a particular class of graphs. This research area is concerned with finding the graphs that have the lowest possible Gutman index within a set of graphs that have been transformed in some way, such as by adding or removing edges or vertices. By understanding the graphs that have the lowest possible Gutman index, researchers can better understand the fundamental principles of graph stability and the role that different graph transformations play in affecting the overall stability of a graph. The research in this area is ongoing and continues to expand as new techniques and algorithms are developed. The findings from this research have the potential to have a significant impact on a wide range of fields and can lead to new and more effective ways of analyzing and understanding complex systems and relationships in a variety of applications. This paper focuses on the study of specific types of trees that are defined by fixed parameters and characterized based on their Gutman index. Specifically, we explore the structural properties of graphs that have the lowest Gutman index within these classes of trees. To achieve this, we utilize various graph transformations that either decrease or increase the Gutman index. By applying these transformations, we construct trees that satisfy the desired criteria.

Let $G$ be a simple graph with vertex set $V(G)=\{1,2,\dots,n\}$ and $\delta(i)= \sum\limits_{\{i,j\} \in E(G)}d(j)$, where $d(j)$ is the degree of the vertex $j$ in $G$. Inspired by the second Zagreb matrix and neighborhood first Zagreb matrix of a graph, we introduce the neighborhood second Zagreb matrix of $G$, denoted by $N_F(G)$. It is the $n\times n$ matrix whose $ij$-th entry is equal to $\delta(i)\delta(j)$, if $i$ and $j$ are adjacent in $G$ and $0$, otherwise. The neighborhood second Zagreb spectral radius $\rho_{N_F}(G)$ is the largest eigenvalue of $N_F(G)$. The neighborhood second Zagreb energy $\mathcal{E}(N_F)$ of the graph $G$ is the sum of the absolute values of the eigenvalues of $N_F(G)$. In this paper, we obtain some spectral properties of $N_F(G)$. We provide sharp bounds for $\rho_{N_F}(G)$ and $\mathcal{E}(N_F)$, and obtain the corresponding extremal graphs.

A global restrained Roman dominating function on a graph $G=(V,E)$ to be a function $f:V\rightarrow\{0,1,2\}$ such that $f$ is a restrained Roman dominating function of both $G$ and its complement $\overline G$. The weight of a global restrained Roman dominating function is the value $w(f)=\Sigma_{u \in V} f(u)$. The minimum weight of a global restrained Roman dominating function of $G$ is called the global restrained Roman domination number of $G$ and denoted by $\gamma_{grR}(G)$. In this paper we initiate the study of global restrained Roman domination number of graphs. We then prove that the problem of computing $\gamma_{grR}$ is NP-hard even for bipartite and chordal graphs. The global restrained Roman domination of a given graph is studied versus to the other well known domination parameters such as restrained Roman domination number $\gamma_{rR}$ and global domination number $\gamma_g$ by bounding $\gamma_{grR}$ from below and above involving $\gamma_{rR}$ and $\gamma_g$ for general graphs, respectively. We characterize graphs $G$ for which $\gamma_{grR}(G)\in \{1,2,3,4,5\}$. It is shown that: for trees $T$ of order $n$, $\gamma_{grR}(T)=n$ if and only if diameter of $T$ is at most $5$. Finally, the triangle free graphs $G$ for which $\gamma_{grR}(G)=|V|$ are characterized.

Let $\mathcal{B}$ be a commutative ring with unity $1\neq 0$, $1\leq m <\infty$ be an integer and $\mathcal{R}=\mathcal{B}\times \mathcal{B} \times\cdots\times \mathcal{B}$ ($m$ times). The total essential dot product graph $ETD(\mathcal{R})$ and the essential zero-divisor dot product graph $EZD(\mathcal{R})$ are undirected graphs with the vertex sets $\mathcal{R}^{*} = \mathcal{R}\setminus \{(0,0,...0)\}$ and $Z(\mathcal{R})^*=Z(\mathcal{R})\setminus \{(0,0,...,0)\}$ respectively. Two distinct vertices $w=(w_1,w_2,...,w_m)$ and $z=(z_1,z_2,...,z_m)$ are adjacent if and only if $ann_\mathcal{B}(w\cdot z)$ is an essential ideal of $\mathcal{B}$ (where $w\cdot z=w_1z_1+w_2z_2+\cdots +w_mz_m\in \mathcal{B}$). In this paper, we prove some results on connectedness, diameter and girth of $ETD(\mathcal{R})$ and $EZD(\mathcal{R})$. We classify the ring $\mathcal{R}$ such that $EZD(\mathcal{R})$ and $ETD(\mathcal{R})$ are planar, outerplanar, and of genus one.

For a graph $G(V,E)$ which is undirected, simple, and finite, we denote by $|V|$ and $|E|$ the cardinality of the vertex set $V$ and the edge set $E$ of $G$, respectively. A \textit{graceful labeling} $f$ for the graph $G$ is an injective function ${f}:V\rightarrow \{0,1,2,..., |E|\}$ such that $\{|f(u)-f(v)|:uv\in E\}=\{1,2,...,|E|\}$. A graph that has a graceful-labeling is called \textit{graceful} graph. A vertex (resp. edge) coloring is an assignment of color (positive integer) to every vertex (resp. edge) of $G$ such that any two adjacent vertices (resp. edges) have different colors. A \textit{graceful coloring} of $G$ is a vertex coloring $c: V\rightarrow \{1,2,\ldots, k\},$ for some positive integer $k$, which induces edge coloring $|c(u)-c(v)|$, $uv\in E$. If $c$ also satisfies additional property that every induced edge color is odd, then the coloring $c$ is called an \textit{odd-graceful coloring} of $G$. If an odd-graceful coloring $c$ exists for $G$, then the smallest number $k$ which maintains $c$ as an odd-graceful coloring, is called \textit{odd-graceful chromatic number} for $G$. In the latter case we will denote the odd-graceful chromatic number of $G$ as $\mathcal{X}_{og}(G)=k$. Otherwise, if $G$ does not admit odd-graceful coloring, we will denote its odd-graceful chromatic number as $\mathcal{X}_{og}(G)=\infty$. In this paper, we derived some facts of odd-graceful coloring and determined odd-graceful chromatic numbers of some basic graphs.

Let $\mathcal G = (\mathcal V, \mathcal E)$ be a simple graph, an $L(2,1)$-labeling of $\mathcal G$ is an assignment of labels from non-negative integers to vertices of $\mathcal G$ such that adjacent vertices get labels which differ by at least by two, and vertices which are at distance two from each other get different labels. The $\lambda$-number of $\mathcal G$, denoted by $\lambda(\mathcal G)$, is the smallest positive integer $\ell$ such that $\mathcal G$ has an $L(2,1)$-labeling with all labels as  members of the set $\{ 0, 1, \dots, \ell \}$. The zero-divisor graph of a finite commutative ring $R$ with unity, denoted by $\Gamma(R)$, is the simple graph whose vertices are all zero divisors of $R$ in which two vertices $u$ and $v$ are adjacent  if and only if $uv = 0$ in $R$. In this paper, we investigate $L(2,1)$-labeling of some  zero-divisor graphs. We study the \textit{partite truncation}, a graph operation that allows us to obtain a reduced graph of relatively small order from a graph of significantly larger order. We establish the relation between  $\lambda$-numbers of the graph  and its partite truncated one. We make use of the operation \textit{partite truncation} to contract the zero-divisor graph of a reduced ring to the zero-divisor graph of a Boolean ring.

In this paper, we  discuss the structure of polycyclic codes over the ring $R=\mathbb{F}_q+u\mathbb{F}_q+v\mathbb{F}_q;u^2=\alpha u,v^2=v$ and $uv=vu=0$, where $\alpha$ is an unit element in $R.$ We introduce annihilator self-dual codes, annihilator self-orthogonal codes and annihilator LCD codes over R. Using a Gray map, we define a one to one correspondence between $R$ and $\mathbb{F}_q$ and  construct quasi polycyclic  codes over the  $\mathbb{F}_q$.

Let $\Phi=(G,\varphi)$ be a $\mathbb{T}$-gain (or complex unit gain) graph and $A(\Phi)$ be its adjacency matrix. The nullity of $\Phi$, denoted by $\eta(\Phi)$, is the multiplicity of zero as an eigenvalue of $A(\Phi)$, and the cyclomatic number of $\Phi$ is defined by $c(\Phi)=e(\Phi)-n(\Phi)+\kappa(\Phi)$, where $n(\Phi)$, $e(\Phi)$ and $\kappa(\Phi)$ are the number of vertices, edges and connected components of $\Phi$, respectively. A connected graph is said to be cycle-spliced if every block in it is a cycle. We consider the nullity of cycle-spliced $\mathbb{T}$-gain graphs. Given a cycle-spliced $\mathbb{T}$-gain graph $\Phi$ with $c(\Phi)$ cycles, we prove that $0 \leq \eta(\Phi)\leq c(\Phi)+1$. Moreover, we show that there is no cycle-spliced  $\mathbb{T}$-gain graph $\Phi$ of any order with $\eta(\Phi)=c(\Phi)$ whenever there are no odd cycles whose gain has real part $0$. We give examples of cycle-spliced  $\mathbb{T}$-gain graphs whose nullity equals the cyclomatic number, and we show some properties of those graphs $\Phi$ such that $\eta(\Phi)=c(\Phi)-\varepsilon$, $\varepsilon \in \{0,1\}$. A characterization is given in case $\eta(\Phi)=c(\Phi)$ when $\Phi$ is obtained by identifying a unique common vertex of $2$ cycle-spliced $\mathbb{T}$-gain graphs $\Phi_1$ and $\Phi_2$. Finally, we compute the nullity of all $\mathbb{T}$-gain graphs $\Phi$ with $c(\Phi)=2$.

This paper proposes a novel hybrid conjugate gradient method for nonparametric statistical inference.The proposed method is a convex combination of the modified linear search (MLS) and Fletcher-Reeves (FR) methods, and it inherits the advantages of both methods. The FR method is known for its fast convergence, while the MLS method is known for its robustness to noise. The proposed method combines these advantages to achieve both fast convergence and robustness to noise. Our method is evaluated on a variety of nonparametric statistical problems, including kernel density estimation, regression, and classification. The results show that the new method outperforms the MLS and FR methods in terms of both accuracy and efficiency.

In this paper, we introduce a modified version of the simple-intersection graph for semisimple rings, applied to a ring $R$ with unity. The findings from this modified version are subsequently utilized to solve several coloring optimization problems.  We demonstrate how the clique number of the simple-intersection graph can be used to determine the maximum number  of possibilities that can be selected from a set of $n$ colors without replacement or order, subject to the constraint that  any pair shares only one common color. We also show how the domination number can be used to determine the  minimum number of possibilities that can be selected, such that any other possibility shares one color with  at least one of the selected possibilities, is $n-1$.

Let $G$ be a simple graph with vertex set $V=V(G)$ and edge set $E=E(G)$. For a real function $f$ defined on nonnegative real numbers, the vertex-degree function index $H_{f}(G)$ is defined as $$H_{f}(G)=\sum_{u\in V(G)}f(d_{u}).$$ In this paper we introduce the vertex-degree function index $H_{f}(D)$ of a digraph $D$. After giving some examples and basic properties of $H_{f}(D)$, we find the extremal values of $H_{f}$ among all tournaments with a fixed number of vertices, when $f$ is a continuous and convex (or concave) real function on $\left[ 0,+\infty \right)$.

The topological indices are the numerical parameters of a graph that characterize the topology of a graph and are usually graph invariant. The topological indices are classified based on the properties of graphs. The degree distance index is the topological index which is calculated by counting the degrees and distance between the vertices. In this paper, the degree distance index of the connected thorn graph, the graph obtained by joining an edge between two connected graphs, and one vertex union of two connected graphs are calculated.

The injective chromatic number $\chi_i(G)$ of a graph $G$ is the smallest number of colors required to color the vertices of $G$ such that any two vertices with a common neighbor are assigned distinct colors. The Mycielskian or Mycielski graph $\mu(G)$ of a graph $G$, introduced by Jan Mycielski in 1955 has the property that, these graphs have large chromatic number with small clique number. The generalized Mycielskian $\mu_m(G),m>0$ (also known as cones over graphs) are the natural generalizations of the Mycielski graphs. In this paper, sharp bounds are obtained for the injective chromatic number of generalized Mycielskian of any graph $G$. Further, the injective chromatic number of generalized Mycielskian of some special classes of graphs such as paths, cycles, complete graphs, and complete bipartite graphs are obtained.

In the last years, Naji et al. have introduced leap Zagreb indices conceived depending on the second degrees of vertices, where the second degree of a vertex $v$ in a graph $G$ is equal to the number of its second neighbors and denoted by $d_2(v/G)$.  Analogously, the leap Zagreb coindices were introduced by Ferdose and Shivashankara. The first leap Zagreb coindex of a graph is defined as  $\overline{L_1}(G)=\sum_{uv\not\in E_2(G)}(d_2(u)+d_2(v))$, where $E_2(G)$ is the 2-distance (second) edge set of $G$, In this paper, we present explicit exact expressions for the first leap Zagreb coindex $\overline{L_1}(G)$ of some graph operations.