Discrete Mathematics, Algorithms and Applications

In this paper, we will introduce “Riesel” numbers and we show closed formulae for calculating the $n$th “Riesel” number $R_n$, the number of “Riesel” numbers up to $n$, and the sum of the first $n$ “Riesel” numbers. We will explore the relationships between the selected numbers and solve two special cases of diophantine equations.

An antimagic labeling of a simple graph $G$ is a bijection $\tau :E(G)\to \{1,2,\dots ,|E(G)|\}$ such that ${\sum }_{e\in E(u)}\tau (e)\ne {\sum }_{e\in E(v)}\tau (e)$ for any two vertices $u,v$ in $G$. We survey the results about antimagic labelings and other labelings motivated by antimagic labelings of graphs, and present some conjectures and open questions.

The crossing number of a graph $G$, denoted by $\mathrm{\text{cr}}(G)$, is defined to be the minimum number of crossings that arise among all its drawings in the plane. This concept has been of interest to many researchers who have studied it for many families of graphs. In this paper, we introduce the crossing number of Cartesian product of sunlet graph $S_m$ with path $P_n$. Further, we prove that the crossing number of $S_m\square P_2$ is equal to $m$, along with giving a conjecture for the general case. In addition, we utilize the vertex’s rotation concept in order to prove some necessary conditions for the complete bipartite graph $K_{m,n}$ to be optimal when it is drawn in the plane, by presenting an upper bound for the crossing number of any subgraph in it together with determining the exact number of crossings in case the vertices of subgraph have the same rotation.

The eccentricity matrix ${ℰ}(G)=({𝜀}_{uv})$ of a graph $G$ is constructed from the distance matrix by keeping each row and each column only the largest distances with

The graph parameter neighbor-connectivity was first investigated by Gunther and Hartnell in 1987 and provides important information on how reliable a network can be when failures of a node may impact its neighbors. In this model, the failure of a node causes the deletion of its closed neighborhood, i.e., the node and its adjacent neighbors as well. The minimum number of closed neighborhoods whose removal results in an empty, complete, or disconnected subgraph is called the neighbor-connectivity of the graph. Since then component order connectivity models have emerged to address inadequacies in the traditional models of connectivity, namely, that in many real-world networks, when disconnecting a graph one may be left with components that are large enough to still be operable. By adapting neighbor-connectivity to a component order model, we introduced neighbor-component order connectivity, defined as the minimum number of closed neighborhoods that must be removed from a network to ensure all remaining components have order less than some given threshold value. Given a threshold value of one, the neighbor-component order connectivity of a graph is equivalent to the well-known parameter domination number of the graph. The problem of computing the domination number of an arbitrary graph is NP-hard, and computing neighbor-component order connectivity of a graph for an arbitrary threshold value is also NP-hard. Here, we present a linear-time algorithm for computing the neighbor-component order connectivity of an arbitrary tree for an arbitrary threshold value, thus generalizing the classic linear algorithm of Cockayne, Goodman, and Hedetniemi for the domination number of the tree.

Let $D=(V(D),E(D))$ be a simple digraph and a bijection $f:V(D)\to \{1,2,3,\dots ,n\}$. The labeling $f$ induces on arc labeling $f^{\prime }:E(D)\to \{1,-1,0\}$ such that for any arc $\overrightarrow{uv}$ in $E(D)$, $f^{\prime }(\overrightarrow{uv})=(u/v)$, where $(u/v)$ is the Jacobi symbol. Let $e_{f^{\prime }}(i)$ be the number of arcs labeled with $i\in \{1,-1,0\}$. The labeling $f$ is called a Jacobi symbol labeling if $f^{\prime }(\overrightarrow{uv})=1$ for all $\overrightarrow{uv}\in E(D)$. Moreover, $D$ is Jacobi symbol digraph if it admits Jacobi symbol labeling. The labeling $f$ is called a Jacobi symbol cordial labeling if $|e_{f^{\prime }}(1)-e_{f^{\prime }}(-1)|\le 1$. Moreover, $D$ is Jacobi symbol cordial digraph if it admits Jacobi symbol cordial labeling. The labeling $f$ is called a Jacobi symbol 3-equitable labeling if $|e_{f^{\prime }}(i)-e_{f^{\prime }}(j)|\le 1$ for all $-1\le i,j\le 1$. A digraph which admits a Jacobi symbol 3-equitable labeling is called a Jacobi symbol 3-equitable digraph. In this paper, we will find out some Jacobi symbol digraphs, Jacobi symbol cordial digraphs and Jacobi symbol 3-equitable digraphs.

