Combinatorics and Graph Theory

1708 Submissions

[2] viXra:1708.0404 [pdf] submitted on 2017-08-28 06:04:10

Statistics on Small Graphs

Authors: Richard J. Mathar
Comments: Pages 47-120 are adjacency matrices for connected simple graphs up to 7 nodes.

We create the unlabeled or vertex-labeled graphs with up to 10 edges and up to 10 vertices and classify them by a set of standard properties: directed or not, vertex-labeled or not, connectivity, presence of isolated vertices, presence of multiedges and presence of loops. We present tables of how many graphs exist in these categories.
Category: Combinatorics and Graph Theory

[1] viXra:1708.0163 [pdf] replaced on 2017-08-16 02:10:47

Traveling Salesman Problem Solved with Zero Error

Authors: A. A. Frempong
Comments: 12 Pages. Copyright © by A. A. Frempong

The traveling salesman can determine by hand, with zero or negligible error, the shortest route from home base city to visit once, each of three cities, 10 cities, 20 cities, 100 cities, or 1000 cities, and return to the home base city. The general approach to solving the different types of NP problems is the same, except that sometimes, specific techniques may differ from each other according to the process involved in the problem. In the salesman problem, the first step is to arrange the data in the problem in increasing order, since one's interest is in the shortest distances. The main principle here is that the shortest route is the sum of the shortest distances such that the salesman visits each city once and returns to the starting city. The approach in this paper is different from the author's previous approach (viXra:1505.0167) in which the needed distances not among the least ten distances were added to the least ten distances before route construction began. In this paper, one starts with only the least ten distances and only if a needed distance is not among the set of the least ten distances, would one consider distances greater than those in the set of the ten least distances. The shortest route to visit nine cities and return to the starting city was found in this paper. It was also found out that even though the length of the shortest route is unique, the sequence of the cities involved is not unique. The approach used in this paper can be applied in workforce project management and hiring, as well as in a country's workforce needs and immigration quota determination. Since an approach that solves one of these problems can also solve other NP problems, and the traveling salesman problem has been solved, all NP problems can be solved, provided that one has an open mind and continues to think. If all NP problems can be solved, then all NP problems are P problems and therefore, P is equal to NP. The CMI Millennium Prize requirements have been satisfied
Category: Combinatorics and Graph Theory