Discrete Mathematics, Algorithms and Applications

A perfect $t$-code in a graph $\mathrm{\Gamma }$ is a subset ${𝒞}$ of $V(\mathrm{\Gamma })$ such that every vertex of $\mathrm{\Gamma }$ is at a distance not more than $t$, to exactly one vertex of ${𝒞}$. In this paper, we present a new family of perfect $t$-codes in Cayley graphs of groups. We proposed the role of the subgroups of a group to create perfect $t$-codes by restricting the elements of the left transversal of the subgroups in the given group. Also, we introduce a new decoding algorithm for the all of perfect $t$-codes in Cayley graphs. These codes are able to correct every $t$-error pattern.

A Roman dominating function (RDF) on a graph $G$ is a function $f:V(G)\to \{0,1,2\}$ satisfying the condition that every vertex u for which $f(u)=0$ is adjacent to at least one vertex v for which $f(v)=2$. A vertex $u$ with $f(u)=0$ is undefended if it is not adjacent to a vertex with $f(v)>0$. The function $f:V(G)\to \{0,1,2\}$ is a weak Roman dominating function (WRDF) if each vertex $u$ with $f(u)=0$ is adjacent to a vertex $v$ with $f(v)>0$ such that the function $f^{\prime }:V(G)\to \{0,1,2\}$ defined by $f^{\prime }(u)=1$, $f^{\prime }(v)=f(v)-1$ and $f^{\prime }(w)=f(w)$ if $w\in V-\{u,v\}$ has no undefended vertex. The Roman domination subdivision number of a graph $G$ is the minimum number of edges that must be subdivided in order to increase the Roman domination number of $G$. We introduce the concept of weak Roman subdivision number of a graph $G$, denoted by ${\mathrm{\text{sd}}}_{\gamma r}(G)$ as the minimum number of edges that must be subdivided in order to increase the weak Roman domination number of $G$. In this paper, we determine the exact values of the weak Roman subdivision number for paths, cycles and complete bipartite graphs. We obtain bounds for the weak Roman subdivision number of a graph and characterize the extremal graphs.

Given a graph $G=(V,E)$ and a finite set $T$ of positive integers containing $0,$ a $T$-coloring of $G$ is a function $f:V(G)\to Z^{+}\cup \{0\}$ for all $u\ne w$ in $V(G)$ such that if $uw\in E(G)$ then $|f(u)-f(w)|\notin T.$ For a $T$-coloring $f$ of $G$, the $f$-span ${\mathrm{\text{sp}}}_T^f(G)$ is the maximum value of $|f(u)-f(w)|$ over all pairs $u,w$ of vertices of $G.$ The $T$-span ${\mathrm{\text{sp}}}_T(G)$ is the minimum $f$-span overall $T$-colorings of $G$. The $f$-edge span of a $T$-coloring ${\mathrm{\text{esp}}}_T^f(G)$ is the maximum value of $|f(u)-f(w)|$ over all edges $uw$ of $G$. The $T$-edge span ${\mathrm{\text{esp}}}_T(G)$ is the minimum $f$-edge span overall $T$-colorings of $G$. This paper discusses the $T$-span and $T$-edge span of Cartesian, Join, Union and Tensor products of graphs. Also, we discuss the relation between Restricted span and Restricted edge span of graphs.

In this paper we compare the performance of two algebraic geometry codes (Suzuki and Hermitian codes) constructed using maximal algebraic curves over ${𝔽}_{q^4}$ with large automorphism groups by choosing specific divisors. We discuss their parameters, compare the rate of these codes as well as their relative minimum distances, and we show that both codes are asymptotically good in terms of the rate which is in contrast to their behavior in terms of the relative minimum distance.

In this paper, we introduce a new statistic on standard Young tableaux that is closely related to the maxdrop permutation statistic that was introduced by the first author. We prove that the value of the statistic must be attained at one of the corners of the standard Young tableau. We determine the coefficients of the generating function of this statistic over two-row standard Young tableaux having $n$ cells. We prove several results for this new statistic that include unimodality of the coefficients for the two-row case.

It is well known that there exist 22 symmetry type graphs associated to $4$-orbit maps. For this one, we give the feasible values taken by the degree of the vertices and the number appropriate of edges in the boundary of each face of the map, by introducing the concepts of vertex type graph, face type graph and characteristic system.

In various scenarios today, the generation of random permutations has become an indispensable tool. Since random permutation of dimension $n$ is a random element of the symmetric group $S_n$, it is necessary to have algorithms capable of generating any permutation. This work demonstrates that it is possible to generate the symmetric group $S_{n^2}$ by shifting the components of a particular matrix representation of each permutation.

Let $G$ be a simple undirected graph with vertex set $V(G)=\{v_1,v_2,\dots ,v_n\}$. The arithmetic–geometric matrix ${{𝒜}}_{\mathrm{\text{ag}}}(G)$ of a graph $G$ is defined so that its $(i,j)$-entry is equal to $\frac{d_i+d_j}{2\sqrt{d_i{d}_j}}$ if the vertices $v_i$ and $v_j$ are adjacent, and zero otherwise, where $d_i$ denotes the degree of vertex $v_i$ in $G$. In this paper, some bounds on the arithmetic–geometric spectral radius and arithmetic–geometric energy are obtained, and the respective extremal graphs are characterized. Moreover, some bounds for the arithmetic–geometric Estrada index involving arithmetic–geometric energy of graphs are determined. Finally, a class of arithmetic–geometric equienergetic graphs is constructed by graph operations.