Let $H=(V,E)$ be a connected graph of size $n$. If $W$ is an ordered subset of distinct vertices in $H$ then the subset $W$ is said to be a resolving set for $H$, if all of the vertices in the graph can be uniquely defined by the vector of distances to the vertices in $W$. A resolving set $W$ with minimum possible vertices is said to be a metric basis for $H$. The cardinality of the metric basis is called the metric dimension of the graph $H$. In this paper, we demonstrate that the metric dimension for some families of related planar graphs is three.

In this paper, we investigate the structure and properties of skew negacyclic codes and skew quasi-negacyclic codes over the ring $R={\mathbb{Z}}_q+u{\mathbb{Z}}_q,u^2=0.$ Some structural properties of $R[x,\mathrm{\Theta }]$ are discussed, where $\mathrm{\Theta }$ is an automorphism of $R.$ A skew quasi-negacyclic code of length $s\ell$ with index $\ell$ over $R$ is viewed both as in the conventional row circulant form and also as an $R[x,\mathrm{\Theta }]/(x^s+1)$-submodule of $GR(R,\ell )[x,\delta ]/(x^s+1)$, where $GR(R,\ell )$ is the Galois extension ring of degree $\ell$ over $R$ and $\delta$ is an automorphism of $GR(R,\ell ).$ A sufficient condition for one generator skew quasi-negacyclic codes to be free is determined. Some distance bounds for free one generator skew quasi-negacyclic codes are discussed. Furthermore, given the decomposition of a skew quasi-negacyclic code, we provide the decomposition of its dual code. As a result, a characterization of self-dual skew quasi-negacyclic codes over $R={\mathbb{Z}}_q+u{\mathbb{Z}}_q$ is provided. By using computer search we obtained a number of new linear codes over ${\mathbb{Z}}_4$ from skew negacyclic and skew quasi-negacyclic codes over ${\mathbb{Z}}_4+u{\mathbb{Z}}_4$.

In 2012, Ponraj et al. defined k-product cordial labeling as follows: Let $f$ be a map from $V(G)$ to $\{0,1,\dots ,k-1\}$ where $k$ is an integer, $1\le k\le |V(G)|$. For each edge $uv$ assign the label $f(u)f(v)$ $(\mathrm{\text{mod }}k)$. $f$ is called a k-product cordial labeling if $|v_f(i)-v_f(j)|\le 1$, and $|e_f(i)-e_f(j)|\le 1$, $i,j\in \{0,1,\dots ,k-1\}$, where $v_f(x)$ and $e_f(x)$ denote the number of vertices and edges, respectively, labeled with $x$ $(x=0,1,\dots ,k-1)$. A graph that admits k-product cordial labeling is called k-product cordial graph. Later, we proved that several families of graphs are k-product cordial graphs. In this paper, we show that the product of graphs admit k-product cordial labeling.

A dominator coloring of a graph $G$ is a proper vertex coloring with a domination property that each vertex dominates a color class. The minimum number of colors used in a dominator coloring of $G$ is called dominator chromatic number of $G$ and is denoted as ${\chi }_d(G)$. Graphs with ${\chi }_d(G)\le 3$ have characterizations and such graphs can be recognized in polynomial time. However, for $k\ge 4$, deciding whether ${\chi }_d(G)\le k$ is NP-hard. In this paper, we investigate the computational complexity of minimum $q$-dominator partization problem (Min-$q$-D-Partz). In Min-$q$-D-Partz, given a graph $G$, the objective is to find a vertex set $S$ of minimum size such that ${\chi }_d(G[V\setminus S])\le q$. We prove that Min-$2$-D-Partz is APX-complete and has a two-factor approximation algorithm. We also prove that Min-$3$-D-Partz cannot be approximated within any constant factor and can be approximated within a factor of $O(\sqrt{logn})$.

