Discrete Mathematics, Algorithms and Applications

In this paper, the group homomorphism graph is introduced and investigated. The group homomorphism graph, denoted by $HI(G,G^{\prime })$, is an undirected graph in which the vertex set contains all homomorphisms excluding the monomorphisms and the zero homomorphism from the group $G$ to the group $G^{\prime }$, and two distinct vertices are adjacent if and only if the intersection of their kernels is non-trivial. We investigate the interplay between the graph-theoretic properties of this graph with algebraic properties of the groups. In this work, connectedness, diameter, clique number, chromatic number, domination number, independence number, etc. are found.

In this paper, we study mixed alphabet codes over two alphabets $Z_2$, and its extension $Z_2[u]=Z_2+u{Z}_2$, $u^2=0$. We define new Gray maps, using which we study cyclic codes and obtain the properties of their generators. Further, we construct constacyclic codes, and linear codes, and observe the useful properties of their generators. Finally, we present some examples of cyclic codes and binary linear codes.

Let $G=(V,E)$ be a graph with $V=V(G)$ and $E=E(G)$. A double Italian dominating function (DIDF) of $G$ is a function $f:V(G)\to \{0,1,2,3\}$ having the property that for every vertex $v\in V$, ${\sum }_{u\in N_G(v)}f(u)\ge 3$, if $f(v)=0$, and ${\sum }_{u\in N_G(v)}^{}f(u)\ge 2$, if $f(v)=1$. The weight of a DIDF is $w(f)={\sum }_{v\in V}f(v)$. The double Italian domination number is the minimum weight taken over all DIDFs of $G$ and denoted by ${\gamma }_{\mathrm{\text{dI}}}(G)$. Two domination parameters related to the DIDF are restrained, and total restrained DID function which are studied on some graphs. A central graph $C(G)$ of a graph $G$ is obtained by subdividing each edge of $G$ exactly once and joining all the non-adjacent vertices of $G$.

In this paper, we obtain the exact value for restrained and total restrained of double Italian domination number of central of custom graphs and in addition, we determine the sharp bounds for central of any graph.

In this research, we introduce the notion of an $L$-soft and investigate several universal properties of it. Then, the family of $L$-softs is established and denoted by ${\text{Soft}}_{𝔈}(𝕃)$. So, we tried to build an algebraic structure on ${\text{Soft}}_{𝔈}(𝕃)$. First, we showed that ${\text{Soft}}_{𝔈}(𝕃)$ with sub-$L$ operation is a poset. Also, we proved that ${\text{Soft}}_{𝔈}(𝕃)$ with some operations made a complete distributive bounded lattice, bounded hoop, bounded L-algebra, CKL-algebra, BCK-algebra, commutative integral quantum B-algebra and Boolean algebra. Finally, we presented a congruence relation on ${\text{Soft}}_{𝔈}(𝕃)$ and we investigated the quotient of it.

Let $R$ be a commutative ring with $1.$ A zero-divisor graph $\mathrm{\Lambda }(R)$ is an undirected graph on the vertex set $R-\{0\}$ such that any two nonzero elements $p,q\in R$ are adjacent whenever $p\cdot q=0.$ The concept of entropy measure is fundamental and has been the subject of interest in various fields. The purpose of this paper is to calculate the entropy measure of $\mathrm{\Lambda }(R)$ for various rings. We take into consideration the ring ${\mathbb{Z}}_h$ for $h=\phi \psi ,{\phi }^2\psi ,{\phi }^2{\psi }^2,\phi \psi \chi ,$ where $\phi ,\psi$ and $\chi$ are distinct prime numbers. Moreover, we also discussed the entropy measure of the zero-divisor graph for the rings $\mathbb{Z}\phi \times \mathbb{Z}\psi ,\mathbb{Z}\phi \times \mathbb{Z}\psi \times \mathbb{Z}\chi ,\mathbb{Z}\phi \psi \times \mathbb{Z}\chi ,$ and $\mathbb{Z}{\phi }^2\times \mathbb{Z}{\psi }^2.$ This study will help us further understand the algebraic structure of the commutative rings.

In the research content of this paper, we characterize the unit interval graphs which are paired $k$-disjoint path coverable. Specifically, we prove that $G$ is paired $k$-disjoint path coverable if and only if $G$ is $(2k-1)$-connected, where $k>2$. Moreover, we show that $G$ is semi-paired $k$-disjoint path coverable if and only if $G$ is $(2k-1)$-connected where $k\ge 3$ and $n\ge 2k$.

