Discrete Mathematics, Algorithms and Applications

Turán theorem states that the Turán graph $T_{n,r}$ is the unique graph which has the maximum edge number among the $K_{r+1}$-free graphs of order $n$. In this paper, we prove that $T_{n,r,h}=\overline{K_h}\vee T_{n-h,r-1}$ has both the maximum number of maximal cliques and the maximum spectral radius among all graphs of order $n$ with $I_r(G)=h>0$ and $I_{r+1}(G)=0$, where $I_t(G)$ stands for the maximum number of disjoint $t-$cliques of $G$.

In this paper, we consider the discrete unit square cover (DUSC) problem as follows: given a set ${𝒫}$ of $n$ points and a set ${𝒮}$ of $m$ axis-aligned unit squares in ${ℝ}^2$, the objective is (i) to check whether the union of the squares in ${𝒮}$ covers all the points in ${𝒫}$, and (ii) if the answer is yes, then select a minimum cardinality subset ${{𝒮}}^{\ast }\subseteq {𝒮}$ such that each point in ${𝒫}$ is covered by at least one square in ${{𝒮}}^{\ast }$. For the DUSC problem:

• ⁽ⁱ⁾we propose a $(2+\frac{4}{k-2})$-approximation algorithm, where $k(>2)$ is an integer parameter that defines a trade-off between the running time and the approximation factor of the algorithm. The running time of our proposed algorithm is $O(k{m}^{k}n+nlogn)$. Our solution of the DUSC problem is based on a simple $(1+\frac{2}{k-2})$-approximation algorithm for the subproblem strip square cover (SSC) problem, where all the points in ${𝒫}$ are lying within a horizontal strip of unit height.
• ⁽ⁱⁱ⁾we also propose a 2-approximation algorithm, which runs in $O(m^{4}n)$ time. The 2-approximation algorithm is based on an algorithm for the subproblem SSC problem. The algorithm for the subproblem is developed using plane sweep and graph search traversal techniques. We also extend this algorithm to get 2-approximation result for the weighted DUSC problem where the squares are assigned weights, and the aim is to choose a subset ${{𝒮}}^{\ast }\subseteq {𝒮}$ such that each point in ${𝒫}$ is covered by at least one square in ${{𝒮}}^{\ast }$ and the sum of the weights of squares in ${{𝒮}}^{\ast }$ is minimized.

Ideal flow network is a strongly connected network with flow, where the flows are in steady state and conserved. The matrix of ideal flow is premagic, where vector, the sum of rows, is equal to the transposed vector containing the sum of columns. The premagic property guarantees the flow conservation in all nodes. The scaling factor as the sum of node probabilities of all nodes is equal to the total flow of an ideal flow network. The same scaling factor can also be applied to create the identical ideal flow network, which has from the same transition probability matrix. Perturbation analysis of the elements of the stationary node probability vector shows an insight that the limiting distribution or the stationary distribution is also the flow-equilibrium distribution. The process is reversible that the Markov probability matrix can be obtained from the invariant state distribution through linear algebra of ideal flow matrix. Finally, we show that recursive transformation $F_k\to F_{k+1}$ to represent $k$-vertices path-tracing also preserved the properties of ideal flow, which is irreducible and premagic.

Let $G_1,G_2$ and $H$ be three graphs on disjoint sets of vertices and $G_1$ has $m_1$ edges. Let $S(G_1,H)$ be the graph obtained from $G_1$ and $H$ in the following way:

(1) Delete all the edges of $G_1$ and consider $m_1$ disjoint copies of $H$.

(2) Join each vertex of the $i$th copy of $H$ to the end vertices of the $i$th edge of $G_1$.

Let $G_1({\vee }_H)G_2$ be the graph obtained from $S(G_1,H)$ by joining each vertex of $G_1$ with each vertex of $G_2.$ In this paper, we determine the adjacency (respectively, Laplacian, signless Laplacian) spectrum of $G_1({\vee }_H)G_2$ in terms of those of $G_1,G_2$ and $H.$ As an application, we construct infinite pairs of cospectral graphs.

In this paper, we use multiple guard movements to defend the edges of a graph $G$ against a single attack. At most, one guard is positioned at each vertex. To defend an attack on an edge, a guard at an incident vertex moves across the attacked edge and the other guards may move (or not) to the neighboring vertices to better configure themselves. This strategy requires the set of vertices containing guards to be a vertex cover before and after an attack. A suitable placement of guards is called an $m$-secure vertex cover of $G$. We call this the $m$-secure vertex cover problem, where $m$ stands for the multiple guard movements. The minimum number of guards required to defend the edges of $G$ against a single attack using multiple guard movements is called the $m$-secure vertex covering number and it is denoted by ${\alpha }_m(G)$. In this paper we initiate a study of this parameter.

Let $H$ be a simple graph with $n$ vertices and $G$ be a sequence of $n$ rooted graphs $G_1,G_2,\dots ,G_n$. The rooted product $H(G)$, of $H$ by $G$ is constructed by identifying the root vertex of $G_i$ with the $i$th vertex of $H$ for $1\le i\le n$. In this paper, we introduce a method for computation of the characteristic polynomial of the signless Laplacian matrix of $H(G)$. Then the signless Laplacian spectrum and the signless Laplacian energy of some graphs will be computed.

