Discrete Mathematics, Algorithms and Applications

The deficiency $df(v)$ of a vertex $v$ is the deviation between the degree of the vertex $v$ and the maximum degree of the graph. The maximum deficiency matrix $M_{df}(G)$ of a simple graph $G$ is square matrix whose $(i,j)$th entry is max($df(v_i),df(v_j))$, if the vertices $v_i$ and $v_j$ are adjacent and $0$, otherwise. Maximum deficiency energy $E{M}_{df}(G)$ is the absolute sum of eigenvalues of maximum deficiency matrix $M_{df}(G)$. In this paper, we find maximum deficiency energy of some classes of graphs. Moreover, we construct an algorithm and Python 3.8 program to find out spectrum and maximum deficiency energy of $G$.

A decomposition of a graph is a collection of its edge — disjoint subgraphs whose union equals the edge set of the graph. A decomposition all of whose members are paths is called a path decomposition. In this paper, we introduce and initiate a study of a new variation of decomposition namely equitable path decomposition of a graph $G$ which is defined to be a decomposition in which all the members are paths and the lengths of any two paths are differ by at most one in $G$. In this paper, we initiate a study on this parameter.

In this paper, an algorithm is present that uses the sum of disjoint products (SDP) to calculate the reliability bounds of a complex system. The algorithm requires a set of all minimal paths and cuts to compute the bounds of the reliability polynomial. Furthermore, using Boolean algebra to construct a sum-of-products expression. This research aims to create the lower and upper bounds of reliability for a complex communication system (Double-bridge). By minimizing the number of disjointed (mutually exclusive) variables, the method can reduce the computer time required to estimate the probability of the principal events. The communication system is also used to establish the usefulness of the provided algorithm, which is better than the currently used SDP method for big data sets and more specific to understand and implement. Furthermore, simulations and numerical examples have shown that the new technique typically improves Spross bounds, particularly for highly reliable systems.

We consider a discrete search problem to detect a hidden target on one of the $M$-intersected real lines at the origin. The target position is a vector of independent random variables with a known multivariate probability distribution that is symmetric around the origin. From the available information about the probability of the target, we can consider one bounded interval as a search space on each line. To maximize the detection probability, we divide each interval into a number of small subintervals. Some subintervals have low target probabilities; thus, we delete them and distribute their probabilities among the searched subintervals. The problem has a discrete version where each line contains a set of independent search subintervals. The search effort is bounded by a normal distribution. More than obtaining the maximum detection probability, we also need to get the minimum search effort to detect the target. After studying the stability of the minimum search effort, we present an illustrative example to show the effectiveness of our model.

The molecular topological descriptors, which are the numerical invariants of a molecule’s structure, are very good in foretelling a molecule’s bioactivity. Because of its usefulness in many areas of mathematical chemistry, graph theory has achieved tremendous advancements in this field and has become quite popular among scientists. Many of these indices are used and researched in the domains of chemistry, pharmacology, drug manufacture, and other related subjects. This paper calculates the eccentricity indices of a HDN network of the third kind, as well as the total and average eccentricities, $({\mathrm{\text{GA}}}_4)$, $({\mathrm{\text{ABC}}}_5)$, and eccentric version of Zagreb indices. For these descriptors, we also provide analytically closed equations that could be applied in order to explore the network’s underlying topologies.

Let $n\ge 1$ and $U_n$ be the multiplicative group of the additive group ${\mathbb{Z}}_n$ of integers modulo $n$. The unitary Haar graph $H_n=\mathrm{\text{Haar}}({\mathbb{Z}}_n,U_n)$ is a graph with vertex set ${\mathbb{Z}}_n\times \{0,1\}$ and the edge set $\{\{(a,0),(b,1)\}|b-a\in U_n\}$. In this paper, we study some structural properties of $H_n$ such as total chromatic number, diameter, planarity, the girth, vertex-connectivity and edge-connectivity. Also, some spectral properties of the graph $H_n$ are determined.