In last two decades, the basic Roman domination problem and the variants thereof have attracted many researchers from different fields to study these problems in both ways, theoretically and computationally. Function $f:V\to \{-1,1,2\}$ is the signed Roman domination function (SRDF) if and only if it satisfies the following conditions: (i) for each vertex $v\in V$ of graph $G$ the sum of the values assigned to $v$ and all its neighbors is at least 1 and (ii) each vertex $v\in V$ for which $f(v)=-1$, must be adjacent to at least one vertex $u$ such that $f(u)=2$. The minimum weight ${\sum }_{v\in V}f(v)$ of all SRDFs on graph $G$ is defined as signed Roman domination number (${\gamma }_{\mathrm{\text{sR}}}(G)$). Definition of the signed total Roman domination function (STRDF) follows the definition of SRDF with a minor change where condition (i) considers the sum of all values assigned to all neighbors of $v$ to be at least one, for each vertex $v$. The minimum weight ${\sum }_{v\in V}f(v)$ of all STRDFs on graph $G$ is called signed total Roman domination number (${\gamma }_{\mathrm{\text{stR}}}(G)$). In this paper, we deal with the calculation of the signed (total) Roman domination numbers on a few classes of planar graphs from the literature. We give proofs for the exact values of the numbers ${\gamma }_{\mathrm{\text{sR}}}(A_n)$ and ${\gamma }_{\mathrm{\text{sR}}}(R_n)$ as well as the numbers ${\gamma }_{\mathrm{\text{stR}}}(S_n)$ and ${\gamma }_{\mathrm{\text{stR}}}(T_n)$. For some other classes of planar graphs, such as $Q_n$, and $T_n^{″}$, lower and upper bounds on ${\gamma }_{\mathrm{\text{sR}}}$ are presented.

Let $D$ be a digraph of order $n$. Let $A(D)$ and $\mathrm{\text{Deg}}(D)$ be respectively, the adjacency matrix and the diagonal matrix of vertex out-degrees of $D.$ The generalized adjacency matrix $A_{\alpha }(D)$ of $D$ is defined as

A proper subset $X$ of vertices in the graph $G$ is a captive dominating set if it is a total dominating set and each vertex in $X$ dominates at least one vertex which does not belong to $X$; also, the captive domination number of $G$, denoted by ${\gamma }_{\mathrm{\text{ca}}}(G)$, is the cardinality of a minimum captive dominating set of $G$. In [M. N. Al-Harere, A. A. Omran and A. T. Breesam, Captive domination in graphs, Discrete Math. Algorithms Appl. 12(6) (2020) 2050076], Al-Harere et al., presented some lower and upper bounds for the captive domination number of $G$, using the number of vertices and edges. Here, we present some upper bounds for ${\gamma }_{\mathrm{\text{ca}}}(G)$, using independence number and clique number. Also, the captive domination number of split graphs is studied. Among other results, some lower bounds for the captive domination number, in terms of maximum degree and the number of vertices with maximum degree, are presented.

We consider a new coloring as follows such that a subset of $V(G)$ needs very few colors. Let $G$ be a graph with vertex set $V(G)$ and $a,b,i$ be three integers with $a\ge b\ge i\ge 0$. $S$ is a vertex subset of $G$, graph $G$ is said to be $i$-weak $(a:b)$-choosable about set $S$, if the following can be satisfied: For any list assignment $L=\{L(v):|L(v)|=a,v\in V(G)\}$, there is a way that each vertex $v$ of $S$ is assigned $i$ colors of $L(v)$ and each vertex $u$ of $V(G)\backslash S$ is assigned $b$ colors of $L(v)$ such that the color sets corresponding to adjacent vertices do not intersect. In this paper, we consider the $i$-weak $(a:b)$-choosable problem of $1$-planar graphs without short cycles and prove our results by the discharging method. In this paper, we prove that every $1$-planar graph without $3$-cycles, $5$-cycles and adjacent $4$-cycles is $i$-weak $(4b+i:b)$-choosable about set $S=\{v:v\in V(G),d(v)=4\}$.

In a sweep cover problem, points of interest (PoIs) are required to be visited by mobile sensors periodically. The time span between two consecutive visits of a PoI is the sweep-period of that PoI. In this paper, we study the min sweep-period sweep cover problem with a distance constraint (MinSPSC${}_{\mathrm{\text{DC}}}$). Given $M$ mobile sensors with speed $a$, $K$ base stations and a distance constraint $D$, the goal of MinSPSC${}_{\mathrm{\text{DC}}}$ is to design routes for the mobile sensors such that the maximum sweep-period is minimized under the condition that every mobile sensor has to visit a base station before traveling distance $D$. We present an $\frac{M}{M-K+1}\cdot \frac{2D}{D-2d_{max}}$-approximation algorithm for MinSPSC${}_{\mathrm{\text{DC}}}$, where $d_{\mathrm{\text{max}}}$ is the maximum distance between a PoI and a base station.

