Discrete Mathematics, Algorithms and Applications

Lovász had posed a question stating whether every connected, vertex-transitive graph has a Hamilton path in 1969. There is a growing interest in solving this longstanding problem and still it remains widely open. In fact, it was known that only five vertex-transitive graphs exist without a Hamiltonian cycle which do not belong to Cayley graphs. A Cayley graph is the subclass of vertex-transitive graph, and in view of the Lovász conjecture, the attention has focused more toward the Hamiltonicity of Cayley graphs. This survey will describe the current status of the search for Hamiltonian cycles and paths in Cayley graphs and digraphs on different groups, and discuss the future direction regarding famous conjecture.

We present an algorithm for solving the maximum 1-2 matching problem in bipartite graphs by reducing it to solving the 1-1 matching in general undirected graphs. Further, we propose two variants of the maximum 1-2 matching problem: one is the maximum 1-2 matching problem of the different kind in divided bipartite graphs and the other is the maximum 1-2 matching problem of the same kind in divided bipartite graphs. The former one is shown to be solved by a similar algorithm to that of the maximum 1-2 matching problem by reducing it to solve the maximum 1-1 matching problem in bipartite graphs. For the latter one, we can only present the augmenting subgraph theorem, which is an extension of our augmenting trail theorem for the maximum 1-2 matching problem.

In a graph $G=(V,E)$, a set $S\subseteq V(G)$ is said to be an open packing set if no two vertices of $S$ have a common neighbor in $G.$ The maximum cardinality of an open packing set is called the open packing number and is denoted by ${\rho }^o$. The open packing bondage number of a graph $G$, denoted by $ob(G)$, is the cardinality of the smallest set of edges $F\subset E(G)$ such that ${\rho }^o(G-F)>{\rho }^o(G)$. In this paper, we initiate a study on this parameter.

Self-dual and maximal self-orthogonal codes over $\mathrm{\text{GF}}(q)$, where $q$ is even or $q\equiv 1$(mod 4), are extensively studied in this paper. We prove that every maximal self-orthogonal code can be extended to a self-dual code as in the case of binary Golay code. Using these results, we show that a self-dual code can also be constructed by gluing theory even if the sum of the lengths of the gluing components is odd. Furthermore, the (Hamming) weight enumerator $W_{\overline{C}}(x,y)$ of a self-dual code $\overline{C}$ is given in terms of a maximal self-orthogonal code $C$, where $\overline{C}$ is obtained by the extension of $C$.

Let $G$ be a connected graph with a distance matrix $D$. Let $D^L(G)=\mathrm{\text{Tr}}(G)-D(G)$ and $D^Q(G)=\mathrm{\text{Tr}}(G)+D(G)$ be, respectively, the distance Laplacian matrix and the distance signless Laplacian matrix of graph $G$, where $\mathrm{\text{Tr}}(G)$ denotes the diagonal matrix of the vertex transmissions in $G$. The eigenvalues of $D^L(G)$ and $D^Q(G)$ constitute the distance Laplacian spectrum and distance signless Laplacian spectrum, respectively. The subdivision graph $S(G)$ of a graph $G$ is obtained by inserting a new vertex into every edge of $G$. We denote the set of such new vertices by $I(G)$. The subdivision-vertex join of two vertex disjoint graphs $G_1$ and $G_2$ denoted by $G_1\dot{\vee }{G}_2$, is the graph obtained from $S(G_1)$ and $G_2$ by joining each vertex of $V(G_1)$ with every vertex of $V(G_2)$. The subdivision-edge join of two vertex disjoint graphs $G_1$ and $G_2$ denoted by $G_1\underset{}{⊻}{G}_2$, is the graph obtained from $S(G_1)$ and $G_2$ by joining each vertex of $I(G_1)$ with every vertex of $V(G_2)$. In this paper, we determine the distance Laplacian and distance signless Laplacian spectra of subdivision-vertex join and subdivision-edge join of a connected regular graph with an arbitrary regular graph in terms of their eigenvalues. As an application we exhibit some infinite families of cospectral graphs and find the respective spectra of the Jahangir graph $J_{2,n}$.

The third leap Zagreb index of a graph $G$ is denoted as ${LM}_3(G)$ and is defined as ${LM}_3(G)={\sum }_{b\in V(G)}d(b/G)d_2(b/G)$, where $d_2(b/G)$ and $d(b/G)$ are the 2-distance degree and the degree of the vertex $b$ in $G$, respectively. The first, second and third leap Zagreb indices were introduced by Naji et al. [A. M. Naji, N. D. Soner and I. Gutman, On leap Zagreb indices of graphs, Commun. Combin. Optim. 2(2) (2017) 99–117] in 2017. In this paper, the behavior of the third leap Zagreb index under several graph operations like the Cartesian product, Corona product, neighborhood Corona product, lexicographic product, strong product, tensor product, symmetric difference and disjunction of two graphs is studied.