An injective $k$-edge coloring of a graph $G$ is a $k$-edge coloring $\phi$ of $G$ such that $\phi (e_1)\ne \phi (e_3)$ for any three consecutive edges $e_1,e_2$ and $e_3$ of a path or a 3-cycle. The injective edge chromatic index of $G$, denoted by ${\chi }_i^{\prime }(G)$, is the minimum $k$ such that $G$ has an injective $k$-edge coloring. Li and Chen determined the injective edge chromatic index of the generalized Petersen graph $P(n,k)$ for $1\le k\le 2$. In this paper, we consider the injective edge coloring of the generalized Petersen graph $P(ck,k)$ and show that ${\chi }_i^{\prime }(P(ck,k))\le 5$ for $k\ge 3$.

Let $R$ be a finite commutative ring with identity, $I$ be an ideal of $R$ and $J(R)$ denotes the Jacobson radical of $R$. The ideal-based zero-divisor graph ${\mathrm{\Gamma }}_I(R)$ of $R$ is a graph with vertex set $V({\mathrm{\Gamma }}_I(R))=\{x\in R-I:xy\in I,$ for some $y\in R-I\}$ in which distinct vertices $x$ and $y$ are adjacent if and only if $xy\in I$. In this paper, we determine the diameter, girth of ${\mathrm{\Gamma }}_{J(R)}(R)$. Specifically, we classify all finite commutative nonlocal rings for which ${\mathrm{\Gamma }}_{J(R)}(R)$ is perfect. Furthermore, we discuss about the planarity, outerplanarity, genus and crosscap of ${\mathrm{\Gamma }}_{J(R)}(R)$ and characterize all of them.

[M. Ma, The connectivity of exchanged hypercubes, Discrete Math., Algorithms Appl. 2(2) (2010) 213–220.] proved that the vertex connectivity and the edge connectivity of the exchanged hypercube are each equal to the minimum degree of the graph. This paper presents a proof of that result, which is substantially simpler and more intuitive.

In this paper, we use IVI-octahedron ideals and IVI-octahedron bi-ideals to discuss some characterizations of special semigroups, e.g., an intra-regular semigroup, a semigroup which is semilattice of left [respectively, right] simple semigroups or simple left groups and a semigroup which is a semilattice of groups and a [respectively, left and right] simple semigroups. Finally, we define an IVIO-simple [IVIOL-simple and IVI) R-simple] semigroup and study some of its properties and we give a characterization of a semisimple semigroup by IVIOIs.

A graph $\mathrm{\Gamma }$ on $n$ vertices is called a hyperenergetic graph if $E(\mathrm{\Gamma })>2(n-1)$ where $E(\mathrm{\Gamma })$ is the energy of $\mathrm{\Gamma }$. In this paper, we consider hyperenergetic Cayley graphs. In detail, for any abelian group $G$, we construct a class of Cayley graphs over $G$, in which almost all are hyperenergetic. Furthermore, we also construct such a class of Cayley graphs over the dihedral group.

Let $G$ be a connected simple graph. A dominating subset $S$ of $V(G)$ is a fair dominating set of $G$ if all the vertices not in $S$ are dominated by the same number of vertices from $S$. Let $D$ be a minimum fair dominating set of $G$. A fair dominating set $S\subseteq (V(G)\setminus D)$ is called an inverse fair dominating set of $G$ with respect to $D$. The inverse fair domination number of $G$ denoted by ${\gamma }_{\mathrm{\text{fd}}}^{-1}(G)$ is the minimum cardinality of an inverse fair dominating set of $G$. In this paper, we investigate the concept and give some important results. Further, we give the characterization of an inverse fair dominating set in the join and corona of two graphs.