Combinatorics and Graph Theory

Chord Diagrams with Directed Chords

Authors: Richard J. Mathar
Comments: 11 Pages.

Chord diagrams are cubic graphs with two types of edges: the first set of edges comprise a subgraph which is a simple cycle (the frame); the second type of edges (the chords) comprise disconnected 2-vertex subgraphs incident to distinct vertices of the frame. We define associated cubic graphs with directed chords (arcs) while keeping the edges of the frame undirected, and plot all 1, 3, 13, and 121 of them for 2, 4, 6, and 8 vertices.
Category: Combinatorics and Graph Theory

Graph Isomorphism in Polynomial time

Authors: Christos I. Karatzas
Comments: 16 Pages.

We show that the Graph Isomorphism (GI) problem can be solved in polynomialO(n3 + n2 m log(n + m) + m2 n log(n + m) + m3 log(n + m)) time, on simple con-nected graphs with n vertices and m edges. As fundamental part of the proof,we introduce a novel method, named Symmetry Classication, which computesa canonical automorphism partition of a simple connected graph in polynomialO(n2 + nm log n) time. The master algorithm reduces to bipartite graph iso-morphism by transforming the input graph, if not bipartite, to its subdivisiongraph and computes the canonical form of the latter; or of the former if alreadybipartite. Canonical form is obtained by repeating the sequence of rst applyingSymmetry Classication method, then canonically selecting a vertex for indi-vidualization, and last applying the classical 1-dimensional Weisfeiler-Lehmanalgorithm, until a canonical discrete coloring is attained. Since both bipartiteand connected graph isomorphism are isomorphism complete we conclude thatGI lies in P.
Category: Combinatorics and Graph Theory

A New Upper Bound for the Heilbronn Triangle Problem

Authors: Theophilus Agama
Comments: 10 Pages.

Using ideas from the geometry of compression, we improve on the current upper bound of Heilbronn's triangle problem. In particular, by letting $Delta(s)$ denotes the minimal area of the triangle induced by $s$ points in a unit disc, then we have the upper bound $$Delta(s)ll frac{1}{s^{frac{3}{2}-epsilon}}$$ for small $epsilon:=epsilon(s)>0$.
Category: Combinatorics and Graph Theory

Graphs and Their Symmetries

Authors: Teo Banica
Comments: 400 Pages.

This is an introduction to graph theory, from a geometric viewpoint. A finite graph $X$ is described by its adjacency matrix $din M_N(0,1)$, which can be thought of as a kind of discrete Laplacian, and we first discuss the basics of graph theory, by using $d$ and linear algebra tools. Then we discuss the computation of the classical and quantum symmetry groups $G(X)subset G^+(X)$, which must leave invariant the eigenspaces of $d$. Finally, we discuss similar questions for the quantum graphs, with these being again described by certain matrices $din M_N(mathbb C)$, but in a more twisted way.
Category: Combinatorics and Graph Theory

Sigmoid Fictionization of Magnetization in the Spin-Glass Ising Model

Authors: Akira Saito
Comments: 3 Pages.

The magnetization of the spin-glass Ising model can be expressed using a sigmoid function. In the ground state, the magnetization is determined by solving a set of nonlinear simultaneous equations, each corresponding to a magnetization. As the magnetization of the ground state in the spin-glass Ising model constitutes an NP-complete problem, the P=NP problem can be reformulated as solving these nonlinear simultaneous equations. If practical computation yields result that are feasible, it can be essentially considered as P=NP. Furthermore, all interacting systems in nature can be represented by sigmoid functions, and the ground state can be obtained by solving nonlinear simultaneous equations.
Category: Combinatorics and Graph Theory

Bivariate Generating Functions for Non-attacking Wazirs on Rectangular Boards

Authors: Richard J. Mathar
Comments: 15 Pages.

A wazir is a fairy chess piece that attacks the 4 neighbors to the North, East, South and West of the chess board. This work constructs the bivariate generating functions for the number of placing w mutually non-attacking wazirs on rectangular boards of shape r X c at fixed c. The equinumerous setup counts binary {0,1}-arrays of dimension r X c which have w 1's with mutual L1 (Manhattan) distances > 1.
Category: Combinatorics and Graph Theory

Detecting Whether a Graph Has a Fixed-point-free Automorphisms Is in Polynomial Time

Authors: Yasunori Ohto
Comments: 7 Pages.

The problem that to determining whether a graph has a fixed-point-free automorphism is NP-complete.We show that it is solvable in polynomial time.First, we obtain the automorphisms of an input graph G by using a spectral method.Next, we prove the Theorem used to detect whether there is a fixed-point free automorphism in G.Next, we construct an algorithm to detect whether G has a fixed-point-free automorphism using this result.The computational complexity of this problem is O(n^5).Then, the complexity classes P and NP are the same.
Category: Combinatorics and Graph Theory

Solving Graph Isomorphism Problem in Polynomial Time

Authors: Yasunori Ohto
Comments: 7 Pages. (Name added to Article by viXra Admin as required)

We show that the graph isomorphism problem is solvable in polynomial time.
Category: Combinatorics and Graph Theory

Elimination of ‘6’ as the Solution to Hadwiger-Nelson Problem

Authors: Aryan Hussain Sahir
Comments: 3 Pages.

Mathematicians are working day and night to solve problems like Riemann Hypothesis but problems like Hadwiger-Nelson problem are getting ignored though it can contribute greatly to many fields of science. In this paper, one of possible solutions to it has been eliminated by simple procedure, making the list of possible solutions decrease to "two" (2).
Category: Combinatorics and Graph Theory

The Particle Swarm Multi-search Space Augmentation Optimization

Authors: Derrick Donkor
Comments: 9 Pages.

The proposed Particle Swarm Optimization (PSO) variant uses a search space with a non-overlapping distinct search space for each particle in the population in the exploration of the optimum solution. What is normally done for a reduction in swarm size and achieving a much quicker response in PSO is to manually set the swarm size and other auxiliary constants through trial and error. An algorithm is proposed which assigns each particle to a unique non-verlapping finite search space and aggregates all particles position to form the solution at every functional evaluation. This assignment of the particles to a finite distinct search space is suitable for quick convergence with less iteration and less particle size comparatively. The theoretical basis is provided for the proposed algorithm and empirical studies are conducted to compare the proposed algorithm with other selected optimization algorithms on reference benchmark test functions.
Category: Combinatorics and Graph Theory

MTNSA: Microblogging Text Network Sentiment Analysis (Incorporating Hashtags and Emojis)

Authors: Abdalrhman Alquaary
Comments: 9 Pages.

In an era where social media platforms play a crucial role in shaping public discourse, microblogging data emerges as a vital resource for understanding complex social interactions. This paper introduces MTNSA (Microblogging Text Network Sentiment Analysis), a groundbreaking approach that harnesses the richness of social media communication by analyzing three separate categories: the relationships between words, relationships between hashtags, and relationships between emojis. MTNSA utilizes innovative techniques leveraging network theory to unravel the thoughts and opinions in microblogging environments, enriching itself by integrating sentiment analysis into this framework. This innovative method provides a comprehensive view of the sentiments associated with each node, offering deeper insights into the emotional nuances of online discourse. MTNSA's unique design enables its application across multilingual discourses, as it focuses on uncovering relationships between nodes, making it a versatile tool for global analysis in diverse linguistic contexts. The ability of MTNSA to blend nodes and emotional contexts into a unified analytical model presents a significant advancement in our understanding of digital communication patterns. It equips researchers, marketers, and policymakers with a robust tool to decode the intricate language of social media, contributing profoundly to our comprehension of how emotions and ideas are expressed and disseminated in the digital realm, thereby opening new frontiers for analysis in the dynamic landscape of social media.
Category: Combinatorics and Graph Theory

Solution to the Ground State of the Spin Glass Model

Authors: Akira Saito
Comments: 5 Pages.

We present a method for determining the order parameters of the spin glass Ising model (a general Ising model) in its ground state. This solution is valid specifically for the ground state, revealing the final outcomes of interactions and providing a solution to combinatorial optimization problems. The solution is presented through differential equations related to the inverse temperature, which can be solved using Euler's method. If the tracing of states through inverse temperature allows for the determination of state variables in a practically finite time, it becomes relevant to the P=NP problem. Furthermore, the set of equations obtained is also shown to be equivalent to those used in Boltzmann machines.
Category: Combinatorics and Graph Theory

A (1.999999)-Approximation Ratio for Vertex Cover Problem

Authors: Majid Zohrehbandian
Comments: 6 Pages.

Until the authenticity of the unique games conjecture is proven, it can be thought to be false. Therefore, I request you, dear reader, to read this paper carefully, and if you don't find any mistake in it, think about the option that maybe unique games conjecture is not correct! If the unique games conjecture is true then it is impossible to produce a less than 2 approximation ratio for the vertex cover problem. Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied over the years and while a 2-approximation for it can be trivially obtained, researchers have not been able to approximate it better than 2-textit{o}(1). In this paper, by a combination of a new semidefinite programming formulation along with satisfying new proposed properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of 1.999999 on arbitrary graphs, en route to answering an open question about the unique games conjecture.
Category: Combinatorics and Graph Theory

Tessellations and Sweeping Nets: Advancing the Calculus of Geometric Logic

Authors: Parker Emmerson
Comments: 44 Pages. Note by viXra Admin: Please list author name in the order of fist name followed by ;ast name!)

In this paper, we have explained how logic-vectors can be interpreted as a geometrical representation over computational engines and how it can be implemented in code using large language models. We have also proposed the usage of Time Compass to derive logic-vector evolution over a quasi-chaotic system and its direct manipulation on the tessellation Colormap. This paper focuses on the optimal arrangement of reflecting points for efficient ray tracing given limited sweep time. We examine spatial configurations, employing our core concept of a sweeping subnet and defining a causal barrier to capture constraints imposed by time.We will also discuss the influence of these constructions on the design of an algorithm for approximating optimal tessellations.I have provided code for each of the graphs, as the mathematics is demonstrated unequivocally by their implementation. The reader can test out the reality of this system by visualizing the graphs themselves using Python in a suitable environment like Google Colaboratory.
Category: Combinatorics and Graph Theory

Dimensions of a Graph

Authors: Volker W. Thürey
Comments: 6 Pages.

We introduce eight infinite sets of constants.Some we calculate. Roughly speaking, we seek graphs as small as possible. The graphs serve as examples for different kinds of 'dimensions'. In the second part 'Points', we place points on the plane, and from this, we ask infinite many questions. In a third part, we introduce for each graph a sequence called the 'Thuerey Numbers'.At the end, we summarize the open questions.
Category: Combinatorics and Graph Theory

Spectrum of Sunflower Hypergraphs

Authors: Prajnanaswaroopa S
Comments: 9 Pages.

Hypergraphs are generalization of graphs, which have several useful applications. Sunflower hypergraphs are interesting hypergraphs, which become linear in some cases. In this paper, we discuss the Siedel spectrum of these hypergraphs.
Category: Combinatorics and Graph Theory

The Isomorphism of H4 and E8

Authors: J. Gregory Moxness
Comments: 19 Pages.

This paper gives an explicit isomorphic mapping from the 240 real R^8 roots of the E8 Gossett 4_{21} 8-polytope to two golden ratio scaled copies of the 120 root H4 600-cell quaternion 4-polytope using a traceless 8x8 rotation matrix U with palindromic characteristic coefficients and a unitary form e^{iU}}. It also shows the inverse map from a single H4 600-cell to E8 using a 4D<->8D chiral L<->R mapping function, phi scaling, and U^{-1}. This approach shows that there are actually four copies of each 600-cell living within E8 in the form of chiral H4L+phi H4L+H4R+phi H4R roots. In addition, it demonstrates a quaternion Weyl orbit construction of H4-based 4-polytopes that provides an explicit mapping between E8 and four copies of the tri-rectified Coxeter-Dynkin diagram of H4, namely the 120-cell of order 600. Taking advantage of this property promises to open the door to as yet unexplored E8-based Grand Unified Theories or GUTs.
Category: Combinatorics and Graph Theory

Simultaneous Equations of Order Parameter for Ground State Spin Glass Model

Authors: Akira Saito
Comments: 4 Pages. In Japanese (Note by viXra Admin: Please fill in author name in English)

We were able to express the order parameter of the spin glass model in the ground state using simultaneous equations. Although this simultaneous equation is an equation that is valid only in the ground state, it is possible to minimize economic loss from a network system that influences each other to model food chains, organizations, economic social phenomena, etc., and to obtain optimal results from complex conditions. Accurately understanding the ground state provides a wide range of benefits, including combinatorial optimization problems that enable accurate matching. Furthermore, since the spin glass ising model is a basic model, it is also possible to refer to natural world and mathematical problems such as complex systems and P≠NP problems [1]. Here, as a basis for these problems, and as a method for analyzing social phenomena and problems such as combinatorial optimization problems and complex systems, we will introduce simultaneous equation formulation and numerical calculation of simultaneous equation solutions as a solution method for ground state spin glass models. Show the results.
Category: Combinatorics and Graph Theory

Harmonic Graphs Conjecture: Graph-Theoretic Attributes and their Number Theoretic Correlations

Authors: Felipe Correa Rodríguez
Comments: 8 Pages. This is a paper of graph theory.

The Harmonic Graphs Conjecture states that there exists a harmonious relationship between the graph's Harmonic Index ($HI(G_n)$) and the number of vertices ($n$) for every connected graph $G_n$. This relationship can be expressed as a formula, which takes into account the prime number theorem and the sum of divisors function. In this paper, we prove the Harmonic Graphs Conjecture for cycle graphs and complete graphs. We do this by expanding the definitions of the harmonic index and the sum of divisors function, and then using the prime number theorem to approximate the values of these functions. This work is an effort to provide a contribution to the field of graph theory. It provides a new way to study the connectivity of graphs and opens up new avenues for research. For example, our results could be used to develop new algorithms for finding connected components in graphs, or to design new networks that are more resilient to failures.
Category: Combinatorics and Graph Theory

On Conway's 99-graph: Parts 1-20

Authors: E. Guseinov
Comments: 95 Pages.

This preprint in Russian reflects some of my results on Conway's 99-graph (G) obtained in 2022-2023 during a research that I did on my own. Here I prove that G is Cartesian indecomposable (Part 10, Theorem 36), G can not be obtained by a group-theoretic generalization of Berlekamp-Seidel's construction (Part 11), G contains no Hamming graph H(4,3) (Part 8, Theorem 28), G is not contained in strongly regular graphs srg(243,22,1,2) (Part 12, Theorem 40), the independence number of G is at least 10 (Part 4, Theorem 21). Parts 12-17, 19 and 20 reflect attempts to prove G may contain H(2,3), i. e. the Paley graph P(9). I'm currently accepting offers to join a graph theoretical research, so you can write me on elmarguseinov@yahoo.com.
Category: Combinatorics and Graph Theory