For two integers $m$ and $n$ with $m\le n$, a $k$-partite graph is said to be a semi-balanced $k$-partite graph if each partite set has either $n$ or $m$ vertices. We give some degree conditions for semi-balanced $k$-partite graphs to be Hamiltonian and almost pancyclic, respectively. Furthermore, using these results, we obtain the degree conditions for a balanced $k$-partite graph to be vertex bipancyclic if $k$ is even, and vertex $k$-pancyclic if $k$ is odd.

The quad-cube is a special case of the metacube that itself is derivable from the hypercube. It is amenable to an application as a network topology, especially when the node size exceeds several million. This paper presents a sequence of graphs, leading up to the quad-cube, where the graphs in the sequence are important in their own right. For example, they exhibit hypercube-like low diameters and efficient domination parameters, and most of them admit a Hamiltonian cycle. The hierarchy is likely to be useful in the future.

In this paper, we first examine the properties of the matrices of the generalized $m$-step Jacobsthal sequence, and we develop a public key cryptosystem using key exchange based on the relationship between inner product and orthogonality. Then we create encryption and decryption algorithms using this key exchange, self-adjoint operator, and generalized $m$-step Jacobsthal sequence, and we provide a detailed example of how encryption and decryption algorithms work. Finally, a security strength and complexity analysis of these algorithms will be made.

A binary $[n,k]$-linear code ${𝒞}$ is a $k$-dimensional subspace of ${𝔽}_2^n$. For $x\in {𝔽}_2^n$, the set $x+{𝒞}$ is a coset of ${𝒞}$. In this work, we study a partial ordering on the set of cosets of a binary linear code ${𝒞}$ of length $n$: for $x,y\in {𝔽}_2^n$, $x\preccurlyeq y$ provided that $supp(x)\subseteq supp(y)$, and we construct its associated Hasse diagram. We give general and particular examples that help to understand the concept and we obtain general properties of this graph.

For a graph $G$ with vertex set $V_G=\{v_1,v_2,\dots ,v_n\}$ and edge set $E_G=\{e_1,e_2,\dots ,e_m\}$, let $S_G$ denotes the subdivision graph of $G$ with vertex set $V_G\cup E_G$. In $S_G$, replace each vertex $v_i$, $i=1,2,\dots ,n$, by $n_1$ vertices and join every vertex to the neighbors of $v_i$. Then in the resulting graph, replace each vertex $e_j$, $j=1,2,\dots ,m$, by $m_1$ vertices and join every vertex to the neighbors of $e_j$. The resulting graph is denoted by $S_G(n_1,m_1)$. This generalizes the construction of the subdivision graph $S_G$ to $S_G(n_1,m_1)$ of a graph $G$. In this paper, we provide the complete information about the spectrum of $S_G(n_1,m_1)$ using the spectrum of $S_G$. Further, we determine the Laplacian spectrum of $S_G(n_1,m_1)$ using the Laplacian spectrum of $G$, when $G$ is a regular graph. Also, we find the Laplacian spectrum of $S_G(n_1,m_1)$ using the Laplacian spectrum of $S_G$ when $n_1=m_1$. The energy of a graph $G$ is defined as the sum of the absolute values of the eigenvalues of $G$. The incidence energy of a graph $G$ is defined as the sum of the square roots of the signless Laplacian eigenvalues of $G$. Finally, as an application, we show that the energy of the graph $S_G(n_1,m_1)$ is completely determined by the incidence energy of the graph $G$.

For a connected graph $G$ of order $n$, a connected open monophonic set $S$ of vertices in a connected graph $G$ is a minimal connected open monophonic set if no proper subset of $S$ is a connected open monophonic set of $G$. The upper connected open monophonic number om${}_c^{+}(G)$ of $G$ is the maximum cardinality of a minimal connected open monophonic set of $G$. The upper connected open monophonic numbers of certain standard graphs are determined. It is proved that ${\mathrm{\text{om}}}_c^{+}(G)=4$ for the Petersen graph $G$. Also, it is proved that for a graph $G$ of order $n$, ${\mathrm{\text{om}}}_c(G)=n$ if and only if ${\mathrm{\text{om}}}_c^{+}(G)=n$. For positive integers $r$,$d$ and $k\ge 4$ with $r\le d\le 2r$, there exists a connected graph $G$ with $\mathrm{\text{rad}}(G)=r$, $\mathrm{\text{diam}}(G)=d$ and ${\mathrm{\text{om}}}_c^{+}(G)=k$. Further, it is analyzed how the addition of a pendant edge to certain standard graphs affects the upper connected open monophonic number of the respective original graphs.

