Discrete Mathematics, Algorithms and Applications

A connected graph $G$ is double-critical if the chromatic number of $G-x-y$ is two less than that of $G$ whenever $x$ and $y$ are two adjacent vertices of $G$. The double-critical graph conjecture states that the complete graphs are the only double-critical graphs. We give a proof of this conjecture for any double-critical graph that contains at least one universal vertex. Using this result we prove the conjecture for all double-critical graphs.

In this paper, we construct a weighted $3$-simplicial complex $S_w=(V,E,F,T,w_V,w_E,w_F,w_T)$ on a connected oriented locally finite graph $(V,E)$ by the introduction of the notion of oriented tetrahedrons $T$, the notion of oriented triangular faces $F$, a weight on $V$, a weight on $E$, a weight on $F$ and a weight on $T$. Next, we create the weighted Gauss–Bonnet operator of $S_w$ and we use it to construct the weighted Laplacian associated to $V$, the weighted Laplacian associated to $E$, the weighted Laplacian associated to $F$, the weighted Laplacian associated to $T$ and the weighted Laplacian associated to $S_w$. After that, we introduce the notion of the $\chi$-completeness of $S_w$ and we give necessary conditions for $S_w$ to be $\chi$-complete. Finally, we prove that the weighted Gauss–Bonnet operator and the weighted Laplacians are essentially self-adjoint based on the $\chi$-completeness.

The concept of associating a graph to a ring was initiated by Beck in 1988. The zero-divisor graph of a commutative ring $R$ with unity ($1\ne 0$) is defined as a simple graph, denoted by $\mathrm{\Gamma }(R)$, where elements of the ring $R$ represent vertices and two distinct vertices in $\mathrm{\Gamma }(R)$ are adjacent if the product of the corresponding elements is zero in $R$. Here, we extend the notion of zero-divisor graphs to signed graphs. We introduce four types of signing to the zero-divisor graphs. Further, we characterize rings for which these four types of signed graphs, its lined signed graphs and their negations are balanced, clusterable, sign-compatible, canonically sign-compatible, and canonically consistent.

The order two element graph of a group $G$ is the simple undirected graph whose vertex set consists of all elements of $G$ and two distinct vertices $u,v$ are adjacent if and only if either $uvorvu\in \{t^2:t\in G\}\cup \{a\in G:a^2=e\}\backslash \{e\}$, where $e$ is the identity element of $G$. We denote this graph by ${𝕊}_2(G)$. In this paper, we identify those commutative groups $G$ for which the graph ${𝕊}_2(G)$ is connected. We also characterize the structures of the graph ${𝕊}_2({\mathbb{Z}}_n)$ for any positive integer $n$. Moreover, we consider the symmetric group $S_n$, the dihedral group $D_n$ for any positive integer $n$ and for these groups, we look into the structure and other graph-theoretic properties of the corresponding graphs. Finally, we give a list of finite groups of order $\le 16$ with their corresponding order two element graph structures.

A bar visibility representation of a graph $G$ is an assignment of the vertices of $G$ to distinct horizontal line segments in the plane so that two vertices are adjacent in $G$ if and only if there is an uninterrupted vertical channel of positive width that joins the bars corresponding to those vertices. A bar visibility representation is called a unit bar visibility representation if every bar has the same length. If each vertex is assigned to $t$ distinct bars of the same length in a unit bar visibility representation then the representation is called $t$-unit bar visibility representation. In this paper, we introduce a “sliding column model” for $t$-unit bar visibility representation and show that every graph of maximum degree $\mathrm{\Delta }$ has a $t$-unit bar visibility representation for $t\le \lfloor \frac{\mathrm{\Delta }+1}{2}\rfloor$. We also show that a planar graph of maximum degree 3 having $n$ vertices and $m$ edges has a 2-unit bar visibility representation on $2n-m$ columns and a 3-connected cubic graph of $n$ vertices admits a 2-unit bar visibility representation on $\frac{n}{2}$ columns.

We introduce a new generalization of Gaussian Pell polynomials. We call it $d$-Gaussian Pell polynomials. Then we present the sum, generating functions and Binet formulas of these polynomials. We give the matrix representation of $d$-Gaussian Pell polynomials. We introduce the matrix as binary representations according to the Riordan matrix representation. Using the Riordan method, we obtain the factorizations of the Pascal matrix involving the polynomial. In addition, we present the inverse of matrices of the polynomial.

The aim of this paper is to present a study of the Moore–Penrose inverse $L^{†}$ of the Laplacian matrix of a simple and connected graph, particularly, for some families of graphs such as path, cycle, ladder, fan and wheel graphs. For this purpose, it is used diverse approaches and MP inverse of the Cartesian product of graphs, and are obtained new closed-form formulas of the $L^{†}$ of these families. A comparison of the computational efficiency of the new formulas versus traditional mathematical software is presented, showing the advantage of new formulas.

Given an ordered $k$-decomposition $D=\{G_1,G_2,\dots ,G_k\}$ of a connected graph $G=(V,E)$, the representation of an edge $e\in E$ with respect to the decomposition $D$ is the $k$-tuple $\gamma (e/D)=(d(e,G_1),d(e,G_2),\dots ,d(e,G_k))$, where $d(e,G_i)$ represents the distance from $e$ to $G_i$. A decomposition $D$ of $E$ is a resolving decomposition if for every pair of edges $e,f\in E,\gamma (e/D)\ne \gamma (f/D)$. The minimum $k$ for which $G$ has a resolving $k$-decomposition is its decomposition dimension $\mathrm{\text{dec}}(G)$. In this paper, upper bounds for the decomposition dimension of some class of graphs are determined.

