Open Journal of Discrete Applied Mathematics (ODAM)

Capacitated vehicle routing problem is one of the variants of the vehicle routing problem which was studied in this research. In this research we applied a reinforcement learning algorithm to find set of routes from a depot to the set of customers while also considering the capacity of the vehicles, in order to reduce the cost of transportation of goods and services. Each vehicle originates from a depot, service the customers and return to the depot. We compare the reinforcement learning model with an exact method; column generation and Google’s OR-tool. Our objective is to solve a large-size of problem to near-optimality. We were able to use reinforcement learning to solve upto 101 nodes to near-optimality.

In this paper, we establish a connection between differential operators and Narayana numbers of both kinds, as well as a kind of numbers related to central binomial coefficients studied by Sulanke (Electron. J. Combin. 7 (2000), R40).

The Wiener index is a topological index of a molecule, defined as the sum of distances between all pairs of vertices in the chemical graph. Hexagonal chains consist of hexagonal rings connected with each other by edges. This class of chains contains molecular graphs of unbranched catacondensed benzenoid hydrocarbons. A segment of length \(\ell\) of a chain is its maximal subchain with \(\ell\) linear annelated hexagons. We consider chains in which all segments have equal lengths. Such chains can be uniquely represented by binary vectors. The Wiener index of hexagonal chains under some operations on the corresponding binary vectors are investigated. The obtained results may be useful in studying of topological indices for sets of hexagonal chains induced by algebraic constructions.

For every \(n\ge 3\), we determine the minimum number of edges of graph with \(n\) vertices such that for any non edge \(xy\) there exits a hamiltonian cycle containing \(xy\).

In this paper, the approach to obtaining nontrivial formulas for some recursively defined sequences is illustrated. The most interesting result in the paper is the formula for the solution of quadratic map-like recurrence. Also, some formulas for the solutions of linear difference equations with variable coefficients are obtained. At the end of the paper, some integer sequences associated with a quadratic map are considered.

For a given graph, let \(w_k\) denote the number of its walks with \(k\) vertices and let \(\lambda_1\) denote the spectral radius of its adjacency matrix. Nikiforov asked in [Linear Algebra Appl 418 (2006), 257–268] whether it is true in a connected bipartite graph that \(\lambda_1^r\geq\frac{w_{s+r}}{w_s}\) for every even \(s\geq 2\) and even \(r\geq 2\)? We construct here several infinite sequences of connected bipartite graphs with two main eigenvalues for which the ratio \(\frac{w_{s+r}}{\lambda_1^r w_s}\) is larger than~1 for every even \(s,r\geq 2\), and thus provide a negative answer to the above problem.

In a simple connected graph \(G\), eccentricity of a vertex is one of the first, distance-based invariants. The eccentricity of a vertex \(v\) in a connected graph \(G\) is the maximum distance of the vertex \(v\) to any other vertex \(u\). The total eccentricity of the graph \(G\) is the sum of the all vertex eccentricities. A graph \(G\) is called an apex tree if it has a vertex \(x\) such that \(G-x\) is a tree. In this work we have found the graph having extremal total eccentricity of \(k\)-apex trees.

In this paper, we obtained some new properties of Zagreb indices. We mainly give explicit formulas to the second Zagreb index of semitotal-line graph (or middle graph), semitotal-point graph and total transformation graphs \(G^{xyz}.\)

A graceful difference labeling (gdl for short) of a directed graph \(G\) with vertex set \(V\) is a bijection \(f:V\rightarrow\{1,\ldots,\vert V\vert\}\) such that, when each arc $uv$ is assigned the difference label \(f(v)-f(u)\), the resulting arc labels are distinct. We conjecture that all disjoint unions of circuits have a gdl, except in two particular cases. We prove partial results which support this conjecture.

Given a set of locations or cities and the cost of travel between each location, the task is to find the optimal tour that will visit each locations exactly once and return to the starting location. We solved a routing problem with focus on Traveling Salesman Problem using two algorithms. The task of choosing the algorithm that gives optimal result is difficult to accomplish in practice. However, most of the traditional methods are computationally bulky and with the rise of machine learning algorithms, which gives a near optimal solution. This paper studied two methods: branch-and-cut and machine learning methods. In the machine learning method, we used neural networks and reinforcement learning with 2-opt to train a recurrent network that predict a distribution of different location permutations using the negative tour-length as the reward signal and policy gradient to optimize the parameters of recurrent network. The improved machine learning with 2-opt give near-optimal results on 2D Euclidean with upto 200 nodes.