Discrete Mathematics, Algorithms and Applications

Let $G=(V,E)$ be a simple graph with vertex set $V$ and edge set $E$. An outer-paired dominating set $S$ of a graph $G$ is a dominating set such that the subgraph induced by $V\backslash S$ has a perfect matching. The outer-paired domination number of $G$, denoted by ${\tilde{\gamma }}_{\mathrm{\text{pr}}}(G)$, is the minimum cardinality of an outer-paired dominating set of $G$. In this paper, we study the outer-paired domination number of graphs and present some sharp bounds concerning the invariant. Also, we characterize all the trees with ${\tilde{\gamma }}_{\mathrm{\text{pr}}}(G)=n-2$.

A $C_4{C}_8$ net is a trivalent decoration made by alternating square $C_4$ and octagons $C_8$. It can cover either a cylinder or a tori. Cayley graph $\mathrm{\text{Cay}}(G,S)$ on a group $G$ with connection set $S$ has the elements of $G$ as its vertices and an edge joining $g$ and $sg$ for all $g\in S$ and $s\in S$. Motivated by Afshari’s work, we show that the $C_4{C}_8(S)[n,n]$ tori are Cayley graphs by constructing a regular subgroup of the automorphism group of $C_4{C}_8(S)[n,n]$.

In this paper, we investigate the linear dynamical system $f:{\mathbb{Z}}_{p^t}^2\to {\mathbb{Z}}_{p^t}^2$, where ${\mathbb{Z}}_{p^t}$ is the ring of integers modulo $p^t$ ($p$ is a prime). In order to facilitate the visualization of this system, we associate a graph $\mathrm{\Gamma }(A)$ on it, whose nodes are the points of ${\mathbb{Z}}_{p^t}^2$, and for which there is an arrow from $\alpha$ to $\beta$, when $\alpha A=\beta$ for a fixed $2\times 2$ matrix $A$. In this paper, the in-degree of each node in $\mathrm{\Gamma }(A)$ is obtained, and a complete description of $\mathrm{\Gamma }(A)$ is given, when $A$ is an idempotent matrix, or a nilpotent matrix, or a diagonal matrix. The results in this paper generalize Elspas’ [1959] and Toledo’s [2005].

The eccentric connectivity index and second Zagreb eccentricity index are well-known graph invariants defined as the sums of contributions dependent on the eccentricities of adjacent vertices over all edges of a connected graph. The coindices of these invariants have recently been proposed by considering analogous contributions from the pairs of non-adjacent vertices. Here, we obtain several lower and upper bounds on the eccentric connectivity coindex and second Zagreb eccentricity coindex in terms of some graph parameters such as order, size, number of non-adjacent vertex pairs, radius, and diameter, and relate these invariants to some well-known graph invariants such as Zagreb indices and coindices, status connectivity indices and coindices, ordinary and multiplicative Zagreb eccentricity indices, Wiener index, degree distance, total eccentricity, eccentric connectivity index, second eccentric connectivity index, and eccentric-distance sum. Moreover, we compute the values of these coindices for two graph constructions, namely, double graphs and extended double graphs.

In this paper, a new definition of graph domination called “Captive Domination” is introduced. The proper subset of the vertices of a graph $G$ is a captive dominating set if it is a total dominating set and each vertex in this set dominates at least one vertex which doesn’t belong to the dominating set. The inverse captive domination is also introduced. The lower and upper bounds for the number of edges of the graph are presented by using the captive domination number. Moreover, the lower and upper bounds for the captive domination number are found by using the number of vertices. The condition when the total domination and captive domination number are equal to two is discussed and obtained results. The captive domination in complement graphs is discussed. Finally, the captive dominating set of paths and cycles are determined.