An equitable $k$-coloring of a graph $G$ is a proper vertex coloring such that $\left|\right|V_i|-|V_j\left|\right|\le 1$ for any $i,j\in \{1,2,\dots ,k\}$, where $V_i$ ($1\le i\le k$) is the set of vertices colored with $i$. If there is an equitable $k$-coloring of $G$, then the graph $G$ is said to be equitably $k$-colorable. In this paper, we prove that every planar graph without 5-cycles and chordal 4-cycles has an equitable $k$-coloring for $k\ge max\{\mathrm{\Delta }(G),6\},$ where $\mathrm{\Delta }(G)$ is the maximum degree of $G$.

Harary and Melter introduced the concept of resolving sets in graphs. Slater stated the term locating set and the minimum resolving set as reference sets. Chartrand mentioned the locating set as a resolving set and the minimum cardinality of a resolving set as metric dimension or simply dimension in later stage. Several types of resolving sets like connected resolving sets, independent resolving sets, acyclic resolving sets, etc. have been discussed in the past. In this work, weakly connected resolving set is introduced and we studied its bounds.

Lattice cryptosystem is a kind of public key cryptosystem which is resistant to quantum computing attacks. Cryptanalysis is involved in the study of lattice cryptanalysis. There are many problems such as the interdisciplinary characteristics are obvious and the research methods tend to be diversified. This paper defines new graph total colorings: graceful-difference total coloring, odd-edge graceful difference total coloring. It is proven that (1) if a connected bipartite graph $G$ recognizes ordered graceful-difference labeling, the bipartite graph $G^{\ast }$ obtained by adding $m$ leaves to connected bipartite graph $G$ recognizes a graceful-difference total coloring, (2) in order to establish a random coloring graphic lattice, two operations are given to design the graphic lattice. The proof of the theorem can be transformed into a feasible and effective algorithm.

For a finite simple undirected graph $G$, the universal adjacency matrix $U(G)$ is a linear combination of the adjacency matrix $A(G)$, the degree diagonal matrix $D(G)$, the identity matrix $I$ and the all-ones matrix $J$, that is $U(G)=\alpha A(G)+\beta D(G)+\gamma I+\eta J$, where $\alpha ,\beta ,\gamma ,\eta \in ℝ$ and $\alpha \ne 0$. The cozero-divisor graph ${\mathrm{\Gamma }}^{\prime }(R)$ of a finite commutative ring $R$ with unity is a simple undirected graph with the set of all nonzero nonunits of $R$ as vertices and two vertices $x$ and $y$ are adjacent if and only if $x\notin yR$ and $y\notin xR$. In this paper, we study structural properties of ${\mathrm{\Gamma }}^{\prime }(R)$ by defining an equivalence relation on its vertex set in terms of principal ideals of the ring $R$. Then we obtain the universal adjacency eigenpairs of ${\mathrm{\Gamma }}^{\prime }(R)$ and its complement, and as a consequence one may obtain several spectra like the adjacency, Seidel, Laplacian, signless Laplacian, normalized Laplacian, generalized adjacency and convex linear combination of the adjacency and degree diagonal matrix of ${\mathrm{\Gamma }}^{\prime }(R)$ and $\overline{{\mathrm{\Gamma }}^{\prime }(R)}$ in an unified way. Moreover, we get the universal adjacency eigenpairs of the cozero-divisor graph and its complement for a reduced ring and the ring of integers modulo $m$ in a simpler form.

Let $G=(V,E)$ be a nontrivial connected simple graph and $d(a,b)$ be the distance between the vertices $a$ and $b$ in $G$. The metric dimension of a graph $G$, denoted by dim($G$), refers to the smallest set of vertices required to uniquely identify every vertex in the graph $G$. A family of simple connected graphs say $F_s$, where $s\in \mathbb{N}$ has a constant metric dimension, if dim$(F_s)$ is finite and does not depend on the choice of $s$ in $F_s$. In this paper, we consider two infinite families of planar graphs, say $Q_s$, where $s\ge 8$ and $Z_s$, where $s\ge 6$, and investigate their metric basis as well as the metric dimension. Additionally, we prove that the metric basis for these two graphs are independent.