A Roman dominating function of a graph $G$ is a labeling $f:V(G)\to \{0,1,2\}$ such that every vertex with label $0$ has a neighbor with label $2$. The Roman domination number, ${\gamma }_R(G)$ of $G$, is the minimum of ${\sum }_{v\in V(G)}f(v)$ over such functions. Let $G$ be an $n$-vertex graph. Chambers et al. [E. W. Chambers, B. Kinnersley, N. Prince and D. B. West, External Problems for Roman domination Siam J. Discrete Math. 23 (2009) 1575–1586.] proved that if $G$ is a connected graph of order $n\ge 3$, then ${\gamma }_R(G)+{\gamma }_R(\overline{G})\le n+3$, with equality if and only if $G$ or $\overline{G}$ is $C_5$ or $(n/2)K_2$. In this paper, we construct a specific family of graphs $\xi$, and prove that if $G\notin \xi$ and $\overline{G}\notin \xi$, then ${\gamma }_R(G)+{\gamma }_R(Ḡ)\le n+1$, and this bound is sharp.

Recently Indulal and Balakrishnan [Distance spectrum of Indu–Bala product of graphs, AKCE Int. J. Graph Comb. 13 (2016) 230–234] put forward a new graph operation, namely, the Indu–Bala product $G_1▾G_2$ of graphs $G_1$ and $G_2$, and it is obtained from two disjoint copies of the join $G_1\vee G_2$ of $G_1$ and $G_2$ by joining the corresponding vertices in the two copies of $G_2$. In this paper, we obtain the adjacency spectra, the Laplacian spectra and the signless Laplacian spectra of $G_1▾G_2$ in terms of the corresponding spectra of $G_1$ and $G_2$. As applications, these results enable us to construct infinitely many pairs of respective cospectral graphs. Further, the Laplacian spectra enable us to get the formulas of the number of spanning trees and Kirchhoff index of $G_1▾G_2$ in terms of the Laplacian spectra of regular graphs $G_1$ and $G_2$.

For every Hadamard design with parameters $2$-$(n-1,\frac{n}{2}-1,\frac{n}{4}-1)$ having a skew-symmetric incidence matrix we give a construction of 54 Hadamard designs with parameters $2$-$(4n-1,2n-1,n-1)$. Moreover, for the case $n=8$ we construct doubly-even self-orthogonal binary linear codes from the corresponding Hadamard matrices of order 32. From these binary codes we construct five new extremal Type II ${\mathbb{Z}}_4$-codes of length 32. The constructed codes are the first examples of extremal Type II ${\mathbb{Z}}_4$-codes of length 32 and type $4^{k_1}{2}^{k_2}$, $k_1\in \{7,8,9,10\}$, whose residue codes have minimum weight 8. Further, correcting the results from the literature we construct 5147 extremal Type II ${\mathbb{Z}}_4$-codes of length 32 and type $4^{14}{2}^4$.

A vertex subset $S$ of a graph $G=(V,E)$ is a $[1,2]$-dominating set if each vertex of $V\setminus S$ is adjacent to either one or two vertices in $S$. The minimum cardinality of a $[1,2]$-dominating set of $G$, denoted by ${\gamma }_{[1,2]}(G)$, is called the $[1,2]$-domination number of $G$. In this paper, the $[1,2]$-domination and the $[1,2]$-total domination numbers of the generalized Petersen graphs $P(n,2)$ are determined.

Many models of genome rearrangement involve operations that are self-inverse, and hence generate a group acting on the space of genomes. This gives a correspondence between genome arrangements and the elements of a group, and consequently, between evolutionary paths and walks on the Cayley graph. Many common methods for phylogenetic reconstruction rely on calculating the minimal distance between two genomes; this omits much of the other information available from the Cayley graph. In this paper, we begin an exploration of some of this additional information, in particular describing the phylogeny as a Steiner tree within the Cayley graph, and exploring the “interval” between two genomes. While motivated by problems in systematic biology, many of these ideas are of independent group-theoretic interest.

This work introduces an algorithm that generates all combinations of size $k$ ($1\le k\le n$) of the set $\{1,2,\dots ,n\}$ satisfying the strong minimal change property (SMCP) and requires $O(k)$ memory space. The algorithm was implemented both iteratively and recursively; the iterative version has the advantage of processing the current combination in only one place of the algorithm, and the recursive version has the advantage of performing few operations to generate the next combination. The recursive version is similar to the algorithm of Eades and McKay because both algorithms have two functions that recursively call each other to generate the combinations; however, in the algorithm of Eades and McKay the depth of the recursion is $O(n)$, while in our algorithm is $O(k)$. Performance comparison against three algorithms having the SMCP show that the recursive version of our algorithm performs better than the other algorithms when $n$ is large.

Constant dimension subspace codes are subsets of the finite Grassmann Variety. Orbit codes are constant dimension subspace codes that arise as the orbit of subgroup of general linear group acting on subspaces in an ambient space. In particular, orbit codes of symplectic subgroup of the general linear group have been investigated recently. In this paper, we determine product of symplectic groups and its orbit code, and decoding algorithm of this code is considered.

A strong edge-coloring of a graph $G=(V,E)$ is a partition of its edge set $E$ into induced matchings. In this paper, we gave a short survey on recent results about strong edge-coloring of a graph.