Open Journal of Discrete Applied Mathematics (ODAM)

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.

The Wiener index \(W(G)\) of a graph \(G\) is defined as the sum of distances between its vertices. A tree \(T\) generates \(r\)-uniform hypergraph \(H_{r,k}(T)\) by the following way: hyperedges of cardinality \(r\) correspond to edges of the tree and adjacent hyperedges have \(k\) vertices in common. A relation between quantities \(W(T)\) and \(W(H_{r,k}(T))\) is established.

The aim of this paper is to calculate the multiplicative topological indices of Zigzag polyhex nanotubes, Armchair polyhex nanotubes, Carbon nanocone networks, two dimensional Silicate network, Chain silicate network, six dimensional Hexagonal network, five dimensional Oxide network and four dimensional Honeycomb network.

Let \(G\) be a simple connected graph with \(n\) vertices, \(m\) edges, and a sequence of vertex degrees \(\Delta=d_1\geq d_2\geq\cdots\geq d_n=\delta >0\). Denote by \(\mu_1\geq \mu_2\geq\cdots\geq \mu_{n-1}>\mu_n=0\) the Laplacian eigenvalues of \(G\). The Kirchhoff index of \(G\) is defined as \(Kf(G)=n\sum_{i=1}^{n-1} \frac{1}{\mu_i}\). A couple of new lower bounds for \(Kf(G)\) that depend on \(n\), \(m\), \(\Delta\) and some other graph invariants are obtained.