General Conjecture on the Optimal Covering Trails in a K-Dimensional Cubic Lattice

Authors: Marco Ripà
Comments: 7 Pages. Comments and suggestions are welcome.

We introduce a general conjecture involving minimum-link covering trails for any given k-dimensional grid n × n × · · · × n, belonging to the cubic lattice N^k. In details, if n is above two, we hypothesize that the minimal link length of any covering trail, for the above mentioned set of n^k points in the Euclidean space R^k , is equal to h(n, k) = (n^k −1 )/(n−1) + c · (n − 3), where c = k − 1 iff h(4, 3) = 23, c = 1 iff h(4, 3) = 22, or even c = 0 iff h(4, 3) = 21.
Category: Combinatorics and Graph Theory

Rencontres for Equipartite Distributions of Multisets of Colored Balls into Urns

Authors: Richard J. Mathar
Comments: 7 Pages.

A multiset of u*b balls contains u different colors and b balls of each color. Randomly distributing them across u urns with b balls per urn, what is the probability that no urn contains at least two balls of a common color? We reduce this problem to the enumeration of u X u binary matrices with constant row and column sum b and provide an explicit table of probabilities for small b and u.
Category: Combinatorics and Graph Theory

A Slightly More Theorem Than the Four Color Theorem Then Four Color Theorem of Which This is a Special Case

Authors: Henri Caillaud
Comments: 30 Pages. In French (Correction made by viXra Admin - Please conform!)

This is a proof of a theorem on normal graphs (any point on the graph has three neighbors) whose 'countries' are not homogeneous. The property of homogeneity will be explained in detail. These graphs are not necessarily planar but planar graphs are a subset of them. The property demonstrated is to be "Hamiltonian in even loops". This property is equivalent to the property of being "colorable in four colors" for planar maps.
Category: Combinatorics and Graph Theory

An Elementary Solution of the Four-color Conjecture

Authors: Chongxi Yu
Comments: 3 Pages.