Cayley graph is a graph that encodes the abstract structure of a group. It gives a way of encoding information about a group in a graph. On the other hand, hypergroup is a generalization of group in which the composition of any two elements is a non-empty set. The purpose of this paper is to find a suitable generalization of Cayley graphs to cover hypergroups. More precisely, we introduce generalized Cayley graphs over hypergroups, study their properties and find a simple tool to construct large connected GCH-graphs from smaller $\mathrm{\text{GCH}}$-graphs by using graph product.

For a simple connected graph $G$ of order $n$ with Laplacian eigenvalues ${\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_{n-1}>{\mu }_n=0$, the Laplacian resolvent energy of $G$ is defined as $\mathrm{\text{RL}}(G)={\sum }_{i=1}^n\frac{1}{n+1-{\mu }_i}.$ In this paper, we provide an improved lower bound for $\mathrm{\text{RL}}(G)$ through majorization. Considering our lower bound, we also derive some lower bounds for $\mathrm{\text{RL}}(G)$ when the graph $G$ possesses tree structure.

Codes over integer rings equipped with the Lee metric are gaining attention among researchers recently. In this paper, we investigate some specific linear codes over integer rings and characterize their dimensions and Lee weights using greatest common divisors (GCD). Furthermore, we construct equidistant Lee codes over ${\mathbb{Z}}_{2^b},{\mathbb{Z}}_{2p}\text{and}{\mathbb{Z}}_p$ which have applications in error detection and error correction.

For a graph $G$, the Mostar index of $G$ is the sum of $|n_u(e)-n_v(e)|$ over all edges $e=uv$ of $G$, where $n_u(e)$ denotes the number of vertices of $G$ that have a smaller distance in $G$ to $u$ than to $v$, and analogously for $n_v(e)$. We determine all the graphs that maximize and minimize the Mostar index, respectively, over all trees in terms of some fixed parameters like the number of odd vertices, the number of vertices of degree two, and the number of pendent paths of fixed length.

Let $\mathrm{\Gamma }$ be a simple graph of order $n$ having $m$ edges and let $\overrightarrow{\mathrm{\Gamma }}$ be an orientation of $\mathrm{\Gamma }$. The hermitian skew Laplacian matrix $SL(\overrightarrow{\mathrm{\Gamma }})$ of $\overrightarrow{\mathrm{\Gamma }}$ is defined as $SL(\overrightarrow{\mathrm{\Gamma }})=\overline{D}(\overrightarrow{\mathrm{\Gamma }})-iS(\overrightarrow{\mathrm{\Gamma }})$, where $i=\sqrt{-1}$ is the imaginary unit, $\overline{D}(\overrightarrow{\mathrm{\Gamma }})$ is the diagonal matrix of oriented degrees ${\overline{d}}_i=d_i^{+}-d_i^{-}$ and $S(\overrightarrow{\mathrm{\Gamma }})$ is the skew matrix. The spectral radius of the matrix $SL(\overrightarrow{\mathrm{\Gamma }})$ is the hermitian skew Laplacian spectral radius and the sum of the absolute values of eigenvalues of $SL(\overrightarrow{\mathrm{\Gamma }})$ is the hermitian skew Laplacian energy of $\overrightarrow{\mathrm{\Gamma }}$. In this paper we study the hermitian spectral radius and hermitian skew Laplacian energy of $\overrightarrow{\mathrm{\Gamma }}$. We obtain some new bounds for the hermitian skew Laplacian spectral radius and characterize the extremal oriented graphs attaining these bounds. Further, we obtain some bounds for the hermitian skew Laplacian energy and locate the extremal oriented graphs.

Given a set ${\mathscr{H}}$ of some positive integers, a positive integer $n$ is ${\mathscr{H}}$-testable if there are two disjoint subsets $P$ and $Q$ of ${\mathscr{H}}$ such that $n={\sum }_{p\in P}p-{\sum }_{q\in Q}q$. The testability of the set $N_n$ of positive integers not exceeding $n$, denoted by $\tau (n)$, is the minimum integer $m$ such that there is a set ${\mathscr{H}}$ with $m$ positive integers satisfying that each $t\in N_n$ is ${\mathscr{H}}$-testable. In this short paper, we prove that $\tau (n)=\lceil {log}_3(2n+1)\rceil$ and propose an algorithm to output the representation of an arbitrary positive integer by the form ${\sum }_{i\in X}{3}^i-{\sum }_{j\in Y}{3}^j$, where $X$ and $Y$ are two disjoint sets of some non-negative integers not exceeding $\tau (n)$.

For an algebraic curve ${𝒳}$ defined over an algebraically closed field of characteristic $p>0$, $a$-number $a({𝒳})$ is the dimension of the space of exact holomorphic differentials on ${𝒳}$. We computed the $a$-number for a family of certain Picard curves using the action of the Cartier operator on $H^0({𝒳},{\mathrm{\Omega }}^1)$.

In this paper, we illustrate the rule for finding number of idempotents in the doubly stochastic matrix semigroup $D_n$ and also locate the idempotents in the case of $D_3$ and $D_4$. Further, we describe idempotent generated ideals of these semigroups and it is shown that the idempotent generated ideals form a lattice.

Let $G$ be a simple connected graph. The modified first Zagreb index is denoted by ${}^m{M}_1(G)$ is defined as ${}^m{M}_1(G)={\sum }_{u\in V}\frac{1}{d{(u)}^2}$. We present a lower bound for ${}^m{M}_1(G)$ in terms of order and total domination number for trees and characterize the extremal trees attaining the bound.

All the graphs considered in this paper are simple and undirected. Let $G=(V(G),E(G))$ be a simple undirected graph. A function $f:V(G)\to \{0,1,2\}$ is called root cube mean cordial labeling if the induced function $f^{\ast }:E(G)\to \{0,1,2\}$ defined by $f^{\ast }(uv)=\lfloor \sqrt{\frac{{(f(u))}^3+{(f(v))}^3}{2}}\rfloor$ satisfies the condition $|v_f(i)-v_f(j)|\le 1$ and $|e_f(i)-e_f(j)|\le 1$ for any $i,j\in \{0,1,2\}$, where $v_f(x)$ and $e_f(x)$ denotes the number of vertices and number of edges with label $x$, respectively, and $\lfloor x\rfloor$ denotes the greatest integer less than or equals to $x$. The $G$ is called root cube mean cordial if it admits root cube mean cordial labeling. In this paper, we have discussed root cube mean cordial labeling of some graphs. Also, we have provided some graphs which are not root cube mean cordial.

A proper vertex coloring of a graph $G$ is said to be locally identifying (lid-coloring) if for any pair $u,v$ of adjacent vertices with distinct closed neighborhoods, the sets of colors in the closed neighborhoods of $u$ and $v$ are different. The smallest integer $k$ for which $G$ admits a lid-coloring is called the lid-chromatic number of $G$. The corona product $G\odot H$ of two graphs $G$ and $H$ is the graph obtained by taking one copy of $G$ and $|V(G)|$ copies of $H$, and then joining the $i$th vertex of $G$ to every vertex in the $i$th copy of $H$ for every $i=1,2,\dots ,|V(G)|$, where $\left|A\right|$ denotes the number of elements in the set $A$. In this paper, the lid-chromatic number of corona product of graphs has been studied.

A graph $G=G(V,E)$ is called $L$-list colorable if there is a vertex coloring of $G$ in which the color assigned to a vertex $v$ is chosen from a list $L(v)$ associated with this vertex. We say $G$ is $k$-choosable if all lists $L(v)$ have the cardinality $k$ and $G$ is $L$-list colorable for all possible assignments of such lists. A graph $G$ is said to be chromatic choosable if its chromatic and list chromatic numbers are equal. Investigation of $\chi$-choosable graphs is one of the open problems. In this paper, we investigate this problem for classes of perfect graphs.