Topological descriptors are numerical parameters of a molecular graph which characterize its molecular topology and are usually graph invariant. In QSAR/QSPR study, physico-chemical properties and topological indices such as Randić, atom-bond connectivity $(ABC)$ and geometric-arithmetic (GA) index are used to predict the bioactivity of chemical compounds. Graph theory has found a considerable use in this area of research. The counting polynomials are those polynomials having at exponent the extent of a property partition and coefficients the multiplicity/occurrence of the corresponding partition. All of the studied interconnection mesh networks in this paper are motivated by the molecular structure of a Sodium chloride NaCl.

In this paper, Omega, Sadhana and PI polynomials are computed for mesh-derived networks. These polynomials were proposed on the ground of quasi-orthogonal cut edge strips in polycyclic graphs. These polynomials count equidistant and non-equidistant edges in graphs. Moreover, the analytical closed formulas of these polynomials for mesh-derived networks are computed for the first time.

Subspace code is very useful in the error correction for random network coding. In this paper, subspace code based on flats in affine space over finite fields is constructed. Sphere-packing bound, Wang–Xing–Safavi-Naini bound, anticode bound, Ahlswede–Aydinian bound and Gilbert–Varshamov bound for the size of code based on flats in affine space over finite fields are provided. Finally, we introduce another method of obtaining the anticode bound for the size of code based on flats in affine space from Erdős–Ko–Rado theorem.

We construct binary and ternary Linear Complementary Dual (LCD) codes with parameters ${[2^n-{\sum }_{i=1}^s{2}^{u_i}+s-1,n,2^{n-1}-{\sum }_{i=1}^s{2}^{u_i-1}]}_2$ and ${[\frac{3^n-1}{2},n,3^{n-1}-n]}_3$, where $u_i\le 2$ and ${\sum }_{i=1}^s{u}_i=n$. Further, we derive and study properties of a class of two, three and four weight codes $C[n;u_1,u_2]$. We show that under suitable conditions $C[n;u_1,u_2]$ codes are self-orthogonal and satisfy the Griesmer bound.

Let $f(u)$ be a polynomial of degree $m,m\ge 2,$ which splits into distinct linear factors over a finite field ${𝔽}_q$. Let ${ℛ}={𝔽}_q[u]/〈f(u)〉$ be a finite non-chain ring. In an earlier paper, we studied duadic and triadic codes over ${ℛ}$ and their Gray images. Here, we study duadic negacyclic codes of Type I and Type II over the ring ${ℛ}$, their extensions and their Gray images. As a consequence some self-dual, isodual, self-orthogonal and complementary dual (LCD) codes over ${𝔽}_q$ are constructed. Some examples are also given to illustrate this.

At Eurocrypt ’02, Cramer and Shoup introduced the idea of public key encryption schemes with double decryption mechanism (DD-PKE) and at Asiacrypt ’03, Bresson, Catalano and Pointcheval revisited the notion of DD-PKE. They proposed the first DD-PKE scheme (called BCP cryptosystem) over the group of quadratic residues. In this paper, we point out an attack against BCP cryptosystem and propose a secure variant constructed over the group of signed quadratic residues (SQR).

Let $G$ be a simple graph of order $n.$ Let $c=a+b\sqrt{m}$ and $\overline{c}=a-b\sqrt{m},$ where $a$ and $b$ are two nonzero integers and $m$ is a positive integer such that $m$ is not a perfect square. In [M. Lepovi$ć$, On conjugate adjacency matrices of a graph, Discrete Mathematics 307 (2007) 730–738], the author defined the matrix $A^c(G)={[c_{ij}]}_n$ to be the conjugate adjacency matrix of $G,$ if $c_{ij}=c$ for any two adjacent vertices $i$ and $j,c_{ij}=\overline{c}$ for any two nonadjacent vertices $i$ and $j,$ and $c_{ij}=0$ if $i=j.$ In this paper, we define conjugate Laplacian matrix of graphs and describe various properties of its eigenvalues and eigenspaces. We also discuss the conjugate Laplacian spectra for union, join and Cartesian product of graphs.

Self-orthogonal codes play an important role in constructing quantum-error-correcting codes. In this paper, we prove that if quasi-symmetric 2-(41, 9, 9) design exists, then it arises from self-orthogonal and self-complementary $[41,19,8]$ codes with dual distance of at least 5. Moreover, we emphasize the enumeration of inequivalent doubly-even codes with the needed dual distance and an automorphism of order 7. This is found to be precisely 8.

The $p$-competition graph $C_p(D)$ of a digraph $D=(V,A)$ is a graph with $V(C_p(D))=V(D)$, where for distinct vertices $x$ and $y$, $xy\in E(C_p(D))$ if and only if there exist distinct $p$ vertices $v_1,v_2,\dots ,v_p\in V(D)$ such that $x\to v_i$, $y\to v_i$ are arcs of the digraph $D$ for each $i=1,2,\dots ,p$. In this paper, we show that spiders $S_{m,n}$ are $p$-competition graphs, where $p\le n-2$ and $m$ is even.