The four-color conjecture ( Guthrie's problem after F. Guthrie) is divided into 5 simple groups, every region is shared a common boundary with 1, 2, 3, 4, and unlimited regions sharing a common boundary (other than a single point) do not share the same color to make the problem much simpler and clearer, The four-color theorem is solved perfectly by using these simpler models.
Category: Combinatorics and Graph Theory

A Probabilistic Proof of the Multinomial Theorem Following the Number $a_n^p$

Authors: Atsu Dekpe
Comments: 3 Pages.

In this note, we give an alternate proof of the multinomial theorem following the number $ A_n^p $ using probabilistic approach. Although the multinomial theorem following the number $ A_n^p$ is basically a combinatorial result, our proof may be simple for a student familiar with only basic probability concepts.
Category: Combinatorics and Graph Theory

Multinomial Development

Authors: Atsu Dekpe
Comments: 18 Pages.

In this paper we obtain the multinomial theorem following the numbers $ A_n^p $ and $ C_n^p $ (Vandermonde's identity generalization). Using this notion we obtain generalization of products of numbers in arithmetic progression, arithmetic regression and their sum. From the generalisation we propose (define) the arithmetics sequences product.
Category: Combinatorics and Graph Theory

New Classifications of Labeled Rooted Growing Trees and Their Application to Simplifying of the Tree Representation of Functions

Authors: G. I. Kalmykov
Comments: Pages.

The article deals with labeled rooted growing trees. Research in this area, carried outby the author of this article over the past 35 years, has led to the creation of the conceptof tree classification of labeled graphs. This concept is the mathematical basis of the treesum method aimed at simplifying the representations of the coefficients of power series in classical statistical mechanics. This method was used to obtain tree representations of Mayer coefficients of expansions of pressure and density in terms of activity degrees, which are free from asymptotic catastrophe. The same method was used to obtain tree representations of thecoefficients of the expansion of the ratio of activity to density in terms of activity degrees.All these representations for n ≥ 7 are much simpler than the comparable Ree-Hooverrepresentations according to the complexity criteria defined on these representations. Treerepresentations of the coefficients of the expansion of the m-particles distribution functioninto a series in terms of activity degrees were also obtained. All the above representations ofthe coefficients of power series obtained by the trees sum method are free from the asymptoticcatastrophe.In order to provide a mathematical basis for constructing new, even less complexrepresentations of the coefficients of these power series, further development of the conceptof tree classification of labeled graphs was required.As part of solving the problem of further development of this concept, the article proposesnew classifications of labeled rooted growing trees. And on their basis, the theorem wasformulated and proved, which is the basis for simplifying the tree representations of functions,that is, its representations as a sum of labeled by trees products of functions.
Category: Combinatorics and Graph Theory

"N_1 × N_2 × ... × N_k Dots Puzzle": an Optimal General Algorithm

Authors: Valerio Bencini
Comments: 34 Pages. Written in italian, this is a slightly revised copy of a paper published in 2019.

In this paper, we show a new algorithm for the "n_1 × n_2 × ... × n_k dots puzzle" (an extension of the well-known "nine dots puzzle" of Samuel Loyd), able to solve completely the problem for the case "k=2" and, at the same time, provide lower upper bounds for the other cases.
Category: Combinatorics and Graph Theory

Almost QR

Authors: Elmar Guseinov
Comments: 2 Pages. In Russian

Consider the following five matrices corresponding to black and white square patterns: ((0,0,0),(0,0,0),(0,0,0)), ((0,0,0),(1,1,0),(0,1,0)), ((0,1,0),(0,1,0),(0,1,0)), ((0,1,0),(1,1,0),(0,1,0)), ((0,1,0),(1,1,1),(0,1,0)). You can rotate these matrices clockwise and after that choose four of them (possibly repeated) to build up a big 6x6 pattern. How many big patterns can be obtained if the clockwise rotation gives the same big pattern?
Category: Combinatorics and Graph Theory

A Bipolar Single Valued Neutrosophic Isolated Graphs: Revisited

Authors: Said Broumi, Assia Bakali, Mohamed Talea, Florentin Smarandache, Mohsin Khan
Comments: 6 Pages.

In this research paper, the graph of the bipolar single-valued neutrosophic set model (BSVNS) is proposed. The graphs of single valued neutrosophic set models is generalized by this graph. For the BSVNS model, several results have been proved on complete and isolated graphs. Adding, an important and suitable condition for the graphs of the BSVNS model to become an isolated graph of the BSVNS model has been demonstrated.
Category: Combinatorics and Graph Theory

Extension of Hypergraph to N-Superhypergraph and to Plithogenic N-Superhypergraph, and Extension of Hyperalgebra to N-Ary (Classical-/neutro-/anti-)hyperalgebra

Authors: Florentin Smarandache
Comments: 7 Pages.

We recall and improve our 2019 concepts of n-Power Set of a Set, n-SuperHyperGraph, Plithogenic n-SuperHyperGraph, and n-ary HyperAlgebra, n-ary NeutroHyperAlgebra, n-ary AntiHyperAlgebra respectively, and we present several properties and examples connected with the real world.
Category: Combinatorics and Graph Theory

Introduction to the N-Superhypergraph the Most General Form of Graph Today

Authors: Florentin Smarandache
Comments: 3 Pages.

We recall and improve our 2019 and 2020 concepts of n-SuperHyperGraph, Plithogenic nSuperHyperGraph, n-Power Set of a Set, and we present some application from the real world. The nSuperHyperGraph is the most general form of graph today and it is able to describe the complex reality we live in, by using n-SuperVertices (groups of groups of groups etc.) and nSuperHyperEdges (edges connecting groups of groups of groups etc.).
Category: Combinatorics and Graph Theory

The Model of Four Color Theorem

Authors: Hui Liu
Comments: 2 Pages.

There is no perfect solution to the four-color theorem, although mathematicians have demonstrated it with computers. People have been asking: What is the essence of the four-color theorem? We think that the four color theorem is a space partition problem. We started from one-dimensional space, then expanded from one-dimensional space to two-dimensional space, and the problem was solved perfectly.
Category: Combinatorics and Graph Theory

An Elementary Proof of Franel Number Recurrence Relation

Authors: Suaib Lateef
Comments: 8 Pages.

In this paper, we provide an elementary proof of Franel number recurrence relation. Consequently, we derive a recurrence relation involving the sum of third powers of binomial coefficients.
Category: Combinatorics and Graph Theory

Graph Equations

Authors: Elmar Guseinov
Comments: 18 Pages.

В данной статье приводится решение 83 проблем, формулировка которых близка к формулировке гипотезы грациозности деревьев. Для оптимизации процесса решения была написана соответствующая рекомендательная программа.

This article provides a solution to 83 problems, the formulation of which is close to the formulation of the graceful tree conjecture. To optimize the solution process, an appropriate recommendation system was written.
Category: Combinatorics and Graph Theory

On the Number of Integral Points in the Annular Region Induced by Spheres in $\mathbb{R}^k$

Authors: Theophilus Agama
Comments: 8 Pages.

Using the method of compression we show that the number of integral points in the annular region induced by two $k$ dimensional spheres of radii $r$ and $R$ with $R>r$ satisfies the lower bound \begin{align} \mathcal{N}_{R,r,k} \gg (R^{k-1}-r^{k+\delta})\sqrt{k}.\nonumber \end{align}for some small $\delta>0$ with $k>\frac{\delta(\log r)}{\log R-\log r}$.
Category: Combinatorics and Graph Theory

Five More Proofs of the Cosine Addition Formula (Inspired by Mark Levi's Perpetuum Mobile Proof)

Authors: Doron Zeilberger
Comments: 1 Page.

Inspired by Mark Levi's wonderful proof of the Cosine addition formula, that showed that it follows from the sad fact that Perpetual Motion is impossible, we recall five other proofs.
Category: Combinatorics and Graph Theory

Small Cycles of the Generalized Shells

Authors: Elmar Guseinov
Comments: Pages.

The Erdős-Gyárfás conjecture (EGC) states that every graph with minimum vertex degree of at least 3 contains a cycle whose length is a power of 2. The statement has not been proven even for cubic graphs. Moreover, it has not been proven for cubic Hamiltonian graphs. On the other hand, we can see that every cubic Hamiltonian graph has an even number of vertices 2k and can be obtained by adding k edges to a 2k-cycle. It will be shown that adding this number of edges to a given vertex of the cycle always gives a 4-cycle. This suggests the validity of EGC for cubic Hamiltonian graphs. This theorem is a consequence of a more general result the proof of which is the main content of the paper. Namely, we will determine the maximum number of edges the addition of which to a given vertex of a cycle does not give a cycle of a sufficiently small length.
Category: Combinatorics and Graph Theory

Computation of Multiple Binomial Series Based on Geometric Series

Authors: Chinnaraji Annamalai
Comments: 2 Pages.

This paper presents addition of multiple binomial series based on geometric series. In general, a finite multiple summations of a geometric series are called binomial series. Addition of multiple binomial series is a sum and summation of multiple binomial series.
Category: Combinatorics and Graph Theory

Summation of Multiple Times of a Geometric Series and Its Binomial Series

Authors: Chinnaraji Annamalai
Comments: 2 Pages.

This paper presents a binomial series of summation of multiple times of a geometric series. This will be useful for the researchers who are involving to solve the scientific problems.
Category: Combinatorics and Graph Theory

Comparison Between Optimized and Traditional Combinations of Combinatorics

Authors: Chinnaraji Annamalai
Comments: 2 Pages.

This paper compares the traditional combination of combinatorics with the optimized combination introduced by Chinnaraji Annamalai, Indian Institute of Technology Kharagpur. This comparison of combinatorial combinations will be useful for the researchers who are involving to solve the problems in science and management.
Category: Combinatorics and Graph Theory

Invariant Property of Binomial Coefficients

Authors: Rejean Labrie
Comments: 7 Pages. In French

Although many properties of Pascal's triangle are known, few of them correspond to a summation of products of binomial coefficients. The written property here comes to enrich this last group but it is characterized especially by its invariance.
Category: Combinatorics and Graph Theory

Novel Binomial Series and its Summations

Authors: Chinnaraji Annamalai
Comments: 2 Pages.

This paper presents new binomial series and its summations of the optimized combinations relating to the combinatorics. These series and summations will be useful for the researchers who are involving to solve the scientific problems.
Category: Combinatorics and Graph Theory

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

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

HexCycleSpanner to Tighten Directed Hamiltonian Circuit CycleExpander to Construct Directed Hamiltonian Circuit

Authors: Keshava Prasad Halemane
Comments: 7 Pages. [Corrections made by viXra Admin to conform with scholarly norm Please conform!]

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 (sdHC). 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 (CyExp) that may be used as an effective tool to construct a Directed Hamiltonian Circuit.
Category: Combinatorics and Graph Theory

A Randomized 1.885903-Approximation Algorithm for the Minimum Vertex Cover Problem

Authors: Majid Zohrehbandian
Comments: 6 Pages.

Vertex cover problem is a famous combinatorial problem and its complexity has been heavily studied over the years. It is known that it is hard to approximate to within any constant factor better than 2, while a 2-approximation for it can be trivially obtained. In this paper, new properties and new techniques are introduced which lead to approximation ratios smaller than 2 on special graphs. Then, by a combination of semidefinite programming and a rounding procedure, along with satisfying the proposed assumptions, we introduce an approximation algorithm with a performance ratio of 1.885903 on arbitrary graphs.
Category: Combinatorics and Graph Theory

Characterizing Spectral Properties of Bridge Graphs

Authors: Yixin Li
Comments: 34 Pages.

Bridge graphs are special type of graphs which are constructed by connecting identical connected graphs with path graphs. We discuss different type of bridge graphs $B_{n\times l}^{m\times k}$ in this paper. In particular, we discuss the following: complete-type bridge graphs, star-type bridge graphs, and full binary tree bridge graphs. We also bound the second eigenvalues of the graph Laplacian of these graphs using methods from Spectral Graph Theory. In general, we prove that for general bridge graphs, $B_{n\times l}^2$, the second eigenvalue of the graph Laplacian should between $0$ and $2$, inclusive. At the end, we talk about the future work about infinite bridge graphs. We create definitions and found the related theorems to support our future work about infinite bridge graphs.
Category: Combinatorics and Graph Theory

A Probabilistic Solution for the Syracuse Comjecture

Authors: Imad El Ghazi
Comments: 6 Pages.

We prove the veracity of the Syracuse conjecture by establishing that starting from an arbitrary positive integer diffrent of 1 and 4, the Syracuse process will never comeback to any positive integer reached before and then we conclude by using a probabilistic approach.
Category: Combinatorics and Graph Theory

The Area Induced by Circles of Partition and Applications

Authors: Theophilus Agama
Comments: 5 Pages.

In this paper we continue with the development of the circles of partitions by introducing the notion of the area induced by circles of partitions and explore some applications.
Category: Combinatorics and Graph Theory

Graph Thinness, a Lower Bound and Complexity

Authors: Yaroslav Shitov
Comments: 9 pages

The thinness of a simple graph G= (V,E) is the smallest integer k for which there exist a total order (V, <) and a partition of V into k classes (V_1,...,V_k) such that, for all u, v, w in V with u<v<w, if u and v belong to the same class and {u,w} is in E, then {v,w} is in E. We prove that (1) there are $n$-vertex graphs of thinness $n-o(n)$, which answers a question of Bonomo-Braberman, Gonzalez, Oliveira, Sampaio, and Szwarcfiter, (2) the computation of thinness is NP-hard, which is a solution to a long standing open problem posed by Mannino and Oriolo.
Category: Combinatorics and Graph Theory

Revised Collatz Graph Explains Predictability

Authors: Steven M. Tylock
Comments: 11 Pages.

The Collatz Conjecture remains an intriguing problem. Expanding on an altered formula first presented in “Bits of Complexity”, this paper explores the concept that “3N + Least-Significant-Bit” of a number allows the complete separation of the step of “dividing by two on an even number” within the Collatz Conjecture. This alternate formula replaces the original Collatz on a one-for-one basis. The breadth and depth of graphs of the resulting path of numbers resolving with this new formula illustrate its fractal nature. Lastly, we explore the predictability of this data, and how the ultimate goal of reaching one prevented previous work from finding the key to understanding 3N+1.
Category: Combinatorics and Graph Theory

Sums of Powers of Generalized Binomial Coefficients and Arithmetic Progression

Authors: Suaib Lateef
Comments: 9 pages

In this paper, we establish two relationships between the sums of product of powers of generalized binomial coefficients and arithmetic progression. As a result, we establish a relationship between the sum of an arithmetic progression, sum of squares of an arithmetic progression, sum of cubes of an arithmetic progression, and the number of terms of an arithmetic progression. Also, we establish a relationship between the sum of an arithmetic progression, sum of squares of an arithmetic progression, sum of cubes of an arithmetic progression, sum of fourth powers of an arithmetic progression, sum of fifth powers of an arithmetic progression and the number of terms of an arithmetic progression. We also give two new different expressions for Franel numbers as well as the right-hand side of first Strehl identity.
Category: Combinatorics and Graph Theory

Function Hypergraphs

Authors: Juan Elias Millas Vera
Comments: 3 Pages. 2 images.

In this paper we are going to introduce the notion of function hypergraph. In hypergraphs we have sets of vertices linked by other elements (sub-sets) called edges and the sets can be distributed in many ways. My idea with function hypergraphs is develop a practical use of the theory using defined functions and variables instead of sets.
Category: Combinatorics and Graph Theory

A Problem on Sum of Powers of Binomial Coefficients

Authors: Suaib Lateef
Comments: 5 pages

In this paper, we present a problem concerning the sum of powers of Binomial coefficients. We prove two special cases of the problem using some simple identities involving Binomial coefficients, and list another two cases but without proof.
Category: Combinatorics and Graph Theory

Introduction to the Theory of Graphs: a Methodological Information Description of the Origem Problem and Applications to the Problem for Solution

Authors: Faustino A. Maciala
Comments: 18 Pages. [Corrections are made by viXra Admin to comply with the rules of viXra.org]

The present work presents a study about the introduction to graph theory,of the problem that originated them and looks at the resolution of some problems that involve it. The first section, the introduction, presents an introductory approach to graph theory, problematization and justification of the choice of theme. In the second section, we present a historical review,its importance and the teaching process learning the same theme adding the concept of graph and different types of graphs. In the third section, Results and Discussion, we present the problem of bridges in the city of K ̈onigsbergand some application problems, such as color or 4-color problem, telephone calls and Minimum Longitude Path.

O presente trabalho traz um estudo sobre a introdução a teoria de grafos, do problema que os originou e faz um olhar a resolução de alguns problemas que o envolvem. A primeira secção, a introdução, faz-se uma abordagem introdutória da teoria de grafos, da problematização e da justicativa da escolha do tema. Na segunda secção, apresentamos uma resenha histórica, sua importância e o processo de ensino aprendizagem do mesmo tema acrescendo o conceito de grafo e diferentes tipos de grafos. Na terceira secção, resultados e Discussão, apresenta-se o problema das pontes de Na cidade de Khonigsberg e apresenta-se alguns problemas de aplicação, tais como, problema de coloração ou das 4 cores, chamadas telefónicas e Caminho de Longitude Mínima. Palavras Chave: Grafos, Teoria de Grafos e Resolução de Problemas.
Category: Combinatorics and Graph Theory

Combinatorial Optimization Problem Solving Method by Correlation Coefficient of Ising Model Order Parameter

Authors: Akira Saito
Comments: 4 Pages.

任意の相互作用パラメータを持つイジングモデルの秩序変数を相関係数で表すことができた。これにより検定力分析で決まるサンプル数によって、ある精度の条件下で、秩序変数を求めることができる。温度0でのイジングモデルの秩序変数は、組み合わせ最適化問題の解となることが知られている。各秩序変数によりyesなのかnoなのかを知りたいだけであれば、サンプル数で求まる秩序変数で判断することができる。つまり、組み合わせ最適化問題を、計算ステップ数 T 、入力サイズ N に対してT∼O(N^k)で解くことができる可能性がある。このことはNP困難問題を多項式時間で解ける可能性を示しており、P=NPを暗示している。
Category: Combinatorics and Graph Theory

New Insight Into Introducing a (2-ℇ)-Approximation Ratio for Minimum Vertex Cover Problem

Authors: Majid Zohrehbandian
Comments: 7 Pages. Submitted to "ACM Transactions on Algorithms"

Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied. It is known that it is hard to approximate to within any constant factor better than 2, while a 2‒approximation for it can be trivially obtained. In this paper, new properties and new techniques are introduced which lead to approximation ratios smaller than 2 on special graphs. Then, by introducing a modified graph and corresponding model along with satisfying the proposed assumptions, we propose new insight into solving this open problem and we introduce an approximation algorithm with a performance ratio of 1.99997 on arbitrary graphs.
Category: Combinatorics and Graph Theory

Quantum Partial Automorphisms of Finite Graphs

Authors: Teo Banica
Comments: 28 Pages.

The partial automorphisms of a graph $X$ having $N$ vertices are the bijections $\sigma:I\to J$ with $I,J\subset\{1,\ldots,N\}$ which leave invariant the edges. These bijections form a semigroup $\widetilde{G}(X)$, which contains the automorphism group $G(X)$. We discuss here the quantum analogue of this construction, with a definition and basic theory for the quantum semigroup of quantum partial automorphisms $\widetilde{G}^+(X)$, which contains both $G(X)$, and the quantum automorphism group $G^+(X)$. We comment as well on the case $N=\infty$, which is of particular interest, due to the fact that $\widetilde{G}^+(X)$ is well-defined, while its subgroup $G^+(X)$, not necessarily, at least with the currently known methods.
Category: Combinatorics and Graph Theory

An Extension of the Erd\h{o}s-Tur\'{a}n Additive Base Conjecture Via Generalized Circles of Partition

Authors: Theophilus Agama
Comments: 5 Pages.

In this paper we continue the development of the method of Circles of Partition by introducing the notion of generalized circles of partition. This is an extension program of the notion of circle of partition developed in our first paper \cite{CoP}. As an application we prove an analogue of the Erd\H{o}s-Tur\'{a}n additive base conjecture.
Category: Combinatorics and Graph Theory

Embedding Cycles Within Adjacency Matrices to Represent Rational Generating Functions

Authors: Yonah Berwaldt
Comments: 24 Pages.

This paper explores populating adjacency matrices with connected cycles whose final outputs represent the coefficients of rational generating functions (RGFs). An RGF takes the form of: $p(x)/q(x) + r(x)$. The denominator, $q(x)$, takes the form of: Constant $\cdot (1-c_1x^{x_1})(1-c_2x^{x_2})... (1-c_nx^{x_n})$ where the $c_i$ are complex numbers and where factors can possibly have multiplicities greater than one. It is well known that a closed form solution exists for computing coefficients of RGFs. Also, one can write the linear recurrence relation associated with every RGF into a matrix format. Using matrices, one can compute coefficients for an RGF, such as Molien series for finite groups, in logarithmic time. What has not yet been shown (or is not yet commonly discussed) is that one can conceptualize an RGF as a system of connected cycles within an overarching adjacency matrix. For example, a single cycle of length two would have vertex A connect to vertex B which itself connects back to vertex A with a directed arrow of weight $c_i$. In this conceptualization, each coefficient of an RGF can be reproduced by taking a suitable adjacency matrix to an integer power. Nothing essential is lost by taking this perspective. Due to the self-similar nature of the matrix, we devise an algorithm that can calculate coefficients of RGFs in constant time. Using memoization, a technique for caching intermediate results, calculating coefficients of RGFs can also be done in logarithmic time. One observation is that, depending on the situation (i.e. what $q(x)$ is), there may be a computational benefit to taking the cyclical perspective. For example, for certain $q(x)$, the traditional matrix has cells containing positive and negative values whereas the cyclical approach has cells containing only positive values. The computational benefit is probably irrelevant for computers; however, it may be important for restrictive systems, such as biological systems / neural networks that may have a tight operating envelope. We make a final observation that each cyclical matrix representation can be thought of as a graph which is an epsilon away from being strongly connected. Studying the behavior of these matrices may yield insight into the behavior of a broader class of function. In essence, the study of sequences modeled by RGFs can be converted to the study of connected cyclical graphs that model the RGFs or vice versa.
Category: Combinatorics and Graph Theory

Chordal Bipartite Graphs Are Rank Determined

Authors: Yaroslav Shitov
Comments: 16 Pages.

A partial matrix A is a rectangular array with entries in F ∪ {∗}, where F is the ground field, and ∗ is a placeholder symbol for entries which are not specified. The minimum rank mr(A) is the smallest value of the ranks of all matrices obtained from A by replacing the ∗ symbols with arbitrary elements in F. For any bipartite graph G with vertices (U, V), one defines the set M(G) of partial matrices in which the row indexes are in U, the column indexes are in V, and the (u, v) entry is specified if and only if u, v are adjacent in G. We prove that, if G is chordal bipartite, then the minimum rank of any matrix in M(G) is determined by the ranks of its fully specified submatrices. This result was conjectured by Cohen, Johnson, Rodman, Woerdeman in 1989.
Category: Combinatorics and Graph Theory

The Theory of Cells

Authors: Theophilus Agama
Comments: 10 Pages.

In this paper we introduce and develop the notion of universe, induced communities and cells with their corresponding spots. We study the concept of the density, the mass of communities, the concentration of spots in a typical cell, connectedness and the rotation of communities. In any case we establish the connection that exist among these notions. We also formulate the celebrated union-close set conjecture in the language of density of spots and the mass of a typical community.
Category: Combinatorics and Graph Theory

Unbelievable O(L^1.5) Worst Case Computational Complexity Achieved by Spdspds Algorithm for Linear Programming Problem

Authors: Keshava Prasad Halemane
Comments: 21 Pages. [Corrections made by viXra Admin to conform with scholarly norm]

The Symmetric Primal-Dual Symplex Pivot Decision Strategy (spdspds) is a novel iterative algorithm to solve linear programming problems. Here, a symplex pivoting operation is considered simply as an exchange between a basic (dependent) variable and a non-basic (independent) variable, in the Tucker’s Compact Symmetric Tableau (CST) which is a unique symmetric representation common to both the primal as well as the dual of a linear programming problem in its standard canonical form. From this viewpoint, the classical simplex pivoting operation of Dantzig may be considered as a restricted special case. The infeasibility index associated with a symplex tableau is defined as the sum of the number of primal variables and the number of dual variables, which are infeasible. A measure of goodness as a global effectiveness measure of a pivot selection is defined/determined as/by the decrease in the infeasibility index associated with such a pivot selection. At each iteration the selection of the symplex pivot element is governed by the anticipated decrease in the infeasibility index - seeking the best possible decrease in the infeasibility index - from among a wide range of candidate choices with non-zero values - limited only by considerations of potential numerical instability. The algorithm terminates when further reduction in the infeasibility index is not possible; then the tableau is checked for the terminal tableau type to facilitate the problem classification - a termination with an infeasibility index of zero indicates optimum solution. The worst case computational complexity of spdspds is shown to be O(L1.5).
Category: Combinatorics and Graph Theory

A Proof of the Union-Close Set Conjecture

Authors: Theophilus Agama
Comments: 6 Pages.

In this paper we introduce the notion of universe, induced communities and cells with their corresponding spots. Using this language we formulate and prove the union close set conjecture by showing that for any finite universe $\mathbb{U}$ and any induced community $\mathcal{M}_{\mathbb{U}}$ there exist some spot $a\in \mathbb{U}$ such that the density \begin{align} \mathcal{D}_{\mathcal{M}_{\mathbb{U}}}(a)\geq \frac{1}{2}.\nonumber \end{align}
Category: Combinatorics and Graph Theory

A Randomized 1.01241-Approximation Algorithm for Maximum Cut Problem

Authors: Majid Zohrehbandian
Comments: 7 Pages.

Maximum cut problem is a famous combinatorial problem, which its complexity has been heavily studied over the years. Among them is the efficient algorithm of Goemans and Williamson with an approximation factor roughly 1.13823≅1/0.878 (It is most often expressed as 0.878). Their algorithm combines semidefinite programming and a rounding procedure to produce an approximate solution to the maximum cut problem. In this paper, after introducing a new semidefinite programming formulation we present an improved randomized approximation with an approximation factor roughly 1.01241≅1/0.98775 .
Category: Combinatorics and Graph Theory

The Theory of Closed Cell Packaging Fields

Authors: Franz Hermann
Comments: 38 Pages.

In the first part of our study, we give definitions, examples, and properties of the simplest numerical packings. The second part talks about packages related to number systems. In the third part, we will talk about packages whose period is a prime number
Category: Combinatorics and Graph Theory

Any Finite Connected Poset is Isomorphic to Aut(x)\x for Some Finite Poset X

Authors: Pierre-Yves Gaillard
Comments: 2 Pages.

We show that, given any finite connected poset X, there is a finite poset Y such that the quotient poset Aut(Y)\Y is isomorphic to X.
Category: Combinatorics and Graph Theory

On the Minimal Uncompletable Word Problem for Unambiguous Automata

Authors: Antonio Boccuto, Arturo Carpi
Comments: 11 Pages.

This paper deals with nite (possibly not complete) unambiguous automata, not necessarily deterministic. In this setting, we investigate the problem of the minimal length of the uncompletable word. This problem is associated with the well-known conjecture formulated by A. Restivo. We introduce the concept of relatively maximal row for a suitable set of matrices, and show the existence of a relatively maximal row of length of quadratic order with respect to the number of the states of the treated automaton. We give some estimates of the maximal length of the minimal uncompletable word in connection with the number the states of the involved automaton and the length of a suitable relatively maximal but not maximal word, provided that it exists. In the general case, we establish an estimate of the length of the minimal uncompletable word in terms of the number of states of the studied automaton, the length of a suitable relatively maximal word and the minimal length of the uncompletable word of the automaton formed by all associated maximal rows.
Category: Combinatorics and Graph Theory

On the Euler Integral for the Positive and Negative Factorial

Authors: Tai-Choon Yoon, Yina Yoon
Comments: 10 Pages. [Heading "Abstract" added by viXra Admin]

We reviewed the Euler integral for the factorial, Gauss' Pi function, Legendre's gamma function and beta function, and found that gamma function is defective in $\Gamma(0)$ and $\Gamma(-x)$ because they are undefined or indefinable. And we came to a conclusion that the definition of a negative factorial, that covers the domain of the negative space, is needed to the Euler integral for the factorial, as well as the Euler $Y$ function and the Euler $Z$ function, that supersede Legendre's gamma function and beta function.
Category: Combinatorics and Graph Theory

On the Riemann Hypothesis and the Complex Numbers of the Riemann Zeta Function

Authors: Tai-Choon Yoon, Yina Yoon
Comments: 4 Pages. [Heading "Abstract" added by viXra Admin]

The Riemann product formula is provided with the function $\zeta(s)$ for all complex numbers from $\int_0^\infty\frac{x^{s-1}}{e^x-1}dx$ by substituting $-x$ only partly for $x$ in the numerator, which is incorrect, because we can find even negative factorials at the same place instead of the so-called trivial zero. And for Riemann hypothesis, we may derive out $q=\frac{2n\pi}{ln(a)}$ from the complex variable $z=\pm(p+iq)$ of the Riemann zeta function, which is applicable for all positive and negative planes and complex space including $\zeta(\frac{1}{2})$.
Category: Combinatorics and Graph Theory

Solution of an Open Problem Concerning the Augmented Zagreb Index and Chromatic Number of Graphs

Authors: Tariq Alraqad, Akbar Ali, Hicham Saber
Comments: 10 Pages.

Let $G$ be a graph containing no component isomorphic to the path graph of order $2$. Denote by $d_w$ the degree of a vertex $w$ in $G$. The augmented Zagreb index ($AZI$) of $G$ is the sum of the quantities $(d_ud_v/(d_u+d_v-2))^3$ over all edges $uv$ of $G$. Denote by $\mathcal{G}(n,\chi)$ the class of all connected graphs of a fixed order $n$ and with a fixed chromatic number $\chi$, where $n\ge5$ and $3\le \chi \le n-1$. The problem of finding graph(s) attaining the maximum $AZI$ in the class $\mathcal{G}(n,\chi)$ has been solved recently in [F. Li, Q. Ye, H. Broersma, R. Ye, MATCH Commun. Math. Comput. Chem. 85 (2021) 257--274] for the case when $n$ is a multiple of $\chi$. The present paper gives the solution of the aforementioned problem not only for the remaining case (that is, when $n$ is not a multiple of $\chi$) but also for the case considered in the aforesaid paper.
Category: Combinatorics and Graph Theory

Stirling Numbers Via Combinatorial Sums

Authors: Anwesh Bhattacharya
Comments: 13 Pages. Presented at MMLA 2019, PES University, Bangalore.

In this paper, we have derived a formula to find combinatorial sums of the type $\sum_{r=0}^n r^k {n\choose r}$ for $k \in \mathbb{N}$. The formula is conveniently expressed as a linear combination of terms involving the falling factorial. The co-efficients in this linear expression satisfy a recurrence relation, which is identical to that of the Stirling numbers of the first and second kind.
Category: Combinatorics and Graph Theory

The Theory of Quasi-crystalline Mosaic in the Correct Polygons

Authors: Franz Hermann
Comments: 27 Pages.

It is known that a regular polygon with an even number of sides can be paved with a rhombic mosaic with the rhombus side equal to the polygon side. This paper provides a generalization for constructing a rhombic mosaic for the case of any n-gon. in addition, we consider cases of constructing a rhombic-fractal mosaic of regular polygons. In addition, the hypothesis "about a combined mosaic" is formulated»
Category: Combinatorics and Graph Theory

A 3SDP Relaxation to Solve Vertex Cover Problem

Authors: Majid Zohrehbandian
Comments: 5 Pages.

Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied. It is known that it is hard to approximate to within any constant factor better than 2. In this paper, based on the addition of new constraints to the combination of 3 semidefinite programming (SDP) relaxations, we introduce a new stronger SDP relaxation for vertex cover problem which solve it exactly on general graphs. In this manner and by solving one of the NP-complete problems in polynomial time, we conclude that P=NP.
Category: Combinatorics and Graph Theory

On Some Chromatic Properties of Some Circulant Graphs

Authors: Prajnanaswaroopa S
Comments: 3 Pages.

Here we obtain the list chromatic index, list total chromatic number some of powers of cycles
Category: Combinatorics and Graph Theory

Motzkin Islands: a 3-dimensional Embedding of Motzkin Paths

Authors: Richard J. Mathar
Comments: 14 Pages.

A Motzkin Path is a walk left-to-right starting at the horizontal axis, consisting of up, down or horizontal steps, never descending below the horizontal axis, and finishing at the horizontal axis. Interpret Motzkin Paths as vertical geologic cuts through mountain ranges with limited slopes. The natural embedding of these paths defines Motzkin Islands as sets of graphs labeled on vertices by non-negative integers (altitudes), a graph cycle defining a shoreline at zero altitude, and altitude differences along edges never larger than one. We address some of these islands with simple shapes on triangular and quadratic meshes.
Category: Combinatorics and Graph Theory

К вопросу о непериодическом замощении плоскости

Authors: Franz Hermann
Comments: 20 Pages.

Как известно, вопрос о существовании фигуры, при помощи которой можно было бы замостить плоскость только непериодическими мозаиками до сих пор остаѐтся открытым. В данной заметке мы хотим предложить вниманию читателя, построенную нами фигуру, при помощи которой, при определѐнных начальных условиях замощения, непериодические мозаики строятся с намного большей вероятностью нежели периодические. Насколько нам известно, данную фигуру пока ещѐ никто не использовал для построения непериодических мозаик на плоскости. Забегая вперѐд можно сказать, что данные замощения носят характер квазикристаллических мозаик. По нашему мнению, именно этот факт, может быть, будет наиболее интересен для многих читателей.
Category: Combinatorics and Graph Theory

Making Derangements Using Element Swaps

Authors: Pranjal Jain
Comments: 16 Pages.

The aim of the article is to show that there always exists a sequence of swaps of elements, which when applied to a derangement (of n>3 elements) will go through all derangements of n elements, with an additional constraint that all swaps in this sequence produce a derangement (not necessarily one which hasn't appeared before in the sequence).
Category: Combinatorics and Graph Theory

On the Coloring of Efl Graph Using Colors Equal to Size of Maximal Clique

Authors: Prajnanaswaroopa S
Comments: 4 Pages. Comments are welcome

In this short note, we give a proof for the fact that the chromatic number of the EFL graph formed by the adjoining of k cliques such that any two cliques share at most one vertex is k
Category: Combinatorics and Graph Theory

Solving the 106 Years Old 3^k Points Problem with the Clockwise-Algorithm

Authors: Marco Ripà
Comments: 10 Pages. The first perfect solution of the 3x3x3x3 points problem has been explicitly drawn (40 lines).

In this paper, we present the clockwise-algorithm that solves the extension in k-dimensions of the infamous nine-dot problem, the well known two-dimensional thinking outside the box puzzle. We describe a general strategy that constructively produces minimum length covering trails, for any k∈N\{0}, solving the NP-complete (3 X 3 X … X 3)-points problem inside a 3 X 3 X … X 3 hypercube. In particular, using our algorithm, we explicitly draw different covering trails of minimal length h(k)=(3^k-1)/2 for k=3 and k=4, and we also conjecture that, for every k≥1, it is possible to solve the 3^k-points problem with h(k) lines starting from any of the 3^k nodes, except from the central one.
Category: Combinatorics and Graph Theory

The Vertices of a Graph and its Dimension

Authors: Volker Thürey
Comments: 7 Pages.

We show that the dimension of a graph is less or equal to the cardinality of the set of its vertices
Category: Combinatorics and Graph Theory

An Examination of Resourcing and Scheduling Within the RCMP

Authors: Bruce Rout
Comments: 74 Pages. MSc Thesis Simon Fraser University Dept. of Mathematics

The problem of resourcing and staffing, or finding how much manpower is needed to meet demand, can be traced back to the times of the Roman Empire. We examine here the various means used by the Royal Canadian Mounted Police in trying to solve this problem efficiently. We also examine their latest attack in building a simulator to determine future demands on resources and we provide a solution to determine efficient staffing levels through an application of a scheduling algorithm using “rods”. This algorithm is characterized as a rod-scheduling method which can be reduced to a linear program. It has been found that the previous methods used by police departments in Canada and the United States are extremely cumbersome. The methods suggested here correct this. Although the methods are very similar to those used before in other industries they haven’t been applied to police work. What was previously done in policing is to optimize very simple constraints first and then try to fit the results to the needs of the user. In this work I have suggested first obtaining all legal inputs and then optimizing to obtain a final answer. The author uses this method to investigate different types of demand data. Furthermore, different integer programming techniques are investigated. This document is meant for different users. It is hoped it can be read by various police departments as well as administrators and academics. In light of this the tone of the thesis is conversational. Much of the mathematical work is in sections three to seven.
Category: Combinatorics and Graph Theory

Pictures Instead of Formulae?

Authors: Valery Skorobogatov
Comments: 8 Pages. in Russian

It is suggested to use the pictures together with the mathematical formulae in physics.
Category: Combinatorics and Graph Theory

Self-Developing Structures (Саморазвивающиеся структуры)

Authors: Franz Hermann
Comments: Pages.

In memory of John Conway. New modification of the game "Life". Памяти Джона Конвея.Новая модификация игры "Жизнь".
Category: Combinatorics and Graph Theory

La (-1)-Reconstruction Des Graphes Symétriques à au Moins 3 éléments

Authors: Mohamed Sghiar
Comments: 9 Pages. Submited. Version Française

In this article, by algebraic and geometrical techniques, I give a proof to the famous conjecture of Ulam on the (-1)-reconstruction of the symmetric graphs with at least 3 elements conjectured in 1942, although was published only in 1960.
Category: Combinatorics and Graph Theory

Action Adjointe Sur Les Graphes et la Preuve de la Conjecture P=NP

Authors: Mohamed Sghiar
Comments: 10 Pages. Submited, Frensh version

I study the link between the adjoint action and the Hamiltonian cycles in a symmetric graph. Then by a simple algebraic resolution of a system of equations with several variables I find all the Hamiltonian cycles of the graph. Finally I will apply the results found to give an algorithm of order $ \mathcal{ O } (n ^ 3 ) $ allowing to quickly give all the Hamiltonian cycles with their distance. This gives a proof of the conjecture $ P = NP $.
Category: Combinatorics and Graph Theory

Four Color Theorem-simplified

Authors: Richard L. Hudson
Comments: 5 Pages.

The conjecture [1] stated that four colors are sufficient for any 2-dimensional plane map so that no two regions with a shared border are the same color. The conjecture is now a theorem [2], the result of a lengthy and complex proof, involving over 1000 classifications of graph objects and over 1000 hours of computer time.
Category: Combinatorics and Graph Theory

On a Function Modeling an L-Step Self Avoiding Walk Via Compression Balls

Authors: Theophilus Agama
Comments: 11 Pages.

We introduce and study the needle function \begin{align}(\Gamma_{\vec{a}_1} \circ \mathbb{V}_m)\circ \cdots \circ (\Gamma_{\vec{a}_{\frac{l}{2}}}\circ \mathbb{V}_m):\mathbb{R}^n\longrightarrow \mathbb{R}^n.\nonumber \end{align}We give an alternate proof of the fact that this function is a function modeling an $l$-step self avoiding walk. By exploiting the geometry of compression, we prove that this function is a function modeling an $l$-step self avoiding walk for $l\in \mathbb{N}$. We show that the total length of the $l$-step self-avoiding walk modeled by this function is of the order \begin{align}\ll \frac{l}{2}\sqrt{n}\bigg(\mathrm{\max}\{\mathrm{sup}(x_{j_k})\}_{\substack{1\leq j\leq \frac{l}{2}\\1\leq k\leq n}}+\mathrm{\max}\{\mathrm{sup}(a_{j_k})\}_{\substack{1\leq j\leq \frac{l}{2}\\1\leq k\leq n}}\bigg)\nonumber \end{align}and at least \begin{align}\gg \frac{l}{2}\sqrt{n}\bigg(\mathrm{\min}\{\mathrm{Inf}(x_{j_k})\}_{\substack{1\leq j\leq \frac{l}{2}\\1\leq k\leq n}}+\mathrm{\min}\{\mathrm{Inf}(x_{j_k})\}_{\substack{1\leq j\leq \frac{l}{2}\\1\leq k\leq n}}\bigg).\nonumber \end{align}
Category: Combinatorics and Graph Theory

Distribution of Boundary Points of Expansion and Application to the Lonely Runner Conjecture

Authors: Theophilus Agama
Comments: 8 Pages.

In this paper we study the distribution of boundary points of expansion. As an application, we say something about the lonely runner problem. We show that given $k$ runners $\mathcal{S}_i$ round a unit circular track with the condition that at some time $||\mathcal{S}_i-\mathcal{S}_{i+1}||=||\mathcal{S}_{i+1}-\mathcal{S}_{i+2}||$ for all $i=1,2\ldots,k-2$, then at that time we have \begin{align}||\mathcal{S}_{i+1}-\mathcal{S}_i||>\frac{\mathcal{D}(n)\pi}{k-1}\nonumber \end{align}for all $i=1,\ldots, k-1$ and where $\mathcal{D}(n)>0$ is a constant depending on the degree of a certain polynomial of degree $n$. In particular, we show that given at most eight $\mathcal{S}_i$~($i=1,2,\ldots, 8$) runners running round a unit circular track with distinct constant speed and the additional condition $||\mathcal{S}_i-\mathcal{S}_{i+1}||=||\mathcal{S}_{i+1}-\mathcal{S}_{i+2}||$ for all $1\leq i\leq 6$ at some time $s>1$, then at that time their mutual distance must satisfy the lower bound\begin{align}||\mathcal{S}_{i}-\mathcal{S}_{i+1}||>\frac{\pi}{7C\sqrt{3}}\nonumber \end{align}for some constant $C>0$ for all $1\leq i \leq 7$.
Category: Combinatorics and Graph Theory

Operations on Neutrosophic Vague Graphs

Authors: N. Durga, S. Satham Hussain, Saeid Jafari, Said Broumi
Comments: 26 Pages.

In this manuscript, the operations on neutrosophic vague graphs are introduced. Moreover, Cartesian product, cross product, lexicographic product, strong product and composition of neutrosophic vague graph are investigated and the proposed concepts are illustrated with examples.
Category: Combinatorics and Graph Theory

On a Function Modeling $n$-Step Self Avoiding Walk

Authors: Theophilus Agama
Comments: 6 Pages.

We introduce and study the needle function. We prove that this function is a function modeling $n$-step self avoiding walk. We show that the total length of the $l$-step self-avoiding walk modeled by this function is of the order \begin{align}\ll \frac{n^{\frac{3}{2}}}{2}\bigg(\mathrm{\max}\{\mathrm{sup}(x_j)\}_{1\leq j\leq \frac{l}{2}}+\mathrm{max}\{\mathrm{sup}(a_j)\}_{1\leq j\leq \frac{l}{2}}\bigg).\nonumber \end{align}
Category: Combinatorics and Graph Theory

Counting Partitions

Authors: M. D. Sheppeard
Comments: 4 Pages.

In this lecture we count the number of integer partitions P(n) using an elementary algorithm based on the combinatorics of trees, coded using free apps on the iPad.
Category: Combinatorics and Graph Theory

Yes, P = NP=NP-Complete=NP-hard, says the NP-hard Traveling Salesman Problem

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

The solution of the traveling salesman problem (TSP) in this paper makes this problem no longer an NP-hard problem, but rather, a P problem. The TSP was solved in polynomial time and its solution was also correctly checked in polynomial time. Also solved were an NP-Complete TSP, and six other NP-Complete problems. The TSP solution killed two (three) birds with one stone, because its solution made the NP-hard problems and NP-Complete problems become P problems. The shortest route as well as the longest route for the salesman to visit each of nine cities once and return to the base city was determined. In finding the shortest route, the first step was to arrange the data of the problem in increasing order, since one's interest is in the shortest distances; but in finding the longest route, the first step was to arrange the data of the problem in decreasing order, since one's interest is in the longest distances. For the shortest route, the main principle 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; but for the longest route, the main principle is that the longest route is the sum of the longest distances such that the salesman visits each city once and returns to the starting city. Since ten cities are involved, ten distances would be needed for the salesman to visit each of nine cities once and return to the starting city. One started the construction of the shortest route using only the shortest ten distances; and if a needed distance was not among the set of the shortest ten distances, one would consider distances longer than those in the set of the shortest ten distances. For the longest route, the construction began using only the longest ten distances; and if a needed distance was not among the set of the longest ten distances, one would consider distances shorter than those in the set of the longest ten distances. It was found out that even though, the length of the shortest or the longest route is unique, the sequence of the cities involved is not unique. The approach used in this paper can be applied in work-force project management and hiring, as well as in a country's work-force needs and immigration quota determination. Since approaches that solve the TSP and NP-Complete problems can also solve other NP problems, and the TSP and NP-Complete problems have been solved, all NP problems can be solved. 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

A Calculating Method About How May `comparable' Pairs of Elements Exist in a Certain Set

Authors: Yasushi Ieno
Comments: 15 Pages.

Given two sets, one consisting of variables representing distinct positive n numbers, the other set `a kind of power set' of this n-element set. I got interested in the fact that for the latter set, depending on the values of two elements, it can occur that not every pair of elements is `comparable', that is to say, it is not always uniquely determined which of two elements is smaller. By proving theorems in order to go ahead with our research, we show a table which describes for how many `comparable' cases exist, for several n's.
Category: Combinatorics and Graph Theory

Another Research for Solving the Grasshopper Problem(imo)

Authors: Yasushi Ieno
Comments: 7 Pages.

The 6th problem of the 50th International Mathematical Olympiad (IMO), held in Germany, 2009, is called 'the grasshopper problem'. To this problem Kos developed theory from unique viewpoints by reference of Noga Alon's combinatorial Nullstellensatz. We have tried to solve this problem by an original method inspired by a polynomial that Kos defined, then researched for n=3 and n=4. For almost cases the problem can be solved, but there remains imperfection due to 'singularity'.
Category: Combinatorics and Graph Theory

The Labelled Cycle-Decomposition Trees of a Connected Graph

Authors: Ortho Flint, Stuart Rankin
Comments: 10 Pages. The labelled cycle-decomposition trees are a powerful invariant and computationally inexpensive to produce.

The notion of a labelled cycle-decomposition tree for an arbitrary graph is introduced in this paper. The idea behind the labelled cycle-decomposition tree, one constructed for each vertex in the graph, is to attach to each vertex a data structure that gives more than local information about the vertex, where the data structures can be compared in polynomial time. The fact that trees can be compared in linear time, with particularly efficient algorithms for solving the isomorphism problem for rooted and labelled trees, led us to consider how we could represent the vertex's view of the graph by means of a labelled rooted tree. Of course, cycles in the graph can't be directly recorded by means of a tree structure, but in this article, we present one method for recording certain of the cycles that are encountered during a breadth-first search from the vertex in question. The collection of labelled, so-called cycle-decomposition trees for the graph, one for each vertex, provide an invariant of the graph.
Category: Combinatorics and Graph Theory

Difference Cordial Labeling of the Graphs Related to Duplication of an Edge or Vertex of a Cycle and Total Graph

Authors: A. Sugumaran, V. Mohan
Comments: 13 Pages.

Abstract. A difference cordial labeling of a graph G is a bijective function f from V(G) onto {1, 2, 3, ⋯ , |V(G)|} such that each edge uv is assigned the label 1 if |f(u) – f(v)| = 1, and the label 0 otherwise, satisfying the condition that the number of edges labeled with 1 and the number of edges labeled with 0 differ by at most 1. A graph with difference cordial labeling is called a difference cordial graph. In this paper we proved that the umbrella graph U(m, n), duplication of a vertex by an edge in a cycle Cn, duplication of an edge by a vertex in a cycle Cn and the total graph of a path Pn are difference cordial graphs.
Category: Combinatorics and Graph Theory

A Polynomial Time and Non-Heuristic Solution for NP-Complete Problems (Clique, TSP & Sudoku)(P=NP)

Authors: John Archie Gillis
Comments: 30 Pages.

The present article takes a novel approach to solving NP-Complete problems and provides steps that a computational device and software program can follow to accurately solve NP-class problems without the use of heuristics or brute force methods. The present methods are fast and accurate if utilized properly. The paper states that the solution to solving the P vs NP question (and our ability to design algorithms to solve such problems efficiently) lies in a novel method presented for searching, filtering, combining and structuring data, which describes a novel method for breaking specific problems into logical groupings that the present inventor (John Archie Gillis) has defined as collaborative variables. They utilize novel binary representations/conversions, so that one can more easily and quickly determine selected and desired informational outputs. Many have stated that a solution to this problem will create the world’s first trillionaire as it addresses many pattern-matching and optimization problems that are of great practical interest, such as determining the optimal arrangement of transistors on a silicon chip, developing accurate financial-forecasting models, or analyzing protein-folding behaviour in a cell. Since all the NP-complete optimization problems become easy with the present methods, everything will be much more efficient. Transportation of all forms can now also be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. Developments in vision recognition, language comprehension, translation and many other learning tasks will now become much simpler as well. It is felt that by utilizing the systems of the present invention in numerous fields, that the present paper will have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, internet packet routing, multimedia processing, philosophy, economics and many other fields.
Category: Combinatorics and Graph Theory

The Construction of Cospectral Graphs with Respect to the Generalized Adjacency Matrix

Authors: Daria Grushka, Viktoriia Lebid
Comments: 4 Pages. Text in Ukrainian. Mohyla Mathematical Journal, Vol 1 (2018) http://mmj.ukma.edu.ua/article/view/152600

Spectral graph theory uses the eigenvalues of matrices associated with a graph to determine the structural properties of the graph. The spectrum of the generalized adjacency matrix is considered in the paper. Graphs with the same spectrum are called cospectral. Is every graph uniquely determined by its spectrum (DS for short)? This question goes back for about half a century, and originates from chemistry. In 1956 Gunthard and Primas raised the question in a paper that related the theory of graph spectra to Huckel’s theory. At that time it was believed that every graph is determined by the spectrum, until in 1957 Collatz and Sinogowitz presented a pair of cospectral trees. In 1967 Schwenk proved that for almost all trees there is another tree with the same spectrum. Such a statement is neither proved nor refuted for the class of graphs in general. Till now, computational experiments were done on the set of all graphs on up to 12 vertices by Haemers. Computer enumerations for small n show that up to 10 vertices the fraction of graphs that are DS decreases, but for n = 11 and n = 12 it increases again. We consider the construction of the cospectral graphs called GM-switching for graph G taking the cycle C2n and adjoining a vertex v adjacent to half the vertices of C2n. For these graphs we determine the pairs of cospectral nonisomorphic graphs for small n. It is an operation on graphs that leaves the spectrum of the generalized adjacency matrix invariant. It turns out that for the enumerated cases a large part of all cospectral graphs comes from GM switching, and that the fraction of graphs on n vertices with a cospectral mate starts to decrease at some value of n < 11 (depending on the matrix). Since the fraction of cospectral graphs on n vertices constructible by GM switching tends to 0 if n → ∞, the present data give some indication that possibly almost no graph has a cospectral mate. Haemers and Spence derived asymptotic lower bounds for the number of graphs with a cospectral mate from GM switching.
Category: Combinatorics and Graph Theory

Solving the N_1 X N_2 X N_3 Points Problem for N_3 < 6

Authors: Marco Ripà
Comments: 12 Pages. Original research paper © Marco Ripà - unpublished and unsubmitted before on any journal

In this paper, we show enhanced upper bounds of the nontrivial n_1 × n_2 × n_3 points problem for every n_1 ≤ n_2 ≤ n_3 < 6. We present new patterns that drastically improve the previously known algorithms for finding minimum-link covering paths, solving completely a few cases (e.g., n_1 = n_2 = 3 and n_3 = 4).
Category: Combinatorics and Graph Theory

On the Coloring of Graphs Formed by Cliques Sharing at Most One Common Vertex

Authors: Prajnanaswaroopa S, J Geetha, K Somasundaram
Comments: 3 Pages.

In this short note, we give a coloring procedure for graphs which consist of cliques sharing at most one point
Category: Combinatorics and Graph Theory

Die Würfelschlange

Authors: Henning Thielemann
Comments: 5 Pages. Language: German

The dice sequence The dice sequence is an adaption of Kruskal's card trick to dice. We compute precise and approximated probabilities that the trick works. The adaption to dice simplifies the problem considerably because the probabilities of the dice rolls are independent. Initially I wrote the text for Wikipedia but in order to meet Wikipedia's exclusion of original research I wrote up this paper.
Category: Combinatorics and Graph Theory

Corrigendum to "Polyomino Enumeration Results. (Parkin et Al., Siam Fall Meeting 1967)"

Authors: Richard J. Mathar
Comments: 17 Pages.

This work provides a Java program which constructs free polyominoes of size n sorted by width and height of the convex hull (i.e., its rectangular bounding box). The results correct counts for 15-ominoes published in the 1967 proceedings of the SIAM Fall Meeting, and extend them to 16-ominoes and partially to even larger polyominoes.
Category: Combinatorics and Graph Theory

A New Algebraic Approach to the Graph Isomorphism and Clique Problems

Authors: Roman Galay
Comments: 7 Pages. The following short article offers a couple of algebraically entangled polynomial-time algorithms for the graph isomorphism and clique problems whose correctness is yet to be determined either empirically or through attempting to find proofs.

As it follows from Gödel's incompleteness theorems, any consistent formal system of axioms and rules of inference should imply a true unprovable statement. Actually this fundamental principle can be efficiently applicable in Computational Mathematics and Complexity Theory concerning the computational complexity of problems from the class NP, particularly and especially the NP-complete ones. While there is a wide set of algorithms for these problems that we call heuristic, the correctness or/and complexity of each concrete algorithm (or the probability of its correct and polynomial-time work) on a class of instances is often too difficult to determine, although we may also assume the existence of a variety of algorithms for NP-complete problems that are both correct and polynomial-time on all the instances from a given class (where the given problem remains NP-complete), but whose correctness or/and polynomial-time complexity on the class is impossible to prove as an example for Gödel's theorems. However, supposedly such algorithms should possess a certain complicatedness of processing the input data and treat it in a certain algebraically “entangled” manner. The same algorithmic analysis in fact concerns all the other significant problems and subclasses of NP, such as the graph isomorphism problem and its associated complexity class GI. The following short article offers a couple of algebraically entangled polynomial-time algorithms for the graph isomorphism and clique problems whose correctness is yet to be determined either empirically or through attempting to find proofs.
Category: Combinatorics and Graph Theory

Introducing: Second-Order Permutation

Authors: Bassey Godwin Bassey
Comments: 29 Pages.

In this study we answer questions that have to do with finding out the total number of ways of arranging a finite set of symbols or objects directly under a single line constraint set of finite symbols such that common symbols between the two sets do not repeat on the vertical positions. We go further to study the outcomes when both sets consist of the same symbols and when they consist of different symbols. We identify this form of permutation as 'second-order permutation' and show that it has a corresponding unique factorial which plays a prominent role in most of the results obtained. This has been discovered by examining many practical problems which give rise to the emergence of second-order permutation. Upon examination of these problems, it becomes clear that a directly higher order of permutation exist. Hence this study aims at equipping mathematics scholars, educators and researchers with the necessary background knowledge and framework for incorporating second-order permutation into the field of combinatorial mathematics.
Category: Combinatorics and Graph Theory

Even FibBinary Numbers and the Golden Ratio

Authors: J Gregory Moxness
Comments: 4 Pages.

Previously, a determination of the relationship between the Natural numbers (N) and the n'th odd fibbinary number has been made using a relationship with the Golden ratio \phi=(Sqrt[5]+1}/2 and \tau=1/\phi. Specifically, if the n'th odd fibbinary equates to the j'th N, then j=Floor[n(\phi+1) - 1]. This note documents the completion of the relationship for the even fibbinary numbers, such that if the n'th even fibbinary equates to the j'th N, then j=Floor[n(\tau+1) + \tau].
Category: Combinatorics and Graph Theory

Алгоритм нахождения подстановок

Authors: Франц Герман
Comments: 3 Pages.

В некоторых задачах, решаемых на компьютере, возникает необходимость нахождения перестановок из n элементов. Для небольших n это можно сделать простым перебором, но с увеличением n, нахождение всех перестановок перебором становится занятием очень трудоёмким. В таком случае удобно применять следующий алгоритм.
Category: Combinatorics and Graph Theory

NP ≠ co-NP

Authors: Robert DiGregorio
Comments: 2 Pages. fix error in proof

We prove that class NP ≠ class co-NP.
Category: Combinatorics and Graph Theory

Sigmoid Fictionization of Magnetization in the Spin-Glass Ising Model

Authors: Akira Saito
Comments: 4 Pages.

The magnetization of the spin-glass Ising model can be expressed using a sigmoid function. In the ground state, the magnetization is determined by solving a set of nonlinear simultaneous equations, each corresponding to a magnetization. As the magnetization of the ground state in the spin-glass Ising model constitutes an NP-complete problem, the P=NP problem can be reformulated as solving these nonlinear simultaneous equations. If practical computation yields result that are feasible, it can be essentially considered as P=NP. Furthermore, all interacting systems in nature can be represented by sigmoid functions, and the ground state can be obtained by solving nonlinear simultaneous equations.
Category: Combinatorics and Graph Theory

Detecting Whether a Graph Has a Fixed-Point-Free Automorphisms is in Polynomial Time

Authors: Yasunori Ohto
Comments: 11 Pages.

The problem of determining whether a graph has a fixed-point-free automorphism is NP-complete. We demonstrate that the problem can be solved efficiently within polynomial time. First, we obtain the automorphisms of an input graph G by using a spectral method. Next, we prove the Theorem used to detect whether there is a fixed-point free automorphism in G. Next, we construct an algorithm to detect whether G has a fixed-point-free automorphism using this result. The computational complexity of detecting whether a graph has a fixed-point-free automorphism is O(n^5). If fixed-point-free automorphism exist, the computational complexity of obtaining a fixed-point-free automorphism is O(n^6). Then, the complexity classes P and NP are the same.
Category: Combinatorics and Graph Theory

Detecting Whether a Graph Has a Fixed-point-free Automorphisms Is in Polynomial Time

Authors: Yasunori Ohto
Comments: 7 Pages. We have improved the readability of the paper for submission to a workshops.

The problem that to determining whether a graph has a fixed-point-free automorphism is NP-complete. We show that it is solvable in polynomial time. First, we obtain the automorphisms of an input graph G by using a spectral method. Next, we prove the Theorem used to detect whether there is a fixed-point free automorphism in G. Next, we construct an algorithm to detect whether G has a fixed-point-free automorphism using this result. This algorithm cannot obtain a fixed-point-free automorphism even if it exists. The computational complexity of this problem is O(n^5). Then, the complexity classes P and NP are the same.
Category: Combinatorics and Graph Theory

Solving Graph Isomorphism Problem in Polynomial Time

Authors: Yasunori Ohto
Comments: 7 Pages.

We show that the graph isomorphism problem is solvable in polynomial time. First, we prove the theorem to obtain the automorphisms of G using eigenvalue sets. Next, we construct an algorithm to determine whether two given graphs G_a and G_b are isomorphic using this result. The computational complexity to detect whether the two graphs are isomorphic is O(n^6).
Category: Combinatorics and Graph Theory

A (1.999999)-Approximation Ratio for Vertex Cover Problem

Authors: Majid Zohrehbandian
Comments: 10 Pages.

Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied over the years and while a 2-approximation for it can be trivially obtained, researchers have not been able to approximate it better than 2-o(1). In this paper, by a combination of a new semidefinite programming formulation along with satisfying new proposed properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of 1.999999 on arbitrary graphs, en route to answering an open question about the correctness/incorrectness of the unique games conjecture.
Category: Combinatorics and Graph Theory

A (1.999999)-Approximation Ratio for Vertex Cover Problem

Authors: Majid Zohrehbandian
Comments: 7 Pages.

The vertex cover problem is a famous combinatorial problem, and its complexity has been heavily studied over the years. While a 2-approximation for it can be trivially obtained, researchers have not been able to approximate it better than 2-o(1). In this paper, by a combination of a new semidefinite programming formulation along with satisfying new proposed properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of 1.999999 on arbitrary graphs, en route to answering an open question about the correctness/incorrectness of theunique games conjecture.
Category: Combinatorics and Graph Theory

Harmonic Graphs Conjecture: Graph-Theoretic Attributes and their Number Theoretic Correlations

Authors: Felipe Correa Rodríguez
Comments: 6 Pages. Perfected version. I posted this but time has passed already and there weren't updates on the replacement, so I fear a mistake.

The Harmonic Graphs Conjecture states that there exists an asymptotic relation involving the Harmonic Index and the natural logarithm as the order of the graph increases. This conjecture, grounded in the novel context of Prime Graphs, draws upon the Prime Number Theorem and the sum of divisors function to unveil a compelling asymptotic connection. By carefully expanding the definitions of the harmonic index and the sum of divisors function, and leveraging the prime number theorem's approximations, we establish a formula that captures this intricate relationship. This work is an effort to contribute to the advancement of graph theory, introducing a fresh lens through which graph connectivity can be explored. The synthesis of prime numbers and graph properties not only deepens our understanding of structural complexity but also paves the way for innovative research directions.
Category: Combinatorics and Graph Theory

General Conjecture on the Optimal Covering Trails in a K-Dimensional Cubic Lattice

Authors: Marco Ripà
Comments: 7 Pages.

We introduce a general conjecture involving minimum-link covering trails for any given k-dimensional grid n × n × ··· × n, belonging to the cubic lattice ℕ^k. In detail, if n is above two, we hypothesize that the minimal link length of any covering trail, for the above-mentioned set of n^k points in the Euclidean space ℝ^k, is equal to h(n, k) = (n^k − 1)/(n − 1) + c·(n − 3), where c = k − 1 iff h(4, 3) = 23, c = 1 iff h(4, 3) = 22, or even c = 0 iff h(4, 3) = 21.
Category: Combinatorics and Graph Theory

"N_1 × N_2 × ... × N_K Dots Puzzle": an Optimal General Algorithm

Authors: Valerio Bencini
Comments: 36 Pages.

In this paper, we show a new algorithm for the "n_1 × n_2 × ... × n_k dots puzzle" (an extension of the well-known "nine dots puzzle" of Samuel Loyd), able to solve completely the problem for the case "k=2" and, at the same time, provide lower upper bounds for the other cases.
Category: Combinatorics and Graph Theory

"N_1 × N_2 × ... × N_K Dots Puzzle": an Optimal General Algorithm

Authors: Valerio Bencini
Comments: 36 Pages.

In this paper, we show a new algorithm for the "n_1 × n_2 × ... × n_k dots puzzle" (an extension of the well-known "nine dots puzzle" of Samuel Loyd), able to solve completely the problem for the case "k=2" and, at the same time, provide lower upper bounds for the other cases.
Category: Combinatorics and Graph Theory

"N_1 × N_2 × ... × N_k Dots Puzzle": an Optimal General Algorithm

Authors: Valerio Bencini
Comments: 36 Pages.

In this paper, we show a new algorithm for the "n_1 × n_2 × ... × n_k dots puzzle" (an extension of the well-known "nine dots puzzle" of Samuel Loyd), able to solve completely the problem for the case "k=2" and, at the same time, provide lower upper bounds for the other cases.
Category: Combinatorics and Graph Theory

"N_1 × N_2 × ... × N_k Dots Puzzle": an Optimal General Algorithm

Authors: Valerio Bencini
Comments: 34 Pages. In Italian

In this paper, we show a new algorithm for the "n_1 × n_2 × ... × n_k dots puzzle" (an extension of the well-known "nine dots puzzle" of Samuel Loyd), able to solve completely the problem for the case "k=2" and, at the same time, provide lower upper bounds for the other cases.
Category: Combinatorics and Graph Theory

Graph Equations

Authors: Elmar Guseinov
Comments: 18 Pages.

В данной статье приводится решение 83 проблем, формулировка которых близка к формулировке гипотезы грациозности деревьев. Для оптимизации процесса решения была написана соответствующая рекомендательная программа.

This article provides a solution to 83 problems, the formulation of which is close to the formulation of the graceful tree conjecture. To optimize the solution process, an appropriate recommendation system was written.
Category: Combinatorics and Graph Theory

Propriétés Inédites Des Coefficients Binomiaux

Authors: Réjean Labrie
Comments: 5 Pages.

Apart from the Vandermonde identity there are very few other identities composed of a summation of products of binomial coefficients. Here are four new identities of this type to insert into our mathematical toolbox. An induction demonstration then formalizes these new formulas that highlight unsuspected properties of binomial coefficients.
Category: Combinatorics and Graph Theory

Invariant Property of Binomial Coefficients

Authors: Rejean Labrie
Comments: 7 Pages.

Although many properties of Pascal's triangle are known, few of them correspond to a summation of products of binomial coefficients. The written property here comes to enrich this last group but it is characterized especially by its invariance.
Category: Combinatorics and Graph Theory

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

A Randomized 1.885903-Approximation Algorithm for the Minimum Vertex Cover Problem

Authors: Majid Zohrehbandian
Comments: 7 Pages. Due to some comments, I preferred to add some explanations.

Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied over the years and we know that there is not any mathematical formulation that approximates it better than 2-o(1). In other words, it is known that it is hard to approximate to within any constant factor better than 2, while a 2-approximation for it can be trivially obtained. In this paper, by a combination of a well-known semidefinite programming formulation and a rounding procedure, along with satisfying new properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of 1.885903 on arbitrary graphs, en route answering an open question about the unique games conjecture.
Category: Combinatorics and Graph Theory

A Probabilistic Solution for the Syracuse Conjecture

Authors: Imad El ghazi
Comments: 6 Pages.

We prove the veracity of the Syracuse conjecture by establishing that starting from an arbitrary positive integer diffrent of $1$ and $4$, the Syracuse process will never comeback to any positive integer reached before and then we conclude by using a probabilistic approach.
Category: Combinatorics and Graph Theory

A Probabilistic Solution for the Syracuse Conjecture

Authors: Imad El ghazi
Comments: 6 Pages.

We prove the veracity of the Syracuse conjecture by establishing that starting from an arbitrary positive integer different of 1 and 4, the Syracuse process will never comeback to any positive integer reached before and then we conclude by using a probabilistic approach.
Category: Combinatorics and Graph Theory

A Probabilistic Solution for the Syracuse Conjecture

Authors: Imad El Ghazi
Comments: 7 Pages.

We prove the veracity of the Syracuse conjecture by establishing that starting from an arbitrary positive integer diffrent of 1 and 4, the Syracuse process will never comeback to any positive integer reached before and then we conclude by using a probabilistic approach.
Category: Combinatorics and Graph Theory

On Sums of Product of Powers of Palindromic Sequence and Arithmetic Progression

Authors: Lateef Suaib
Comments: 9 Pages.

In this paper, we combine a real or complex palindromic sequence and arithmetic sequence to produce the sums of product of powers of palindromic-arithmetic sequences. As a result, we generate new expressions for Franel numbers as well as first Strehl identity.
Category: Combinatorics and Graph Theory

On Sums of Product of Powers of Palindromic Sequence and Arithmetic Progression

Authors: Suaib Lateef
Comments: 9 pages

In this paper, we combine a real or complex palindromic sequence, (i.e, a sequence that remains the same when the sequence is reversed) with a sequence in arithmetic progression to produce the sums of product of powers of palindromic sequence and arithmetic progression. As a result, we establish a relationship between the sum of n terms of an arithmetic progression, the sum of their squares, the sum of their cubes, and the number of terms. Also, we establish a relationship between the sum of n terms of an arithmetic progression, the sum of their squares, the sum of their cubes, the sum of their fourth powers, the sum of their fifth powers and the number of terms. We also give two new different expressions for Franel numbers as well as the right-hand side of first Strehl identity.
Category: Combinatorics and Graph Theory

New Insight Into Introducing a (2-ℇ)-Approximation Ratio for Minimum Vertex Cover Problem

Authors: Majid Zohrehbandian
Comments: 9 Pages.

Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied over the years and it is known that there is not any mathematical programming formulation that approximates it better than 2-o(1), while a 2-approximation for it can be trivially obtained. In this paper, by a combination of a well-known semidefinite programming formulation and a randomized procedure, along with satisfying new properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of 1.999999 on arbitrary graphs, en route to answering an open question about the unique games conjecture.
Category: Combinatorics and Graph Theory

New Insight Into Introducing a (2-ℇ)-Approximation Ratio for Minimum Vertex Cover Problem

Authors: Majid Zohrehbandian
Comments: 7 Pages.

Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied over the years and we know that there is not any mathematical formulation that approximates it better than 2-o(1). In other words, it is known that it is hard to approximate to within any constant factor better than 2, while a 2-approximation for it can be trivially obtained. In this paper, by a combination of a well-known semidefinite programming formulation and a rounding procedure, along with satisfying new properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of 1.999999 on arbitrary graphs, en route answering an open question about the unique games conjecture.
Category: Combinatorics and Graph Theory

New Insight Into Introducing a (2-ℇ)-Approximation Ratio for Minimum Vertex Cover Problem

Authors: Majid Zohrehbandian
Comments: 7 Pages.

Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied over the years. It is known that it is hard to approximate to within any constant factor better than 2, while a 2-approximation for it can be trivially obtained. In this paper, new properties and new techniques are introduced which lead to approximation ratios smaller than 2 on special graphs. Then, by a combination of semidefinite programming and a rounding procedure, along with satisfying the proposed assumptions, we introduce an approximation algorithm with a performance ratio of 1.999999 on arbitrary graphs.
Category: Combinatorics and Graph Theory

New Insight Into Introducing a (2-ℇ)-Approximation Ratio for Minimum Vertex Cover Problem

Authors: Majid Zohrehbandian
Comments: 8 Pages.

Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied. It is known that it is hard to approximate to within any constant factor better than 2, while a 2-approximation for it can be trivially obtained. In this paper, new properties and new techniques are introduced which lead to approximation ratios smaller than 2 on special graphs. Then, by introducing a modified graph and corresponding model along with satisfying the proposed assumptions, we propose new insight into solving this open problem and we introduce an approximation algorithm with a performance ratio of 1.999999 on arbitrary graphs.
Category: Combinatorics and Graph Theory

An Extension of the Erd\h{o}s-Tur\'{a}n Additive Base Conjecture Via Generalized Circles of Partition

Authors: Theophilus Agama
Comments: 7 Pages. A detailed proof of the corollary has been added

In this paper we continue the development of the method of Circles of Partition by introducing the notion of generalized circles of partition. This is an extension program of the notion of circle of partition developed in our first paper \cite{CoP}. As an application we prove an analogue of the Erd\H{o}s-Tur\'{a}n additive base conjecture.
Category: Combinatorics and Graph Theory

An Extension of the Erd\h{o}s-Tur\'{a}n Additive Base Conjecture Via Generalized Circles of Partition

Authors: Theophilus Agama
Comments: 6 Pages. A detailed exposition added with a proof of the Erdos-Turan additive base conjecture as a new corollary.

In this paper we continue the development of the method of Circles of Partition by introducing the notion of generalized circles of partition. This is an extension program of the notion of circle of partition developed in our first paper \cite{CoP}. As an application we prove an analogue of the Erd\H{o}s-Tur\'{a}n additive base conjecture.
Category: Combinatorics and Graph Theory

A Proof of the Union-Close Set Conjecture

Authors: Theophilus Agama
Comments: 6 Pages.

In this paper we introduce the notion of universe, induced communities and cells with their corresponding spots. Using this language we formulate and prove the union close set conjecture by showing that for any finite universe $\mathbb{U}$ and any induced community $\mathcal{M}_{\mathbb{U}}$ there exist some spot $a\in \mathbb{U}$ such that the density \begin{align} \mathcal{D}_{\mathcal{M}_{\mathbb{U}}}(a)\geq \frac{1}{2}.\nonumber \end{align}
Category: Combinatorics and Graph Theory

Stirling Numbers Via Combinatorial Sums

Authors: Anwesh Bhattacharya
Comments: 10 Pages. Presented at MMLA 2019, PES University, Bangalore.

In this paper, we have derived a formula to find combinatorial sums of the type $\sum_{r=0}^n r^k {n\choose r}$ for $k \in \mathbb{N}$. The formula is conveniently expressed as a linear combination of terms involving the falling factorial. The co-efficients in this linear expression satisfy a recurrence relation, which is identical to that of the Stirling numbers of the first and second kind.
Category: Combinatorics and Graph Theory

Solving the 106 Years Old 3^k Points Problem with the Clockwise-Algorithm

Authors: Marco Ripà
Comments: Pages.

In this paper, we present the clockwise-algorithm that solves the extension in k-dimensions of the infamous nine-dot problem, the well known two-dimensional thinking outside the box puzzle. We describe a general strategy that constructively produces minimum length covering trails, for any k∈N−{0}, solving the NP-complete (3×3×⋯×3)-points problem inside a 3×3×⋯×3 hypercube. In particular, using our algorithm, we explicitly draw different covering trails of minimal length h(k) = (3^k − 1)/2, for k = 3, 4, 5. Furthermore, we conjecture that, for every k ≥ 1, it is possible to solve the 3^k-points problem with h(k) lines starting from any of the 3^k nodes, except from the central one. Finally, we cover 3×3×3 points with a tree of size 12.
Category: Combinatorics and Graph Theory

La (-1)-Reconstruction Des Graphes Symétriques à au Moins 3 éléments

Authors: Mohamed sghiar
Comments: 8 Pages. French and accepted version

In this article, by algebraic and geometrical techniques, I give a proof to the famous Ulam's conjecture on the (-1)-reconstruction of the symmetric graphs with at least 3 elements conjectured in 1942, although was published only in 1960.
Category: Combinatorics and Graph Theory

On a Function Modeling an L-Step Self Avoiding Walk

Authors: Theophilus Agama
Comments: 14 Pages. A few technicalities resolved regarding the scale of compression and the inequality in the notion of points contained in a compression ball has been made strict. This is because the case of equality is treated separately as admissible points.

We introduce and study the needle \begin{align}(\Gamma_{\vec{a}_1} \circ \mathbb{V}_m)\circ \cdots \circ (\Gamma_{\vec{a}_{\frac{l}{2}}}\circ \mathbb{V}_m):\mathbb{R}^n\longrightarrow \mathbb{R}^n.\nonumber \end{align} By exploiting the geometry of compression, we prove that this function is a function modeling an $l$-step self avoiding walk for $l\in \mathbb{N}$. We show that the total length of the $l$-step self-avoiding walk modeled by this function is of the order \begin{align}\ll \frac{l}{2}\sqrt{n}\bigg(\mathrm{\max}\{\mathrm{sup}(x_{j_k})\}_{\substack{1\leq j\leq \frac{l}{2}\\1\leq k\leq n}}+\mathrm{\max}\{\mathrm{sup}(a_{j_k})\}_{\substack{1\leq j\leq \frac{l}{2}\\1\leq k\leq n}}\bigg)\nonumber \end{align}and at least \begin{align}\gg \frac{l}{2}\sqrt{n}\bigg(\mathrm{\min}\{\mathrm{Inf}(x_{j_k})\}_{\substack{1\leq j\leq \frac{l}{2}\\1\leq k\leq n}}+\mathrm{\min}\{\mathrm{Inf}(a_{j_k})\}_{\substack{1\leq j\leq \frac{l}{2}\\1\leq k\leq n}}\bigg).\nonumber \end{align}
Category: Combinatorics and Graph Theory

On a Function Modeling an L-Step Self Avoiding Walk

Authors: Theophilus Agama
Comments: 14 Pages. A revision file in response to Referee comments

We introduce and study the needle function \begin{align}(\Gamma_{\vec{a}_1} \circ \mathbb{V}_m)\circ \cdots \circ (\Gamma_{\vec{a}_{\frac{l}{2}}}\circ \mathbb{V}_m):\mathbb{R}^n\longrightarrow \mathbb{R}^n.\nonumber \end{align} By exploiting the geometry of compression, we prove that this function is a function modeling an $l$-step self avoiding walk for $l\in \mathbb{N}$. We show that the total length of the $l$-step self-avoiding walk modeled by this function is of the order \begin{align}\ll \frac{l}{2}\sqrt{n}\bigg(\mathrm{\max}\{\mathrm{sup}(x_{j_k})\}_{\substack{1\leq j\leq \frac{l}{2}\\1\leq k\leq n}}+\mathrm{\max}\{\mathrm{sup}(a_{j_k})\}_{\substack{1\leq j\leq \frac{l}{2}\\1\leq k\leq n}}\bigg)\nonumber \end{align}and at least \begin{align}\gg \frac{l}{2}\sqrt{n}\bigg(\mathrm{\min}\{\mathrm{Inf}(x_{j_k})\}_{\substack{1\leq j\leq \frac{l}{2}\\1\leq k\leq n}}+\mathrm{\min}\{\mathrm{Inf}(a_{j_k})\}_{\substack{1\leq j\leq \frac{l}{2}\\1\leq k\leq n}}\bigg).\nonumber \end{align}
Category: Combinatorics and Graph Theory

Collatz Conjecture: A Proof

Authors: Richard Hudson
Comments: 7 Pages.

Originated by Lothar Collatz in 1937 [1], the conjecture states: given the recursive function, y=3x+1 if x is odd, or y=x/2 if x is even, for any positive integer x, y will equal 1 after a finite number of steps. This analysis examines number form and uses a tree type graph to prove the process.
Category: Combinatorics and Graph Theory

Yes, P = NP = NP-Complete = NP-hard, says the NP-hard Traveling Salesman Problem

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

The solution of the traveling salesman problem (TSP) in this paper makes this problem no longer an NP-hard problem, but rather, a P problem. The TSP was solved in polynomial time and its solution was also correctly checked in polynomial time. Also solved were an NP-Complete TSP, and six other NP-Complete problems. The TSP solution killed two (three) birds with one stone, because its solution made the NP-hard problems and NP-Complete problems become P problems. The shortest route as well as the longest route for the salesman to visit each of nine cities once and return to the base city was determined. In finding the shortest route, the first step was to arrange the data of the problem in increasing order, since one's interest is in the shortest distances; but in finding the longest route, the first step was to arrange the data of the problem in decreasing order, since one's interest is in the longest distances. For the shortest route, the main principle 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; but for the longest route, the main principle is that the longest route is the sum of the longest distances such that the salesman visits each city once and returns to the starting city. Since ten cities are involved, ten distances would be needed for the salesman to visit each of nine cities once and return to the starting city. One started the construction of the shortest route using only the shortest ten distances; and if a needed distance was not among the set of the shortest ten distances, one would consider distances longer than those in the set of the shortest ten distances. For the longest route, the construction began using only the longest ten distances; and if a needed distance was not among the set of the longest ten distances, one would consider distances shorter than those in the set of the longest ten distances. It was found out that even though, the length of the shortest or the longest route is unique, the sequence of the cities involved is not unique. The approach used in this paper can be applied in work-force project management and hiring, as well as in a country's work-force needs and immigration quota determination. Since approaches that solve the TSP and NP-Complete problems can also solve other NP problems, and the TSP and NP-Complete problems have been solved, all NP problems can be solved. 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

Yes, P = NP=NP-Complete=NP-hard, says the NP-hard Traveling Salesman Problem

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

The solution of the traveling salesman problem (TSP) in this paper makes this problem no longer an NP-hard problem, but rather, a P problem. The TSP was solved in polynomial time and its solution was also correctly checked in polynomial time. Also solved were an NP-Complete TSP, and six other NP-Complete problems. The TSP solution killed two (three) birds with one stone, because its solution made the NP-hard problems and NP-Complete problems become P problems. The shortest route as well as the longest route for the salesman to visit each of nine cities once and return to the base city was determined. In finding the shortest route, the first step was to arrange the data of the problem in increasing order, since one's interest is in the shortest distances; but in finding the longest route, the first step was to arrange the data of the problem in decreasing order, since one's interest is in the longest distances. For the shortest route, the main principle 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; but for the longest route, the main principle is that the longest route is the sum of the longest distances such that the salesman visits each city once and returns to the starting city. Since ten cities are involved, ten distances would be needed for the salesman to visit each of nine cities once and return to the starting city. One started the construction of the shortest route using only the shortest ten distances; and if a needed distance was not among the set of the shortest ten distances, one would consider distances longer than those in the set of the shortest ten distances. For the longest route, the construction began using only the longest ten distances; and if a needed distance was not among the set of the longest ten distances, one would consider distances shorter than those in the set of the longest ten distances. It was found out that even though, the length of the shortest or the longest route is unique, the sequence of the cities involved is not unique. The approach used in this paper can be applied in work-force project management and hiring, as well as in a country's work-force needs and immigration quota determination. Since approaches that solve the TSP and NP-Complete problems can also solve other NP problems, and the TSP and NP-Complete problems have been solved, all NP problems can be solved. 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

A Computing Method About How Many `comparable' Pairs of Elements Exist in a Certain Set

Authors: Yasushi Ieno
Comments: 17 Pages.

Given two sets, one consisting of variables representing distinct positive n numbers, the other set `a kind of power set' of this n-element set. I got interested in the fact that for the latter set, depending on the values of two elements, it can occur that not every pair of elements is `comparable', that is to say, it is not always uniquely determined which of two elements is smaller. By proving theorems in order to go ahead with our research, we show a table which describes for how many `comparable' cases exist, for several n's.
Category: Combinatorics and Graph Theory

A Computing Method About How Many `comparable' Pairs of Elements Exist in a Certain Set

Authors: Yasushi Ieno
Comments: 16 Pages.

Given two sets, one consisting of variables representing distinct positive n numbers, the other set `a kind of power set' of this n-element set. I got interested in the fact that for the latter set, depending on the values of two elements, it can occur that not every pair of elements is `comparable', that is to say, it is not always uniquely determined which of two elements is smaller. By proving theorems in order to go ahead with our research, we show a table which describes for how many 'comparable' cases exist, for several n's.
Category: Combinatorics and Graph Theory

A Calculating Method About How Many `comparable' Pairs of Elements Exist in a Certain Set

Authors: Yasushi Ieno
Comments: 16 Pages.

Given two sets, one consisting of variables representing distinct positive n numbers, the other set `a kind of power set' of this n-element set. I got interested in the fact that for the latter set, depending on the values of two elements, it can occur that not every pair of elements is `comparable', that is to say, it is not always uniquely determined which of two elements is smaller. By proving theorems in order to go ahead with our research, we show a table which describes for how many `comparable' cases exist, for several n's.
Category: Combinatorics and Graph Theory

Invitation to Hadamard Matrices

Authors: Teo Banica
Comments: 400 Pages.

An Hadamard matrix is a square matrix $Hin M_N(pm1)$ whose rows and pairwise orthogonal. More generally, we can talk about the complex Hadamard matrices, which are the square matrices $Hin M_N(mathbb C)$ whose entries are on the unit circle, $|H_{ij}|=1$, and whose rows and pairwise orthogonal. The main examples are the Fourier matrices, $F_N=(w^{ij})$ with $w=e^{2pi i/N}$, and at the level of the general theory, the complex Hadamard matrices can be thought of as being some sort of exotic, generalized Fourier matrices. We discuss here the basic theory of the Hadamard matrices, real and complex, with emphasis on the complex matrices, and their geometric and analytic aspects.
Category: Combinatorics and Graph Theory

Another Method to Solve the Grasshopper Problem (The International Mathematical Olympiad)

Authors: Yasushi Ieno
Comments: 31 Pages.

The 6th problem of the 50th International Mathematical Olympiad (IMO), held in Germany, 2009, is called 'the grasshopper problem'. To this problem Kos developed theory from unique viewpoints by reference of Noga Alon’s combinatorial Nullstellensatz. We have tried to solve this problem by an original method inspired by a polynomial function that Kos defined, then examined for n=3, 4 and 5. For almost cases the claim of this problem follows, but there remains imperfection due to 'singularity'.
Category: Combinatorics and Graph Theory

Another Method to Solve the Grasshopper Problem (The International Mathematical Olympiad)

Authors: Yasushi Ieno
Comments: 30 Pages.

The 6th problem of the 50th International Mathematical Olympiad (IMO), held in Germany, 2009, is called 'the grasshopper problem'. To this problem Kos developed theory from unique viewpoints by reference of Noga Alon’s combinatorial Nullstellensatz. We have tried to solve this problem by an original method inspired by a polynomial function that Kos defined, then examined for n=3, 4 and 5. For almost cases the claim of this problem follows, but there remains imperfection due to 'singularity'.
Category: Combinatorics and Graph Theory

Another Method to Solve the Grasshopper Problem(imo)

Authors: Yasushi Ieno
Comments: 28 Pages.

The 6th problem of the 50th International Mathematical Olympiad (IMO), held in Germany, 2009, is called 'the grasshopper problem'. To this problem Kos developed theory from unique viewpoints by reference of Noga Alon’s combinatorial Nullstellensatz. We have tried to solve this problem by an original method inspired by a polynomial function that Kos defined, then examined for n=3, 4 and 5. For almost cases the claim of this problem follows, but there remains imperfection due to 'singularity'.
Category: Combinatorics and Graph Theory

Another Method to Solve the Grasshopper Problem(imo)

Authors: Yasushi Ieno
Comments: 28 Pages.

The 6th problem of the 50th International Mathematical Olympiad (IMO), held in Germany, 2009, is called 'the grasshopper problem'. To this problem Kos developed theory from unique viewpoints by reference of Noga Alon’s combinatorial Nullstellensatz. We have tried to solve this problem by an original method inspired by a polynomial function that Kos defined, then researched for n=3, 4 and 5. For almost cases the claim of this problem follows, but there remains imperfection due to 'singularity'.
Category: Combinatorics and Graph Theory

Another Method to Solve the Grasshopper Problem(imo)

Authors: Yasushi Ieno
Comments: 27 Pages.

The 6th problem of the 50th International Mathematical Olympiad (IMO), held in Germany, 2009, is called 'the grasshopper problem'. To this problem Kos developed theory from unique viewpoints by reference of Noga Alon’s combinatorial Nullstellensatz. We have tried to solve this problem by an original method inspired by a polynomial function that Kos defined, then researched for n=3, 4 and 5. For almost cases the claim of this problem follows, but there remains imperfection due to 'singularity'.
Category: Combinatorics and Graph Theory

Another Method to Solve the Grasshopper Problem(imo)

Authors: Yasushi Ieno
Comments: 25 Pages.

The 6th problem of the 50th International Mathematical Olympiad (IMO), held in Germany, 2009, is called 'the grasshopper problem'. To this problem Kos developed theory from unique viewpoints by reference of Noga Alon’s combinatorial Nullstellensatz. We have tried to solve this problem by an original method inspired by a polynomial function that Kos defined, then researched for n=3, 4 and 5. For almost cases the problem can be solved, but there remains imperfection due to 'singularity'.
Category: Combinatorics and Graph Theory

Another Method to Solve the Grasshopper Problem(imo)

Authors: Yasushi Ieno
Comments: 25 Pages.

The 6th problem of the 50th International Mathematical Olympiad (IMO), held in Germany, 2009, is called 'the grasshopper problem'. To this problem Kos developed theory from unique viewpoints by reference of Noga Alon’s combinatorial Nullstellensatz. We have tried to solve this problem by an original method inspired by a polynomial function that Kos defined, then researched for n=3, 4 and 5. For almost cases the problem can be solved, but there remains imperfection due to 'singularity'.
Category: Combinatorics and Graph Theory

Another Method to Solve the Grasshopper Problem(imo)

Authors: Yasushi Ieno
Comments: 7 Pages.

The 6th problem of the 50th International Mathematical Olympiad (IMO), held in Germany, 2009, is called 'the grasshopper problem'. To this problem Kos developed theory from unique viewpoints by reference of Noga Alon's combinatorial Nullstellensatz. We have tried to solve this problem by an original method inspired by a polynomial function that Kos defined, then researched for n=3 and n=4. For almost cases the problem can be solved, but there remains imperfection due to 'singularity'.
Category: Combinatorics and Graph Theory

Some Facts on Permanents in Finite Characteristics

Authors: Anna Knezevic, Greg Cohen, Marina Domanskaya
Comments: 85 pages; this research was partly supported by the School of Electrical Engineering, Computing and Mathematical Sciences of the Curtin University (Australia) whose member is one of the authors (Anna Knezevic)

The permanent’s polynomial-time computability over fields of characteristic 3 for k-semiunitary matrices (i.e. n×n-matrices A such that ��������(����^�� − ��_��) = ��) in the case k ≤ 1 and its #3P-completeness for any k > 1 (Ref. 9) is a result that essentially widens our understanding of the computational complexity boundaries for the permanent modulo 3. Now we extend this result to study more closely the case k > 1 regarding the (n-k)×(n-k)sub-permanents (or permanent-minors) of a unitary n×n-matrix and their possible relations, because an (n-k)×(n-k)-submatrix of a unitary n×n-matrix is generically a ksemi-unitary (n-k)×(n-k)-matrix. The following paper offers a way to receive a variety of such equations of different sorts, in the meantime extending (in its second chapter divided into subchapters) this direction of research to reviewing all the set of polynomial-time permanent-preserving reductions and equations for a generic matrix’s sub-permanents they might yield, including a number of generalizations and formulae (valid in an arbitrary prime characteristic) analogical to the classical identities relating the minors of a matrix and its inverse. Moreover, the second chapter also deals with the Hamiltonian cycle polynomial in characteristic 2 that surprisingly demonstrates quite a number of properties very similar to the corresponding ones of the permanent in characteristic 3. Besides, the paper’s third chapter is devoted to the computational complexity issues of the permanent and some related functions on a variety of Cauchy matrices and their certain generalizations, including constructing a polynomial-time algorithm (based on them) for the permanent of an arbitrary square matrix in characteristic 5 and conjecturing the existence of a similar scheme in characteristic 3. Throughout the paper, we investigate various matrix compressions and transformations preserving the permanent and related functions in certain finite characteristics. And, as an auxiliary algebraic tool supposed for an application when needed in all the constructions we’re going to discuss in the present article, we’ll introduce and utilize a special principle involving a field’s extension by a formal infinitesimal and allowing, provided a number of conditions are fulfilled, to reduce the computation of a polynomial over a field to solving a system of algebraic equations in polynomial time
Category: Combinatorics and Graph Theory

Some Facts on Permanents in Finite Characteristics

Authors: Anna Knezevic, Greg Cohen, Marina Domanskaya
Comments: 85 Pages. this research was partly supported by the School of Electrical Engineering, Computing and Mathematical Sciences of the Curtin University (Australia) whose member is one of the authors (Anna Knezevic)

The permanent’s polynomial-time computability over fields of characteristic 3 for k-semiunitary matrices (i.e. n×n-matrices A such that ��������(����^�� − ��_��) = ��) in the case k ≤ 1 and its #3P-completeness for any k > 1 (Ref. 9) is a result that essentially widens our understanding of the computational complexity boundaries for the permanent modulo 3. Now we extend this result to study more closely the case k > 1 regarding the (n-k)×(n-k)sub-permanents (or permanent-minors) of a unitary n×n-matrix and their possible relations, because an (n-k)×(n-k)-submatrix of a unitary n×n-matrix is generically a ksemi-unitary (n-k)×(n-k)-matrix. The following paper offers a way to receive a variety of such equations of different sorts, in the meantime extending (in its second chapter divided into subchapters) this direction of research to reviewing all the set of polynomial-time permanent-preserving reductions and equations for a generic matrix’s sub-permanents they might yield, including a number of generalizations and formulae (valid in an arbitrary prime characteristic) analogical to the classical identities relating the minors of a matrix and its inverse. Moreover, the second chapter also deals with the Hamiltonian cycle polynomial in characteristic 2 that surprisingly demonstrates quite a number of properties very similar to the corresponding ones of the permanent in characteristic 3. Besides, the paper’s third chapter is devoted to the computational complexity issues of the permanent and some related functions on a variety of Cauchy matrices and their certain generalizations, including constructing a polynomial-time algorithm (based on them) for the permanent of an arbitrary square matrix in characteristic 5 and conjecturing the existence of a similar scheme in characteristic 3. Throughout the paper, we investigate various matrix compressions and transformations preserving the permanent and related functions in certain finite characteristics. And, as an auxiliary algebraic tool supposed for an application when needed in all the constructions we’re going to discuss in the present article, we’ll introduce and utilize a special principle involving a field’s extension by a formal infinitesimal and allowing, provided a number of conditions are fulfilled, to reduce the computation of a polynomial over a field to solving a system of algebraic equations in polynomial time
Category: Combinatorics and Graph Theory

Solving the N_1 × N_2 × N_3 Points Problem for N_3 < 6

Authors: Marco Ripà
Comments: 13 Pages. Revised version

In this paper, we show enhanced upper bounds of the nontrivial n_1 × n_2 × n_3 points problem for every n_1 ≤ n_2 ≤ n_3 < 6. We present new patterns that drastically improve the previously known algorithms for finding minimum-link covering paths, completely solving the fundamental case n_1 = n_2 = n_3 = 3.
Category: Combinatorics and Graph Theory

Solving the N_1 × N_2 × N_3 Points Problem for N_3 < 6

Authors: Marco Ripà
Comments: 13 Pages. The three-dimensional extension of the immortal nine-dot problem has finally been solved!

In this paper, we show enhanced upper bounds of the nontrivial n_1 × n_2 × n_3 points problem for every n_1 ≤ n_2 ≤ n_3 < 6. We present new patterns that drastically improve the previously known algorithms for finding minimum-link covering paths, completely solving the fundamental case n_1 = n_2 = n_3 = 3.
Category: Combinatorics and Graph Theory

Solving the N_1 X N_2 X N_3 Points Problem for N_3 < 6

Authors: Marco Ripà
Comments: 12 Pages.

In this paper, we show enhanced upper bounds of the nontrivial n_1 × n_2 × n_3 points problem for every n_1 ≤ n_2 ≤ n_3 < 6. We present new patterns that drastically improve the previously known algorithms for finding minimum-link covering paths, solving completely a few cases (e.g., n_1 = n_2 = 3 and n_3 = 4).
Category: Combinatorics and Graph Theory

Solving the N_1 X N_2 X N_3 Points Problem for N_3 < 6

Authors: Marco Ripà
Comments: 12 Pages. This paper has not been submitted before to any peer-reviewed journal © Marco Ripà

In this paper, we show enhanced upper bounds of the nontrivial n_1 × n_2 × n_3 points problem for every n_1 ≤ n_2 ≤ n_3 < 6. We present new patterns that drastically improve the previously known algorithms for finding minimum-link covering paths, solving completely a few cases (e.g., n_1 = n_2 = 3 and n_3 = 4).
Category: Combinatorics and Graph Theory

Solving the N_1 X N_2 X N_3 Points Problem for N_3 < 6

Authors: Marco Ripà
Comments: 12 Pages. This paper has not been submitted before to any peer-reviewed journal © Marco Ripà

In this paper, we show enhanced upper bounds of the nontrivial n_1 × n_2 × n_3 points problem for every n_1 ≤ n_2 ≤ n_3 < 6. We present new patterns that drastically improve the previously known algorithms for finding minimum-link covering paths, solving completely a few cases (e.g., n_1 = n_2 = 3 and n_3 = 4).
Category: Combinatorics and Graph Theory

Solving the N_1 X N_2 X N_3 Points Problem for N_3 < 6

Authors: Marco Ripà
Comments: 12 Pages.

In this paper, we show enhanced upper bounds of the nontrivial n_1 × n_2 × n_3 points problem for every n_1 ≤ n_2 ≤ n_3 < 6. We present new patterns that drastically improve the previously known algorithms for finding minimum-link covering paths, solving completely a few cases (e.g., n_1 = n_2 = 3 and n_3 = 4).
Category: Combinatorics and Graph Theory

Corrigendum to "Polyomino Enumeration Results. (Parkin et al., SIAM Fall Meeting 1967)"

Authors: Richard J. Mathar
Comments: 39 Pages. Version 3 includes refined statistics according to perimeter.

This work provides a Java program which constructs free polyominoes of size n sorted by width and height of the convex hull (i.e., its rectangular bounding box). The results correct counts for 15-ominoes published in the 1967 proceedings of the SIAM Fall Meeting, and extend them to 17-ominoes and partially to even larger polyominoes. [vixra:1905.0474]
Category: Combinatorics and Graph Theory

Corrigendum to "Polyomino Enumeration Results. (Parkin et Al., Siam Fall Meeting 1967)"

Authors: Richard J. Mathar
Comments: 28 Pages. In Version 2: All results for 17-ominoes. Java code with option for parallel threads.

This work provides a Java program which constructs free polyominoes of size n sorted by width and height of the convex hull (i.e., its rectangular bounding box). The results correct counts for 15-ominoes published in the 1967 proceedings of the SIAM Fall Meeting, and extend them to 17-ominoes and partially to even larger polyominoes. [vixra:1905.0474]
Category: Combinatorics and Graph Theory

A New Algebraic Approach to the Graph Isomorphism and Clique Problems

Authors: Roman Galay
Comments: 12 Pages. The following short article offers a couple of algebraically entangled polynomial-time algorithms for the graph isomorphism and clique problems whose correctness is yet to be determined either empirically or through attempting to find proofs.

As it follows from Gödel's incompleteness theorems, any consistent formal system of axioms and rules of inference should imply a true unprovable statement. Actually this fundamental principle can be efficiently applicable in Computational Mathematics and Complexity Theory concerning the computational complexity of problems from the class NP, particularly and especially the NP-complete ones. While there is a wide set of algorithms for these problems that we call heuristic, the correctness or/and complexity of each concrete algorithm (or the probability of its correct and polynomial-time work) on a class of instances is often too difficult to determine, although we may also assume the existence of a variety of algorithms for NP-complete problems that are both correct and polynomial-time on all the instances from a given class (where the given problem remains NP-complete), but whose correctness or/and polynomial-time complexity on the class is impossible to prove as an example for Gödel's theorems. However, supposedly such algorithms should possess a certain complicatedness of processing the input data and treat it in a certain algebraically “entangled” manner. The same algorithmic analysis in fact concerns all the other significant problems and subclasses of NP, such as the graph isomorphism problem and its associated complexity class GI. The following short article offers a couple of algebraically entangled polynomial-time algorithms for the graph isomorphism and clique problems whose correctness is yet to be determined either empirically or through attempting to find proofs.
Category: Combinatorics and Graph Theory

A New Algebraic Approach to the Graph Isomorphism and Clique Problems

Authors: Roman Galay
Comments: 8 Pages. The following short article offers a couple of algebraically "entangled" polynomial-time algorithms for the graph isomorphism and clique problems whose correctness is yet to be determined either empirically or through attempting to find proofs.

As it follows from Gödel's incompleteness theorems, any consistent formal system of axioms and rules of inference should imply a true unprovable statement. Actually this fundamental principle can be efficiently applicable in Computational Mathematics and Complexity Theory concerning the computational complexity of problems from the class NP, particularly and especially the NP-complete ones. While there is a wide set of algorithms for these problems that we call heuristic, the correctness or/and complexity of each concrete algorithm (or the probability of its correct and polynomial-time work) on a class of instances is often too difficult to determine, although we may also assume the existence of a variety of algorithms for NP-complete problems that are both correct and polynomial-time on all the instances from a given class (where the given problem remains NP-complete), but whose correctness or/and polynomial-time complexity on the class is impossible to prove as an example for Gödel's theorems. However, supposedly such algorithms should possess a certain complicatedness of processing the input data and treat it in a certain algebraically “entangled” manner. The same algorithmic analysis in fact concerns all the other significant problems and subclasses of NP, such as the graph isomorphism problem and its associated complexity class GI. The following short article offers a couple of algebraically entangled polynomial-time algorithms for the graph isomorphism and clique problems whose correctness is yet to be determined either empirically or through attempting to find proofs.
Category: Combinatorics and Graph Theory