Combinatorics and Graph Theory

2203 Submissions

[3] viXra:2203.0060 [pdf] replaced on 2023-07-10 23:57:02

The 4n-Region Map is Four-Colorable

Authors: Ihsan Raja Muda Nasution
Comments: 4 Pages.

In this paper, we try to solve the four-color problem for a special case; i.e., a map with 4n-region.
Category: Combinatorics and Graph Theory

[2] viXra:2203.0044 [pdf] submitted on 2022-03-09 05:22:59

Combinatorial Relation of Optimized Combination with Permutation

Authors: Chinnaraji Annamalai
Comments: 2 Pages.

This paper presents the relations of optimized combination with traditional combination and permutation. Combinatorics is a collection of several computing techniques used in science and management. In this research paper, new results on both combination and permutation are introduced for the researchers who are involving to find solutions for the scientific problems.
Category: Combinatorics and Graph Theory

[1] viXra:2203.0028 [pdf] replaced on 2025-05-31 20:54:50

Cycleexpander to Construct Directed Hamiltonian Circuit Hexcyclespanner to Tighten Directed Hamiltonian Circuit

Authors: Keshava Prasad Halemane
Comments: 10 Pages.

HexCycleSpanner (HCS) is a novel tool designed to achieve an elementary cycle refinement operation (ECRO) that is used to tighten a Directed Hamiltonian Circuit (dHC) - to be used iteratively as an extremely powerful technique to transform any given dHC to an optimum Shortest Directed Hamiltonian Circuit. Application to solving Asymmetric Travelling Salesman Problem (aTSP) is quite evident. ECRO uses a HCS to achieve an exchange of an outgoing arc-triplet of the given dHC with a corresponding incoming arc-triplet from outside the given dHC, thus resulting in a reconstructed transformed permuted dHC, while retaining the original direction/orientation of the given dHC. Effectively, the removal of the outgoing arc-triplet separates the given dHC into three cut-segments that are again rejoined by the incoming arc-triplet resulting in the reconstructed transformed permuted dHC wherein the original orientation of the dHC is retained - as defined by the orientation of the three cut-segments. This ECRO is analogous to the simplex pivot operation of Linear Programming wherein an exchange of the outgoing basic variable row with the incoming nonbasic variable column is performed to transform a given simplex tableaux representation into another equivalent simplex tableau representation that may be closer to the optimum tableaux. The concept of HexCycleSpanner can be generalized and extended to include incoming directed paths rather than incoming arcs to give rise to what may be called a CycleExpander (CyclExp) that may be used as an effective tool to construct a Directed Hamiltonian Circuit. The absence of a ‘global effectiveness measure’ (‘gem’) for aTSP - unlike in the case of LP - requires one to use a reference data base of optimum/shortest directed path between pairs of nodes to enhance the computational efficiency of the proposed iterative ECRO algorithm.
Category: Combinatorics and Graph Theory