We say that a square real matrix $M$ is off-diagonal nonnegative if and only if all entries outside its diagonal are nonnegative real numbers. In this paper, we show that for any off-diagonal nonnegative symmetric matrix $M$, there exists a nonnegative symmetric matrix $\widehat{M}$ which is sparse and close in spectrum to $M$.

Let $A(n,d)$ be the size of the maximum binary code of length $n$ and minimum Hamming distance $d$. $A(n,d,w)$ is defined similarly for binary code with constant weight $w$. Obviously, finding the value of $A(n,d)$ is equivalent to finding the maximum independent set of the $d-1$th-power of $n$-dimensional hypercube. Based on this, this paper obtains that $A(3m,2m)=4$, $A(\frac{m(m+1)}{2},2m-2,m)=m+1$, $A(2^{m+1}-2,2^m-1)=2^{m+1}$, and explores the structure of the maximum code of length $2^{m+2}$ and minimum Hamming distance $2^{m+1}$, where $m$ is an integer.

This paper proves that for any integer $k\ge 1$, every planar graph $G$ of girth at least $8k-3$ has fractional DP-chromatic number at most $2+\frac{1}{k}$.

Let $G$ be a graph of which $A$ be the adjacency matrix and $D$ be a diagonal matrix whose diagonal entries are the degrees of vertices of $G$. $Q=A+D$ is known as the signless Laplacian matrix of the graph $G$. For any real $\alpha \in [0,1],A_{\alpha }$ matrix is defined by the convex combination $\alpha D+(1-\alpha )A$ of $D$ and $A$. Clearly, $A_{\alpha }$ coincides with $A$ for $\alpha =0$ and coincides with $Q/2$ for $\alpha =1/2$. Thus, the $A_{\alpha }$ eigenvalues are generalizations of adjacency eigenvalues and signless Laplacian eigenvalues.

In this paper, we have obtained the $A_{\alpha }$ spectra of corona and edge corona of two graphs. We have also shown that $A_{\alpha }$ cospectral graphs and $\alpha$ equienergetic graphs can be obtained from there.

In this paper, we study skew cyclic codes over the ring ${ℛ}={𝔽}_q[u,v,w]/〈u^2-1,v^2-1,w^2-1,uv-vu,vw-wv,wu-uw〉$ where $q=p^m$; $p$ is an odd prime. Here, the structural properties, generating polynomials and idempotent generators of the skew cyclic codes are obtained. Also, we show that the Gray images of skew cyclic codes of length $n$ over ${ℛ}$ are skew 8-quasi-cyclic codes of length $8n$.

In this paper, we introduce a new graph product, namely, bowtie product. We determine the generalized characteristic polynomial of the bowtie product of graphs and consequently, we obtain the characteristic polynomial of the adjacency martix, the Laplacian matrix, the signless Laplacian matrix and the normalized Laplacian matrix of this graph. Also, from these results, we obtain the $L$-spectra of some families of bowtie product of graphs. As an application, we obtain infinite pairs of $L$-cospectral graphs and construct infinite number of $L$-integral graphs.

Computing topological indices of graphs is a fundamental and classical topic. Let $G$ be a connected graph. The revised Szeged index $S{z}^{\ast }(G)$ is defined as $S{z}^{\ast }(G)={\sum }_{e=uv\in E(G)}(n_u(e|G)+\frac{n_0(e|G)}{2})(n_v(e|G)+\frac{n_0(e|G)}{2})$, where $n_u(e|G)$ (respectively, $n_v(e|G)$) is the number of vertices whose distance to vertex $u$ (respectively, $v$) is smaller than the distance to vertex $v$ (respectively, $u$), and $n_0(e|G)$ is the number of vertices equidistant from both ends of $e$. In this paper, we determine the smallest revised Szeged index among all conjugated unicyclic graphs (i.e., unicyclic graphs with perfect matchings), and the corresponding extremal graphs are characterized.

If the availability of colors to color a graph $G$ is less than that of the chromatic number $\chi (G)$ of the graph, then coloring the graph with available colors, say $k$ colors, where $1\le k\le \chi (G)-1$, will cause the end vertices of at least one edge to be colored with same color. Such an edge whose end vertices receive a same color is called as a bad edge. A coloring that restricts few color classes to have adjacency between the elements in it so as to minimize the number of bad edges obtained from it in a graph $G$ is called as a near proper coloring and a near proper coloring that uses $k$ colors where $1\le k\le \chi (G)-1$ to color a graph $G$ by permitting only one color class to have adjacency among the elements in it and thereby minimize the number of bad edges resulting from the permitted color class is called as a ${\delta }^{(k)}$-coloring of the graph $G$. In this paper, we determine the number of bad edges of powers of helm graphs $H_{1,n}^r$ and powers of closed helm graphs $C{H}_{1,n}^r$.