In this paper, we construct an infinite family of weighted growing complex networks, namely, weighted neighborhood networks (WNN) which are constructed in an iterative way by using a base network and a sequence of growing weighted networks. We determine the weighted Laplacian spectra of WNN which is expressed in terms of the spectra of base network and the sequence of weighted regular networks. Using the weighted Laplacian spectra, we obtain the Kirchhoff index, the entire mean weighted first-passage time and the number of spanning trees of WNN. Also, we compute the weighted normalized Laplacian spectra of these networks which is expressed in terms of the spectra of regular base network and the sequence of weighted regular networks and from that, we derive the multiplicative Kirchhoff index, Kemeny’s constant and the number of spanning trees in terms of the weighted normalized Laplacian spectra.

Difference sets have wide applications in constructing sequences and codes in engineering and cryptography, and in imaging with coded masks in astronomical events and in medical events. In this paper, the relation between difference sets and binary sequences is presented and a coded mask as an application of difference sets is given. First of all, an algorithm for an appropriate difference set is written in C++ by using twin primes and then a coded mask for imaging astronomical events is designed with the aid of this algorithm.

This paper shows that the topological structures of particle orbits generated by a generic class of vector fields on spherical surfaces, called the flow of finite type, are in one-to-one correspondence with discrete structures such as trees/graphs and sequences of letters. The flow of finite type is an extension of structurally stable Hamiltonian vector fields, which appear in many theoretical and numerical investigations of two-dimensional (2D) incompressible fluid flows. Moreover, it contains compressible 2D vector fields such as the Morse–Smale vector fields and the projection of 3D vector fields onto 2D sections. The discrete representation is not only a simple symbolic identifier for the topological structure of complex flows, but it also gives rise to a new methodology of topological data analysis for flows when applied to data brought by measurements, experiments, and numerical simulations of complex flows. As a proof of concept, we provide some applications of the representation theory to 2D compressible vector fields and a 3D vector field arising in an industrial problem.

For a graph $G$, a double Roman dominating function (DRDF) is a function $f:V(G)\to \{0,1,2,3\}$ such that each vertex $v$ with $f(v)=0$ is adjacent to at least two vertices labeled $2$ or one vertex labeled $3$ and each vertex $v$ with $f(v)=1$ is adjacent to at least one vertex $x$ with $f(x)\ge 2$. The weight of $f$ is the sum of all labelings $f(v)$ and is denoted by $w(f)$. If $f$ is a DRDF on $G$ with minimum weight ${\gamma }_{dR}(G)$, then its inverse double Roman dominating function (IDRDF) $f^{\prime }$ is a DRDF on $G$, such that $f^{\prime }(v)=0,\forall v\in S$, where $S=\{v\in V(G)/f(v)>0\}$. The inverse double Roman domination number (IDRDN) of $G$, denoted by ${\gamma }_{idR}(G)$ is the minimum weight of such a function. We introduce this new type of inverse dominating function, obtain some bounds for the IDRDN of $G$. We characterize the graphs having ${\gamma }_{idR}(G)=3,4,5$ and the highest. We also present an approach for constructing graphs with the desired IDRDN.

In this paper, we use a novel approach to describe generator polynomials of quasi-cyclic (QC) and generalized QC (GQC) codes over finite fields. Our study of QC- and GQC-codes will be general and not only restricted to one-generator codes. We prove that generator polynomials of QC-codes and GQC-codes are unique. Further, we use our results to obtain an expression for the dimensions of QC-codes and GQC-codes. As an application of our construction of these codes, we obtain many optimal linear codes over finite fields $\mathrm{\text{GF}}(2),\mathrm{\text{GF}}(3),\mathrm{\text{GF}}(4)$ and $\mathrm{\text{GF}}(5)$.

Several reasonably cyclotomic sequences are constructed by cyclotomic classes having good pseudo-randomness property. In this paper, we derive the linear complexity of an extended binary cyclotomic sequences of order $2^{l}t$ over finite field having period $pq$. Our result shows that these sequences have higher linear complexity, which can resist linear attack.

In this paper, we analyze the intersection graphs of subtrees in a cactus, called cactus subtree graphs. A max-k-clique subgraph of a graph is an induced subgraph whose maximum clique has at most $k$ vertices. We describe a polynomial time algorithm to find a maximum weight max-$k$-clique subgraph in a cactus subtree graph when $k$ is fixed. In perfect graphs this problem is equivalent to the maximum weight $k$-colorable subgraph problem. In many applications like scheduling production lines and communication networks on imperfect graphs, a maximum max-$k$-clique subgraph solution is better than a maximum $k$-colorable subgraph solution. In addition, we describe cactus subtree graphs polynomial time algorithms for recognition, maximum independent sets, maximum cliques, maximum induced bipartite graphs, maximum induced forests and minimum feedback vertex sets.

Let $G$ be a simple graph and connected. A function $l:V(G)\to \{1,2,\dots ,k\}$ is called vertex irregular $k$-labeling and $w:V(G)\to N$ where $w(u)={\sum }_{v\in N(u)}l(v).$ The function of $f$ is called local irregular vertex coloring if every $uv\in E(G),w(u)\ne w(v)$ and $\mathrm{\text{opt}}(l)=min\{max{l}_i;l_i$ vertex irregular labeling}. The local irregular chromatic number is denoted by ${\chi }_{\mathrm{\text{lis}}}(G).$ In this paper, we study local irregular vertex coloring of $S_m{▹}_{v_0}{S}_n,S_m{▹}_{v_1}{S}_n$, and $S_m{▹}_{v_1}{P}_n.$