Permutations are discrete structures that naturally model a genome where every gene occurs exactly once. In a permutation over the given alphabet $\mathrm{\Sigma }$, each symbol of $\mathrm{\Sigma }$ appears exactly once. A transposition operation on a given permutation $\pi$ exchanges two adjacent sublists of $\pi$. If one of these sublists is restricted to be a prefix then one obtains a prefix transposition. The symmetric group of permutations with $n$ symbols derived from the alphabet $\mathrm{\Sigma }=\{0,1,2,\dots ,(n-1)\}$ is denoted by $S_n$. The symmetric prefix transposition distance between ${\pi }^{\star }\in S_n$ and ${\pi }^{\#}\in S_n$ is the minimum number of prefix transpositions that are needed to transform ${\pi }^{\star }$ into ${\pi }^{\#}$. It is known that transforming an arbitrary ${\pi }^{\star }\in S_n$ into an arbitrary ${\pi }^{\#}\in S_n$ is equivalent to sorting some ${\pi }^{\prime }\in S_n$. Thus, upper bound for transforming any ${\pi }^{\star }\in S_n$ into any ${\pi }^{\#}\in S_n$ with prefix transpositions is simply the upper bound to sort any permutation $\pi \in S_n$. The current upper bound is $n-{log}_{(\frac{7}{2})}n$ for prefix transposition distance over $S_n$. In this paper, we improve the same to $n-{log}_{3}n$.

Let $G$ be a graph of the order $n$ and size $m$. The minimum edge dominating energy is defined as the sum of the absolute values of eigenvalues of the minimum edge dominating matrix of the graph $G$. In this paper, we establish relations between the minimum edge dominating energy of a graph $G$ and the graph energy, the energy of the line graph, signless Laplacian energy of $G$.

We provide a particular measure for the degree to which an arbitrary composition deviates from increasing sorted order. The application of such a measure to the transport industry is given in the introduction. In order to obtain this measure, we define a statistic called the number of pushes in an arbitrary composition (which is required to produce sorted order) and obtain a generating function for this. The concept of a push is a geometrical one and leads naturally to several dependant concepts which are investigated. These are the number of cells which do not move in the pushing process and the number of cells that coincide before and after the pushing process (a number not less than those that do not move). The concept of a push leads to combining certain single pushes in a natural way which we define as a frictionless push. A generating function for these is also developed. The underlying geometry of the process also leads naturally to counting the largest first component of arbitrary compositions that are already in a sorted order. We provide a generating function for this.

The vertex arboricity $\mathrm{\text{va}}(G)$ of a graph $G$ is the minimum number of colors the vertices of the graph $G$ can be colored so that every color class induces an acyclic subgraph of $G$. There are many results on the vertex arboricity of planar graphs. In this paper, we replace planar graphs with graphs which can be embedded in a surface $\mathrm{\Sigma }$ of Euler characteristic $\chi (\mathrm{\Sigma })\ge 0$. We prove that for the graph $G$ which can be embedded in a surface $\mathrm{\Sigma }$ of Euler characteristic $\chi (\mathrm{\Sigma })\ge 0$ if no $3$-cycle intersects a $5$-cycle, or no $5$-cycle intersects a $6$-cycle, then $\mathrm{\text{va}}(G)\le 2$ in addition to the $4$-regular quadrilateral mesh.

The $(2,1)$-total choice number of $G$, denoted by $C_{(2,1)}^T(G)$, is the minimum $k$ such that $G$ is $k$-$(2,1)$-total choosable. It was proved in [Y. Yu, X. Zhang and G. Z. Liu, List (d,1)-total labeling of graphs embedded in surfaces, Oper. Res. Trans. 15(3) (2011) 29–37.] that $C_{p,1}^T(G)\le \mathrm{\Delta }+2p$ if $G$ is a graph embedded in surface with Euler characteristic $𝜀$ and $\mathrm{\Delta }(G)$ big enough. In this paper, we prove that: (i) if $G$ is a planar graph with $\mathrm{\Delta }(G)\ge 7$ and $3$-cycle is not adjacent to $k$-cycle, $k\in \{3,4\}$, then $C_{(2,1)}^T(G)\le \mathrm{\Delta }+4$; (ii) if $G$ is a planar graph with $\mathrm{\Delta }(G)\ge 8$ and $i$-cycle is not adjacent to $j$-cycle, where $i,j\in \{3,4,5\}$, then $C_{(2,1)}^T(G)\le \mathrm{\Delta }+3$.

Let $G=(V,E)$ be a simple graph of order $n$. The strong nonsplit domination polynomial of a graph $G$ is $D_{\mathrm{\text{sns}}}(G,x)={\sum }_{i={\gamma }_{\mathrm{\text{sns}}}(G)}^n{d}_{\mathrm{\text{sns}}}(G,i)x^i$ where $d_{\mathrm{\text{sns}}}(G,i)$ is the number of strong nonsplit dominating sets of $G$ of size $i$ and ${\gamma }_{\mathrm{\text{sns}}}(G)$ is the strong nonsplit domination number of $G$. Let ${\overline{\mathcal{𝒫}}}_n^i$ be the family of strong nonsplit dominating sets of a complement of a path $P_n$ (${\overline{P}}_n$) with cardinality $i$, and let $d_{\mathrm{\text{sns}}}({\overline{P}}_n,i)=\left|\right.{\overline{\mathcal{𝒫}}}_n^i\left|\right.$. In this paper, we construct ${\overline{\mathcal{𝒫}}}_n^i$, the recursive formula for $d_{\mathrm{\text{sns}}}({\overline{P}}_n,i)$ and $D_{\mathrm{\text{sns}}}({\overline{P}}_n,x)$, the strong nonsplit domination polynomial of ${\overline{P}}_n$. Also, we obtain some properties of the coefficients of this polynomial.

Let $G$ be a simple graph with vertex set $V(G)$ and edge set $E(G)$, respectively. An edge irregular $k$-labeling of $G$ is a labeling of $V(G)$ with labels from the set $\{1,2,\dots ,k\}$ in such a way that for any two different edges $e$ and $f$, their weights $w(e)$ and $w(f)$ are distinct. The weight of an edge $xy$ in $G$ is the sum of the labels of the end vertices $x$ and $y$. The minimum $k$ for which the graph $G$ has an edge irregular $k$-labeling is called the edge irregularity strength of $G$, denoted by $\mathrm{\text{es}}(G)$. In this paper, we determine the exact value of edge irregularity strength of corona product of graphs with cycle.

Let $G=(V,E)$ be a graph with edge set $E$ and vertex set $V$. For a connected graph $G$, a vertex set $S$ of $G$ is said to be a geodetic set if every vertex in $G$ lies in a shortest path between any pair of vertices in $S$. If the geodetic set $S$ is dominating, then $S$ is geodetic dominating set. A vertex set $S$ of $G$ is said to be a restrained geodetic dominating set if $S$ is geodetic, dominating and the subgraph induced by $V-S$ has no isolated vertex. The minimum cardinality of such set is called restrained geodetic domination (rgd) number. In this paper, rgd number of certain classes of graphs and 2-self-centered graphs was discussed. The restrained geodetic domination is discussed in graph operations such as Cartesian product and join of graphs. Restrained geodetic domination in corona product between a general connected graph and some classes of graphs is also discussed in this paper.

Let ${𝔽}_4$ be the field of four elements. We denote by $R$ the commutative ring, with $16$ elements, ${𝔽}_4+v{𝔽}_4:=\{a+vb|a,b\in {𝔽}_4\}$ with $v^2=v$. This work defines linear codes over the ring of mixed alphabets ${𝔽}_{4}R$ as well as their dual codes under a nondegenerate inner product. We then derive the systematic form of the respective generator matrices of the codes and their dual codes. We wrap the paper up by proving the MacWilliams identity for linear codes over ${𝔽}_{4}R$.

A $k$ vertex coloring of a graph $G=(V,E)$ partitions the vertex set into $k$ color classes (or independent sets). In minimum vertex coloring problem, the aim is to minimize the number of colors used in a given graph. Here, we consider three variations of vertex coloring problem in which (i) each vertex in $G$ dominates a color class, (ii) each color class is dominated by a vertex and (iii) each vertex is dominating a color class and each color class is dominated by a vertex. These minimization problems are known as Min-Dominator-Coloring, Min-CD-Coloring and Min-Domination-Coloring, respectively. In this paper, we present approximation hardness results for these problems for some restricted class of graphs.

The aim of this paper is to introduce a new class of generalized centralizers on $C^{\ast }$-algebras which is termed as extended $(k_1,k_2)$-centralizer. We study different properties of this class of centralizers. Moreover, we define a class of $C^{\ast }$-algebras which contains the prime $C^{\ast }$-algebras as a subclass. Different properties of extended centralizers with respect to this class of $C^{\ast }$-algebras are discussed with suitable examples.