Combinatorics and Graph Theory

Previous months:
2009 - 0908(1)
2010 - 1001(3) - 1003(4) - 1004(1) - 1006(1) - 1009(1) - 1010(1)
2011 - 1101(1) - 1103(1) - 1106(1)
2012 - 1202(2) - 1204(1) - 1208(2) - 1209(2) - 1210(3) - 1211(2)
2013 - 1303(1) - 1304(3) - 1305(2) - 1306(1) - 1307(5) - 1308(2) - 1309(7) - 1310(2) - 1311(2)
2014 - 1401(1) - 1403(2) - 1404(2) - 1408(1)

Recent submissions

Any replacements are listed further down

[56] viXra:1408.0040 [pdf] submitted on 2014-08-07 22:36:44

Try to re-Prove 4-Color Theorem

Authors: Oh Jung Uk
Comments: 8 Pages.

The point of inside closed curve could not directly connect to the point of outside. If a point of outside closed curve directly connect to points on closed curve then the maximum number of color of map is 4 under only 3 conditions, and the end point of closed curve is located inside newly created closed curve. If another outside point is added then we could prevent maximum color from exceeding 4 by using to rearrange colors of existing points.
Category: Combinatorics and Graph Theory

[55] viXra:1404.0447 [pdf] submitted on 2014-04-23 11:36:30

Fibonacci Quarternions

Authors: John Frederick Sweeney
Comments: 18 Pages.

Pascal’s Triangle, originally Mount Meru of Vedic Physics, provides the perfect format for a combinatorial Universe, with its binomial coefficients, as well as its ease of determining Fibonacci Numbers. Matrix and Clifford algebras, in the form of the chart above, can be shaped into a form identical with Pascal’s Triangle. At the same time, a Romanian researcher has devised an algorithm for determining a Fibonacci Number as a quarternion. This paper poses the question as to whether the Clifford Pyramid contains properties similar to Pascal's Triangle.
Category: Combinatorics and Graph Theory

[54] viXra:1404.0066 [pdf] submitted on 2014-04-08 12:32:15

On the K-Clique Problems: a New Approach

Authors: Dhananjay P. Mehendale
Comments: 9 pages.

In this paper we discuss new approach to deal with k-clique problems or their equivalents, namely, k-independent set problems.
Category: Combinatorics and Graph Theory

[53] viXra:1403.0965 [pdf] submitted on 2014-03-28 22:18:01

On the Reconstruction of Graphs

Authors: Dhananjay P. Mehendale
Comments: 2 pages,

Reconstruction conjecture asks whether it is possible to reconstruct a unique (up to isomorphism) graph from set of its one vertex deleted subgraphs. We show here the validity of reconstruction conjecture for every connected graph which is uniquely reconstructible from the set of all its spanning trees. We make use of a well known result, namely, the reconstruction of a tree from the deck of its pendant point deleted subtrees.
Category: Combinatorics and Graph Theory

[52] viXra:1403.0037 [pdf] submitted on 2014-03-06 14:32:33

Combinatorial Analysis

Authors: Giuseppe Rauti
Comments: 1 Page.

Lecture notes in Combinatorial Analysis.
Category: Combinatorics and Graph Theory

[51] viXra:1401.0130 [pdf] submitted on 2014-01-17 19:44:31

A Written Proof of the Four-Colors Map Problem

Authors: Zhang Tianshu
Comments: 21 Pages.

A contact border of two adjacent figures can only be two adjacent borderlines. Let us consider the plane of any uncolored planar map as which consists of two kinds’ parallel straight linear segments according to a strip of a kind alternating a strip of another, and every straight linear segment of each kind consists of two kinds of colored points according to a colored point of a kind alternating a colored point of another, either kind of colored points at a straight linear segment is not alike to either kind of colored points at either adjacent straight linear segment of the straight linear segment. Anyhow the plane has altogether four kinds of colored points. At the outset, we need transform and classify figures at an uncolored planar map. First merge orderly each figure which adjoins at most three figures and an adjacent figure which adjoins at least four figures into a figure. Secondly merge each tract of figures which adjoin at most three figures and an adjacent figure into a figure. After that, transform every borderline closed curve of figures which compose directly the merging figure into the frame of a rectangle which has only longitudinal and transversal sides, according to the sequence from outside merging figure to inside merging figure. Finally color each figure with a color according to either a color of some particular points of a rectangular borderlines closed curve of the figure, or a color unlike colors of its adjacent figures.
Category: Combinatorics and Graph Theory

[50] viXra:1311.0117 [pdf] submitted on 2013-11-17 05:07:57

The Innovation Game Theory

Authors: Adefokun Tomiwa Michael, Adefokun Tayo Charles
Comments: 4 Pages.

The Innovation Game Theory (IGT) is designed to help businesses, organizations and communities in formulating an approach to their innovation activities in the form of scientific game. As such, leaders, growth managers, theorists, inventors, innovators and consumers visualize the process of overcoming challenges their businesses or communities face (known or unknown) as though it is a game where all strategic actions and resources involved in tackling the challenges are expressed in terms of quantifiable values which are ultimately tied to certain competitive reward mechanisms.
Category: Combinatorics and Graph Theory

[49] viXra:1311.0044 [pdf] submitted on 2013-11-06 09:31:14

A New Calculus on the Ring of Symmetric Functions and Its Applications

Authors: Yusuke Iwahashi
Comments: 7 Pages.

This paper develops a new calculus on the ring of symmetric functions and introduces its application. In the last of this paper, the author describes a new general method to expand any symmetric function in terms of a basis in the ring of symmetric functions. For application of it, the author also mentions a general way to evaluate the transition matrix between any two bases in the ring of symmetric functions.
Category: Combinatorics and Graph Theory

[48] viXra:1310.0229 [pdf] submitted on 2013-10-25 13:12:48

Graceful Labeling for Trees

Authors: Dhananjay P. Mehendale
Comments: 10 pages

We establish the existence of graceful labeling for any unlabeled tree by proposing actual construction procedure for such labeling. We define so called lattice and lattice paths sitting inside it. A lattice path is produced by starting with bottom (or top) row of the lattice and choosing one lattice point per row in the lattice in succession and joining these lattice points. With these lattice points we associate vertex pairs representing edges in a complete graph. It obviously follows that each of so called lattice path represents a graceful graph and further it easily follows that there exist in all n! graceful graphs (among which some are trees) in a complete graph on n vertices. In this paper we propose an algorithm to construct graceful labeling for any given unlabeled tree through construction of appropriate lattice path for this tree under consideration.
Category: Combinatorics and Graph Theory

[47] viXra:1310.0023 [pdf] submitted on 2013-10-05 03:30:14

Mathematics for the Planet Earth

Authors: Nehul Yadav
Comments: 13 Pages. Please reply back to me at nehul12@gmail.com

This research conceptualises the the theories in mathematics with ecology and our evolution. It traces the link between the planet earth with mathematics. It uses calculus , graphs , combinatorics and other theories an models in mathematics. Hope it gets published!
Category: Combinatorics and Graph Theory

[46] viXra:1309.0063 [pdf] submitted on 2013-09-09 11:36:24

Graphs with Contributions to Fundamental Groups

Authors: Linfan Mao
Comments: 44 Pages.

Study of combinatorial spaces and smarandache multispaces.
Category: Combinatorics and Graph Theory

[45] viXra:1309.0062 [pdf] submitted on 2013-09-09 11:39:24

Labeling, Covering and Decomposing of Graphs

Authors: Linfan Mao
Comments: 56 Pages.

This report survey the smarandache system, labeling graphs and others in the classical graph theory.
Category: Combinatorics and Graph Theory

[44] viXra:1309.0061 [pdf] submitted on 2013-09-09 11:41:53

Geometry on Combinatorial Structures

Authors: Linfan Mao
Comments: 56 Pages.

Combinatorial structures underlying things, Topology of Combinatorial Manifold, and Differentiationon Combinatorial Manifold are the topics of this paper.
Category: Combinatorics and Graph Theory

[43] viXra:1309.0060 [pdf] submitted on 2013-09-09 11:46:30

Extending Homomorphism Theorem to Multi-Systems

Authors: Linfan Mao
Comments: 22 Pages.

An axiom is said smarandachely denied (S-denied) if in the same space the axiom behaves differently, i.e., validated and Invalided, or only invalidated but in at least two distinct ways. And a Smarandache multi-space is a union of n different spaces equipped with some different structures for an integer n≧2. This paper studies them.
Category: Combinatorics and Graph Theory

[42] viXra:1309.0059 [pdf] submitted on 2013-09-09 11:48:05

Labeled Graphs with Combinatorial Manifolds

Authors: Linfan Mao
Comments: 27 Pages.

I will prescribe limitation on following topics and mainly concentrate on myself works for combinatorially differential geometry, particularly, the combinatorial counterpart in recent years.
Category: Combinatorics and Graph Theory

[41] viXra:1309.0058 [pdf] submitted on 2013-09-09 11:49:41

Combinatorial World

Authors: Linfan Mao
Comments: 43 Pages.

Applications of Voltage Assignament to Principal Fiber Bundles.
Category: Combinatorics and Graph Theory

[40] viXra:1309.0057 [pdf] submitted on 2013-09-09 12:01:40

Non-Solvable Equation Systems with Graphs Embedded in R^n

Authors: Linfan Mao
Comments: 36 Pages.

We study the Smarandache Systems with Labeled Topological Graphs. A rule R in a mathematical system (Sigma; R) is said to be Smarandachely denied if it behaves in at least two different ways within the same set Sigma, i.e. validated and invalided, or only invalided but in multiple distinct ways. A Smarandache system (Sigma;R) is a system that has at least one smarandachely denied rule R.
Category: Combinatorics and Graph Theory

[39] viXra:1308.0037 [pdf] submitted on 2013-08-06 19:55:15

Smarandache Multi-Spaces & Combinatorial Mathematics

Authors: Linfan Mao
Comments: 73 Pages.

A Smarandache multi-space is a union of n different spaces equipped with some different structures, for an integer n≧2.
Category: Combinatorics and Graph Theory

[38] viXra:1308.0030 [pdf] submitted on 2013-08-05 21:42:13

Estrada Index of Graphs

Authors: Mohammed Kasim, Fumao Zhang, Qiang Wang
Comments: 6 Pages.

Suppose $G$ is a simple graph. The eigenvalues $\delta_1, \delta_2,\ldots, \delta_n$ of $G$ are the eigenvalues of its adjacency matrix $A$. The Estrada index of the graph $G$ is defined as $EE = EE(G) = \Sigma_{i=1}^{n} e^{\delta_i}$. In this paper the basic properties of $EE$ are investigated. Moreover, some lower and upper bounds for the Estrada index in terms of the number of vertices, edges and the Randic index are obtained. In addition, some relations between $EE$ and graph energy $E(G)$ are presented.
Category: Combinatorics and Graph Theory

[37] viXra:1307.0095 [pdf] submitted on 2013-07-19 21:01:04

Nine Dots Puzzle Extended to N_1 X N_2 X … X N_k Points Under House Arrest

Authors: Marco Ripà
Comments: The paper is 5 pages long and it is in Italian. Copyright: © 2013 Ripà

Here is the second and last part of the generalized solution to the extended “Nine Dots Puzzle”. In this paper I provide a non-trivial Lower Bound for the k-dimensional n_1 X n_2 X … X n_k points problem. In this way, you can build a range in which certainly will fall all the best possible solutions to the problem we are considering. In conclusion, I provide a few characteristic numerical examples in order to appreciate the quality of the result arising from the particular approach I have chosen.
Category: Combinatorics and Graph Theory

[36] viXra:1307.0055 [pdf] submitted on 2013-07-11 11:56:55

Combinatorial Process and Pascal's Triangle Or Mount Meru

Authors: John Frederick Sweeney
Comments: 20 Pages.

In Vedic Physics, the combinatorial process by which counts are counted closely resembles the binomial triangle, or Pascal's Triangle, which was known to Ancient India and China as Mount Meru or Zhang's triangle. This is not accidental, but instead reflects the numerical structure of the universe, as the pattern repeats itself in many types of numbers, including Clifford Algebras, Octonions, the Exceptional Lie Algebras, the Magic Triangle, and Barnes - Wall Lattices. Previous papers have discussed details of the counts; this paper focuses on the triangular relationships between numbers, especially those noted by Tony "Frank" Smith.
Category: Combinatorics and Graph Theory

[35] viXra:1307.0052 [pdf] submitted on 2013-07-10 04:56:05

50 Orders of Change in A Combinatorial Universe

Authors: John Frederick Sweeney
Comments: 11 Pages.

Matter may exist in one of three states in the universe. The interactions between these states of matter add up to fifty types of change. Causes of change include: the spectrum of inter-changed states, due to imbalance, failure to synchronize, balance and coherent synchronization, caused by the interplay of three modes of matter, which sum up to 50 (order of powers). This paper describes the three states of matter and how their interactions combine to create fifty types of change.
Category: Combinatorics and Graph Theory

[34] viXra:1307.0041 [pdf] submitted on 2013-07-08 10:59:13

Matter Counts or the Count of Matter

Authors: John Frederick Sweeney
Comments: 9 Pages.

Decoding of Vedic literature reveals three states of matter, and the basic count of matter as modulated by the Golden Section. Thus, all forms of nature follow the contours of the Golden Section in their growth and development. Provided here is a basic explanation of how the counts occur within the three separate states of matter, and a new formation of Time. These concepts form the basis of the Qi Men Dun Jia Model, with its incorporation of the icosahedron and its 60 stellated permutations.
Category: Combinatorics and Graph Theory

[33] viXra:1307.0021 [pdf] submitted on 2013-07-04 10:04:35

Nine Dots Puzzle Extended to NXnX…Xn Points

Authors: Marco Ripà, Pablo Remirez
Comments: The paper is 14 pages long and it is in Italian. Copyright: © 2013 Ripà, Remirez

The classic wit problem, the “Nine Dots Puzzle” is widely used in courses on creativity and appears in a lot of games magazines. One of the earliest appearances is in “Cyclopedia of Puzzles” by Sam Loyd’s in 1914. Here is a review of the generic solution of the problem of the 9 points spread to n2 points. Basing on a specific pattern, we show that any nxn (for n ≥ 5) points puzzle can be also solved Inside the Box, using only 2n−2 straight lines (connected at their end-points), through the square spiral method. The same pattern is also useful to “bound above” the minimal number of straight lines we need to connect nk points in a k-dimensional space, while to “bound below” the solution of the nxnx…xn puzzle we start from a very basic consideration.
Category: Combinatorics and Graph Theory

[32] viXra:1306.0219 [pdf] submitted on 2013-06-26 07:17:26

Irregularity Strength of Digraphs

Authors: Jesse D. Gilbert
Comments: The dedication and acknowledgement have some errors in diction. Also, there is a verb missing in the abstract at the conclusion of the first page.

[Not included.]
Category: Combinatorics and Graph Theory

[31] viXra:1305.0050 [pdf] submitted on 2013-05-08 10:15:41

Integral Eigen-Pair Balanced Classes of Graphs Ratios, Asymptotes, Density and Areas

Authors: Paul August Winter, Carol Lynne Jessop
Comments: Pages.

The association of integers, conjugate pairs and tightness with the eigenvalues of graphs provide the motivation for the following definitions. A class of graphs, with the property, that for each graph (member) of the class, there exists a pair a,b of non-zero, distinct, eigenvalues, whose sum (or product) yields the same integer, either as a fixed constant, or a function of an inherent aspect of the graph (such as its size), is said to be sum-eigen*(a+b)*pair balanced (or product-eigen*(a.b)*pair balanced, respectively). For example, complete graphs on n vertices, are eigen-bi-balanced with sum-eigen*(n-2)*pair balanced and product-eigen*(1-n)*pair balanced, and since a,b are non-zero their reciprocals (which affect the tightness of a graph ) are defined, so that this class has the eigen-balanced ratio of 1/a+1/b=(a+b)/(a.b)= (n-2)/(1-n) =f(n) which is asymptotic to the constant value of -1. The absolute value of the integral of f(n) multiplied by the average degree yields the area (n-1)(n-ln(n-1)) – we show that this is the maximum area for most known classes of eigen-bi-balanced graphs. We investigate the effect of this asymptotic ratio on the energy of the molecular representation of graphs. Cycles are generally neither sum-eigen-pair, nor product-eigen-pair balanced, while paths are only sum- eigen-pair balanced. In this paper, we introduce a class of graphs, involving q cliques each of size q, and show that this class is eigen-bi-balanced with respect to the sum -1 and product 1-q so that it has ratio 1/(q-1) asymptotic to 0, and has area q(2q+2ln(q-1)), and discuss its eigen-bi-balanced criticality.
Category: Combinatorics and Graph Theory

[30] viXra:1305.0038 [pdf] submitted on 2013-05-06 20:09:16

Enumeration of Self-Avoiding Walks in a Lattice

Authors: Tom Harvey
Comments: 12 Pages.

A self-avoiding walk (SAW) is a path on a lattice that does not pass through the same point more than once. We develop a method for enumerating self-avoiding walks in a lattice by decomposing them into smaller pieces called tiles, solving particular cases on the square, triangular and cubic lattices. We also show that enumeration of SAWs in a lattice is related to enumeration of edge-connected shapes, for example polyominoes.
Category: Combinatorics and Graph Theory

[29] viXra:1304.0100 [pdf] submitted on 2013-04-20 13:12:55

Probabilistic Methods on Erdos Problems

Authors: Jesse Gilbert
Comments: 3 Pages. [None.]

This paper has four sections and a bibliography. It serves as both a continuation and an errata for previous versions of the article.
Category: Combinatorics and Graph Theory

[28] viXra:1304.0004 [pdf] submitted on 2013-04-02 01:26:20

Resolving the Decision Version of the Directed Hamiltonian Path (Cycle) Problem Under Two Special Conditions by Method of Matrix Determinant: an Overview

Authors: Okunoye Babatunde O.
Comments: 6 Pages.

In computational complexity, the Decision version of the Directed Hamiltonian Path Problem is known to be NP-complete (Nondeterministic-Polynomial complete). There are no known efficient algorithms for its resolution in Polynomial time. In three papers, the author shows that this problem can be resolved in Polynomial time under two special conditions relating to the determinant of a matrix: the absence of zero rows (columns) and similar rows (columns). In this paper, the author gives a brief overview of the proposed solution and the P vs NP problem.
Category: Combinatorics and Graph Theory

[27] viXra:1304.0002 [pdf] submitted on 2013-04-01 07:25:24

Finding Shortest Hamiltonian Path is in P

Authors: Dhananjay P. Mehendale
Comments: 5 pages

The problem of finding shortest Hamiltonian path in a weighted complete graph belongs to the class of NP-Complete problems [1]. In this paper we will show that we can obtain shortest Hamiltonian path in a given weighted complete graph in polynomial time! We will be discussing a very simple but useful idea of applying certain chosen sequence of permutations (actually transpositions) on given weighted adjacency matrix corresponding to the complete graph, on p points say, under consideration. This simple and novel algorithm essentially consists of applying certain transpositions that will transform the weighted adjacency matrix in such a way that its vertices are now relabeled and in this relabeled weighted complete graph the algorithm terminates decisively in producing the shortest Hamiltonian path, and this shortest Hamiltonian path will be 1->2->3->....->(p-1)->p
Category: Combinatorics and Graph Theory

[26] viXra:1303.0172 [pdf] submitted on 2013-03-22 20:54:42

On Retracts, Absolute Retracts, and Folds in Cographs

Authors: Ton Kloks, Yue-Li Wang
Comments: 14 Pages.

Let G and H be two cographs. We show that the problem to determine whether H is a retract of G is NP-complete. We show that this problem is fixed-parameter tractable when parameterized by the size of H. When restricted to the class of threshold graphs or to the class of trivially perfect graphs, the problem becomes tractable in polynomial time. The problem is also solvable in linear time when one cograph is given as an induced subgraph of the other. We characterize absolute retracts for the class of cographs. Foldings generalize retractions. We show that the problem to fold a trivially perfect graph onto a largest possible clique is NP-complete. For a threshold graph this folding number equals its chromatic number and achromatic number.
Category: Combinatorics and Graph Theory

[25] viXra:1211.0081 [pdf] submitted on 2012-11-14 10:59:09

Characterization of Partitions for Solid Graphs

Authors: Natasha Lee, Joan Portmann
Comments: 5 Pages.

The paper deals with the problems of characterization of simple graphical partitions belonging to the solid graphs, i.e. graphs, in which there are no four of vertices such that it is possible some shift of edges incidental to them and with characterization of the one class of steady graphs too. The necessary and sufficient conditions for the partition belonging to the solid graph have been established.
Category: Combinatorics and Graph Theory

[24] viXra:1211.0074 [pdf] submitted on 2012-11-13 09:11:35

Non-Solvable Ordinary Differential Equations With Applications

Authors: Linfan Mao
Comments: 46 Pages.

Different from the system in classical mathematics, a Smarandache system is a contradictory system in which an axiom behaves in at least two different ways within the same system, i.e., validated and invalided, or only invalided but in multiple distinct ways. Such systems exist extensively in the world, particularly, in our daily life. In this paper, we discuss such a kind of Smarandache system, i.e., non-solvable ordinary differential equation systems by a combinatorial approach, classify these systems and characterize their behaviors, particularly, the sum-stability and prod-stability of such linear and non-linear differential equations. Some applications of such systems to other sciences, such as those of globally controlling of infectious diseases, establishing dynamical equations of instable structure, particularly, the n-body problem and understanding global stability of matters with multilateral properties can be also found.
Category: Combinatorics and Graph Theory

[23] viXra:1210.0161 [pdf] submitted on 2012-10-27 09:09:57

Binomial Construction of the Trinomial Triangle

Authors: Martin Erik Horn
Comments: 17 Pages.

The trinomial triangle can be constructed in a binomial way using unit vectors of geometric algebra of quarks. This sheds some light on the question, how it is possible to transform mathematically entities of two elements into entities of three elements or vice versa.
Category: Combinatorics and Graph Theory

[22] viXra:1210.0081 [pdf] submitted on 2012-10-16 23:30:24

Probe Graph Classes

Authors: D. B. Chandler, M.-S. Chang, T. Kloks, J. Liu, S.-L. Peng
Comments: 121 Pages.

Let GG be a class of graphs. A graph G is a probe graph of GG if its vertex set can be partitioned into a set P of `probes' and an independent set N of `nonprobes' such that G can be embedded into a graph of GG by adding edges between certain nonprobes. In this book we investigate probe graphs of various classes of graphs.
Category: Combinatorics and Graph Theory

[21] viXra:1210.0049 [pdf] submitted on 2012-10-10 05:51:51

In an Adjacency Matrix Which Encodes for a Directed Hamiltonian Path, a Non-Zero Determinant Value Certifies the Existence of a Directed Hamiltonian Path When no Zero Rows (Columns) and no Similar Rows (Columns) Exist in the Adjacency Matrix

Authors: Okunoye Babatunde O.
Comments: 6 Pages.

The decision version of Directed Hamiltonian path problem is an NP-complete problem which asks, given a directed graph G, does G contain a directed Hamiltonian path? In two separate papers, the author expresses the graph problem as an adjacency matrix and a proof given to show that under two special conditions relating to theorems on the determinant of a square matrix, a non-zero determinant value certifies the existence of a directed Hamiltonian path. Here, a brief note is added to repair a flaw in the proof. The result, as expressed in the paper title is a more defensible proposition
Category: Combinatorics and Graph Theory

[20] viXra:1209.0051 [pdf] submitted on 2012-09-17 05:15:21

Triangle-Partitioning Edges of Planar Graphs, Toroidal Graphs and K-Planar Graphs

Authors: Jiawei Gao, Ton Kloks, Sheung-Hung Poon
Comments: 15 Pages.

We show that there is a linear-time algorithm to partition the edges of a planar graph into triangles. We show that the problem is also polynomial for toroidal graphs but NP-complete for k-planar graphs, where k is at least 8.
Category: Combinatorics and Graph Theory

[19] viXra:1209.0021 [pdf] submitted on 2012-09-06 18:40:36

Matrix Determinant as a Verifier of a Path (Cycle) in the Directed Hamiltonian Cycle Problem Under Two Special Conditions: a Formal Proof

Authors: Okunoye Babatunde O.
Comments: 4 Pages. submitted to IEEE African Journal of Computing and ICTs

In earlier work, the author conjectured that under two special conditions relating to theorems on the determinant of a matrix: the absence of a zero row (column) and the absence of similar rows (columns), a non-zero determinant value certifies the existence of a Directed Hamiltonian Path in an arbitrary adjacency matrix. Here, a formal proof is provided by means of deductive logic to establish that in an arbitrary adjacency matrix of size n (n rows and n columns), a non-zero determinant value verifies the existence of a Directed Hamiltonian Path in the adjacency matrix.
Category: Combinatorics and Graph Theory

[18] viXra:1208.0223 [pdf] submitted on 2012-08-26 22:40:04

De Bruijn's Combinatorics

Authors: J.W.Nienhuys (Ling-Ju Hung, Ton Kloks eds.)
Comments: 192 Pages.

This is a translation of the handwritten classroom notes taken by Nienhuys of a course in combinatorics given by N.G. de Bruijn at Eindhoven University of Technology, during the 1970s and 1980s.
Category: Combinatorics and Graph Theory

[17] viXra:1208.0217 [pdf] submitted on 2012-08-24 21:20:18

De Combinatoriek Van De Bruijn

Authors: Ton Kloks
Comments: 18 Pages. In Dutch

In memoriam N.G. de Bruijn. In this paper I show some highlights of his work in combinatorics. This article does NOT contain an overview of his work in Penrose tilings, asymptotics and AUTOMATH. Other surveys on these topics are being written by others.
Category: Combinatorics and Graph Theory

[16] viXra:1204.0019 [pdf] submitted on 2012-04-05 03:07:16

On Pseudo trees and Graph Isomorphism

Authors: Dhananjay P. Mehendale
Comments: 7 pages.

In this paper we obtain a new polynomial time algorithm for testing isomorphism of graphs. This algorithm is based on the idea of associating a rooted, unordered, pseudo tree with given graphs and thus reducing the isomorphism problem for graphs to isomorphism problems for associated rooted, unordered, pseudo trees. We show that isomorphism of the rooted, unordered, pseudo trees associated with graphs and so in effect isomorphism of given two graphs can be tested in polynomial (quadratic) time.
Category: Combinatorics and Graph Theory

[15] viXra:1202.0078 [pdf] submitted on 2012-02-27 01:17:08

On Building 4-Critical Plane and Projective Plane Multiwheels from Odd Wheels

Authors: Dainis Zeps
Comments: 12 Pages. http://arxiv.org/abs/1202.4862

We build unbounded classes of plane and projective plane multiwheels that are 4-critical that are received summing odd wheels as edge sums modulo two. These classes can be considered as ascending from single common graph that can be received as edge sum modulo two of the octahedron graph O and the minimal wheel W3. All graphs of these classes belong to 2n - 2-edges-class of graphs, among which are those that quadrangulate projective plane, i.e., graphs from Groetzsch class, received applying Mycielski's Construction to odd cycle.
Category: Combinatorics and Graph Theory

[14] viXra:1202.0077 [pdf] submitted on 2012-02-27 01:23:06

On Building 4-critical Plane and Projective Plane Multiwheels from Odd Wheels. Extended Abstract

Authors: Dainis Zeps
Comments: 4 Pages. Full version of paper http://arxiv.org/abs/1202.4862

We build unbounded classes of plane and projective plane multiwheels that are 4-critical that are received summing odd wheels as edge sums modulo two. These classes can be considered as ascending from single common graph that can be received as edge sum modulo two of the octahedron graph O and the minimal wheel W_3.
Category: Combinatorics and Graph Theory

[13] viXra:1106.0053 [pdf] submitted on 27 Jun 2011

An Interstellar Position Fixing Method

Authors: Paul A. Titze
Comments: 18 pages, 19 figures.

fix a ship's position in charted interstellar space with the assistance of a three dimensional computer based stellar chart and star camera spectrometers capable of measuring angular separations between three sets of pair stars. The method offers another tool for the navigator to rely on if alternative position fixing methods are not available or if the navigator wishes to verify the validity of one's position given by other means.
Category: Combinatorics and Graph Theory

[12] viXra:1103.0032 [pdf] submitted on 11 Mar 2011

Sequences on Graphs with Symmetries

Authors: Linfan Mao
Comments: 16 pages

An interesting symmetry on multiplication of numbers found by Prof.Smarandache recently. By considering integers or elements in groups on graphs, we extend this symmetry on graphs and find geometrical symmetries. For extending further, Smarandache's or combinatorial systems are also discussed on general mathematical systems in this paper, particularly, the CC conjecture presented by myself six years ago, which enables one to construct symmetrical systems in mathematical sciences.
Category: Combinatorics and Graph Theory

[11] viXra:1101.0095 [pdf] submitted on 28 Jan 2011

Sharp Concentration of the Rainbow Connection of Random Graphs

Authors: Yilun Shang
Comments: 5 pages

An edge-colored graph G is rainbow edge-connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. Similarly, a vertex-colored graph G is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. We prove that both rc(G) and rvc(G) have sharp concentration in classical random graph model G(n, p).
Category: Combinatorics and Graph Theory

[10] viXra:1010.0025 [pdf] submitted on 13 Oct 2010

Combinatorial Maps with Normalized Knot

Authors: Dainis Zeps
Comments: 14 pages

We consider combinatorial maps with fixed combinatorial knot numbered with augmenting numeration called normalized knot. We show that knot's normalization doesn't affect combinatorial map what concerns its generality. Knot's normalization leads to more concise numeration of corners in maps, e.g., odd or even corners allow easy to follow distinguished cycles in map caused by the fixation of the knot. Knot's normalization may be applied to edge structuring knot too. If both are normalized then one is fully and other partially normalized mutually.
Category: Combinatorics and Graph Theory

[9] viXra:1009.0014 [pdf] submitted on 13 Mar 2010

A Group-Permutation Algorithm to Solve the Generalized SUDOKU

Authors: Florentin Smarandache
Comments: 3 pages.

Sudoku is a game with numbers, formed by a square with the side of 9, and on each row and column are placed the digits 1, 2, 3, 4, 5, 6, 7, 8, 9, written only one time; the square is subdivided in 9 smaller squares with the side of 3x3, which, also, must satisfy the same condition, i.e. each square to contain all digits from 1 to 9 written only once.
Category: Combinatorics and Graph Theory

[8] viXra:1006.0062 [pdf] submitted on 25 Jun 2010

Super Special Codes Using Super Matrices

Authors: W. B. Vasantha Kandasamy, Florentin Smarandache, K. Ilanthenral
Comments: 163 pages

The new classes of super special codes are constructed in this book using the specially constructed super special vector spaces. These codes mainly use the super matrices. These codes can be realized as a special type of concatenated codes.
Category: Combinatorics and Graph Theory

[7] viXra:1004.0018 [pdf] submitted on 8 Mar 2010

Vectored Route-Length Minimization - a Heuristic and an Open Conjecture

Authors: Florentin Smarandache, Sukanto Bhattacharya
Comments: 7 pages

We have posed a simple but interesting graph theoretic problem and posited a heuristic solution procedure, which we have christened as Vectored Route-length Minimization Search (VeRMinS). Basically, it constitutes of a re-casting of the classical "shortest route" problem within a strictly Euclidean space. We have only presented a heuristic solution process with the hope that a formal proof will eventually emerge as the problem receives wider exposure within mathematical circles.
Category: Combinatorics and Graph Theory

[6] viXra:1003.0229 [pdf] submitted on 7 Mar 2010

Smarandache Multi-Space Theory

Authors: Linfan Mao
Comments: 275 pages

A Smarandache multi-space is a union of n different spaces equipped with some different structures for an integer n ≥ 2, which can be used both for discrete or connected spaces, particularly for geometries and spacetimes in theoretical physics.
Category: Combinatorics and Graph Theory

[5] viXra:1003.0223 [pdf] submitted on 7 Mar 2010

Smarandache Geometries & Map Theory with Applications(i)

Authors: Linfan Mao
Comments: 215 pages

SMARANDACHE GEOMETRIES & MAP THEORY WITH APPLICATIONS
Category: Combinatorics and Graph Theory

[4] viXra:1001.0031 [pdf] submitted on 22 Jan 2010

Threeconnected Graphs with Only One Hamiltonian Circuit

Authors: Dainis Zeps, Emanuels Grinbergs
Comments: 6 pages

We will call graph 1-H-graph if it is threeconnected and it has only one Hamiltonian circuit
Category: Combinatorics and Graph Theory

[3] viXra:1001.0030 [pdf] submitted on 22 Jan 2010

Combinatorial Maps

Authors: Dainis Zeps
Comments: 61 pages

Tutorial
Category: Combinatorics and Graph Theory

[2] viXra:1001.0029 [pdf] submitted on 22 Jan 2010

4-Critical Wheel Graphs of Higher Order

Authors: Dainis Zeps
Comments: 4 pages

4-critical wheel graphs of higher order are considered concerning their belonging to free-planar or free-Hadwiger classes.
Category: Combinatorics and Graph Theory

[1] viXra:0908.0051 [pdf] submitted on 10 Aug 2009

Solution to Four-Color Problem

Authors: Hamid V. Ansari
Comments: 15 pages

To color a given map we first find its related map with the most mutual adjacencies and color it by only four colors, then we trace back.
Category: Combinatorics and Graph Theory

Replacements of recent Submissions

[16] viXra:1403.0067 [pdf] replaced on 2014-04-07 10:58:21

An idea on Frankl's Conjecture

Authors: Giuseppe Rauti
Comments: 2 Pages.

An idea on Frankl's Conjecture.
Category: Combinatorics and Graph Theory

[15] viXra:1310.0229 [pdf] replaced on 2013-11-12 01:52:44

Graceful Labeling for Trees

Authors: Dhananjay P. Mehendale
Comments: 15 Pages. Rivised

We define so called n-delta lattice containing (n-1) lattice points in first (topmost) row, (n-2) lattice points in second row, and so on. Each time the count of lattice points decreases by unity as we move down by one row till we reach the last (bottommost) row containing single lattice point. We label these lattice points in two different ways and obtain two different labeled lattices. In the first kind of labeling we associate vertex pairs in a particular way as labels for points of the lattice and so call it edge-labeled n-delta lattice. In the second kind of labeling we associate integers as labels with lattice points in each row to indicate the position of that lattice point in the row and so call it position-labeled n-delta lattice. This defining of position-labeled n-delta lattice enables us to associate a lexicographic ordering with lattice paths. We define distinct as well as different lattice paths and further see that for proving graceful tree conjecture one needs to show that the count of distinct lattice paths corresponding to trees in the edge-labeled n-delta lattice is same as the count of nonisomorphic trees with n vertices. We verify this for some (small) values of n. We further see that existence of graceful labeling for an unlabeled tree with n vertices follows from the existence of a lattice path representing this same tree in the edge-labeled n-delta lattice. It is possible to generate all (n, n-1)-trees from all (n-1, n-2)-trees by attaching an edge that emerges from each of the inequivalent vertices of (n-1, n-2)-trees and entering in the new vertex taken outside. We show that extending all lattice paths by adding a lattice point in the paths sitting in the sub-lattice of n-delta lattice in all possible ways is same as the above mentioned generation of trees from lower trees.
Category: Combinatorics and Graph Theory

[14] viXra:1307.0095 [pdf] replaced on 2014-01-11 12:49:08

The Rectangular Spiral Solution for the n_1 X n_2 X … X n_k Points Problem

Authors: Marco Ripà
Comments: 13 Pages.

A generalization of Ripà’s square spiral solution for the nXnX…X n points upper bound problem. Additionally, we provide a non-trivial lower bound for the k-dimensional n_1Xn_2X…Xn_k points problem. In this way, we can build a range in which, with certainty, all the best possible solutions to the problem we are considering will fall. Finally, we provide a few characteristic numerical examples in order to appreciate the fineness of the result arising from the particular approach we have chosen.
Category: Combinatorics and Graph Theory

[13] viXra:1307.0095 [pdf] replaced on 2013-09-06 17:31:43

The Rectangular Spiral Solution for the n_1 X n_2 X … X n_k Points Problem

Authors: Marco Ripà
Comments: 13 Pages.

A generalization of Ripà’s square spiral solution for the nXnX…X n points upper bound problem. Additionally, we provide a non-trivial lower bound for the k-dimensional n_1Xn_2X…Xn_k points problem. In this way, we can build a range in which, with certainty, all the best possible solutions to the problem we are considering will fall. Finally, we provide a few characteristic numerical examples in order to appreciate the fineness of the result arising from the particular approach we have chosen.
Category: Combinatorics and Graph Theory

[12] viXra:1307.0021 [pdf] replaced on 2013-09-05 19:08:16

The Nine Dots Puzzle Extended to Nxnx…xn Points

Authors: Marco Ripà, Pablo Remirez
Comments: 11 Pages. This is the second version of the paper in Italian that I already submitted a few months ago. It has been entirely written in English.

The classic thinking problem, the “Nine Dots Puzzle”, is widely used in courses on creativity and appears in a lot of games magazines. One of the earliest appearances is in “Cyclopedia of Puzzles” by Sam Loyd in 1914. Here is a review of the generic solution of the problem of the 9 points spread to n^2 points. Basing it on a specific pattern, we show that any nxn (for n ≥ 5) points puzzle can also be solved ‘Inside the Box’, using only 2∙n − 2 straight lines (connected at their end-points), through the square spiral method. The same pattern is also useful to “bound above” the minimal number of straight lines we need to connect n^k points in a k-dimensional space, while to “bound below” the solution of the nxnx…xn puzzle we start from a very basic consideration.
Category: Combinatorics and Graph Theory

[11] viXra:1307.0021 [pdf] replaced on 2013-07-30 15:01:36

Nine Dots Puzzle Extended to NXnX…Xn Points

Authors: Marco Ripà, Pablo Remirez
Comments: 15 Pages.

The classic wit problem, the “Nine Dots Puzzle” is widely used in courses on creativity and appears in a lot of games magazines. One of the earliest appearances is in “Cyclopedia of Puzzles” by Sam Loyd’s in 1914. Here is a review of the generic solution of the problem of the 9 points spread to n2 points. Basing on a specific pattern, we show that any nxn (for n ≥ 5) points puzzle can be also solved Inside the Box, using only 2n−2 straight lines (connected at their end-points), through the square spiral method. The same pattern is also useful to “bound above” the minimal number of straight lines we need to connect nk points in a k-dimensional space, while to “bound below” the solution of the nxnx…xn puzzle we start from a very basic consideration.
Category: Combinatorics and Graph Theory

[10] viXra:1307.0021 [pdf] replaced on 2013-07-08 18:48:41

Nine Dots Puzzle Extended to NXnX…Xn Points

Authors: Marco Ripà, Pablo Remirez
Comments: The paper is 15 pages long and it is in Italian. Copyright: © 2013 Ripà, Remirez

The classic wit problem, the “Nine Dots Puzzle” is widely used in courses on creativity and appears in a lot of games magazines. One of the earliest appearances is in “Cyclopedia of Puzzles” by Sam Loyd’s in 1914. Here is a review of the generic solution of the problem of the 9 points spread to n2 points. Basing on a specific pattern, we show that any nxn (for n ≥ 5) points puzzle can be also solved Inside the Box, using only 2n−2 straight lines (connected at their end-points), through the square spiral method. The same pattern is also useful to “bound above” the minimal number of straight lines we need to connect nk points in a k-dimensional space, while to “bound below” the solution of the nxnx…xn puzzle we start from a very basic consideration.
Category: Combinatorics and Graph Theory

[9] viXra:1304.0002 [pdf] replaced on 2013-04-11 15:24:12

Polynomial Algorithms for Shortest Hamiltonian Path and Circuit

Authors: Dhananjay P. Mehendale
Comments: 14 Pages

The problem of finding shortest Hamiltonian path and shortest Hamiltonian circuit in a weighted complete graph belongs to the class of NP-Complete problems [1]. This well known problem asks for a method or algorithm to locate such path or circuit that passes through every vertex only once in the given weighted complete graph. In this paper we begin with proposing two approximation algorithms for shortest Hamiltonian graphs which essentially consists of applying certain chosen permutations (transpositions or product of transpositions) on the adjacency matrix of given weighted complete graph causing reshuffling of the labels of its vertices. We change the labels of vertices through proper choice of permutations in such a way that in this relabeled graph the Hamiltonian path 123….k(k+1)…p becomes approximation to shortest path in the given weighted complete graph under consideration. We then define so called ordered weighted adjacency list for given weighted complete graph and proceed to the main result of the paper, namely, the exact algorithm based on utilization of ordered weighted adjacency list and the simple properties that any path or circuit must satisfy. This algorithm performs checking of sub-lists, containing (n-1) entries (edge pairs) for paths and n entries (edge pairs) for circuits, chosen from ordered adjacency list in a well defined sequence to determine exactly the shortest Hamiltonian path and shortest Hamiltonian circuit. The procedure has intrinsic advantage of landing on the desired solution in quickest possible time and even in worst case in polynomial time.
Category: Combinatorics and Graph Theory

[8] viXra:1209.0021 [pdf] replaced on 2012-09-11 22:39:16

Matrix Determinant as a Verifier of a Path (Cycle) in the Directed Hamiltonian Cycle Problem Under Two Special Conditions: a Formal Proof

Authors: Okunoye Babatunde
Comments: 4 Pages. Accepted and Revised at IEEE African Journal of Computing and ICTs

In earlier work, the author conjectured that under two special conditions relating to theorems on the determinant of a matrix: the absence of a zero row (column) and the absence of similar rows (columns), a non-zero determinant value certifies the existence of a Directed Hamiltonian Path in an arbitrary adjacency matrix. Here, a formal proof is provided by means of deductive logic to establish that in an arbitrary adjacency matrix of size n (n rows and n columns), a non-zero determinant value verifies the existence of a Directed Hamiltonian Path in the adjacency matrix
Category: Combinatorics and Graph Theory

[7] viXra:1208.0217 [pdf] replaced on 2013-01-06 01:50:48

De Combinatoriek Van De Bruijn

Authors: Ton Kloks
Comments: 18 Pages. in Dutch

In memoriam N.G. de Bruijn. In this article I present some highlights of De Bruijn's contributions in combinatorics. This article does not survey his work on eg Penrose tilings, asymptotics or AUTOMATH; other surveys on these topics are being written by others.
Category: Combinatorics and Graph Theory

[6] viXra:1208.0217 [pdf] replaced on 2013-01-06 00:55:45

De Combinatoriek Van De Bruijn

Authors: Ton Kloks
Comments: 18 Pages. in Dutch

In memoriam N.G. de Bruijn. In this article I present some highlights of De Bruijn's contributions in combinatorics. This article does not survey his work on eg Penrose tilings, asymptotics or AUTOMATH; other surveys on these topics are being written by others.
Category: Combinatorics and Graph Theory

[5] viXra:1208.0217 [pdf] replaced on 2012-12-31 20:30:05

De Combinatoriek Van De Bruijn

Authors: Ton Kloks
Comments: 18 Pages. in Dutch

In memoriam N.G. de Bruijn. In this article I present an short survey of the work of N.G. de Bruijn in combinatorics. This text does not survey his work on asymptotics, Penrose tilings, or AUTOMATH. Surveys covering these topics will appear elsewhere.
Category: Combinatorics and Graph Theory

[4] viXra:1208.0217 [pdf] replaced on 2012-09-30 02:20:29

De Combinatoriek Van De Bruijn

Authors: T. Kloks
Comments: 18 Pages. in Dutch

In memoriam N.G. de Bruijn. In this article I present a short survey of the work of N.G. de Bruijn in combinatorics. This text does not survey his work in asymptotics, Penrose tilings, or AUTOMATH. Surveys covering these topics will appear elsewhere.
Category: Combinatorics and Graph Theory

[3] viXra:1208.0217 [pdf] replaced on 2012-09-07 22:43:37

De Combinatoriek van De Bruijn

Authors: T. Kloks
Comments: 18 Pages. In Dutch

In memoriam: N.G. de Bruijn. In this short survey I present an overview of De Bruijn's work in combinatorics. This text does not survey his work in asymptotics, Penrose tilings, or AUTOMATH. Surveys covering these topics will appear elsewhere.
Category: Combinatorics and Graph Theory

[2] viXra:1003.0227 [pdf] replaced on 26 Jun 2011

Automorphismgroups of Maps, Surfaces and Smarandache Geometries

Authors: Linfan Mao
Comments: 399 pages.

Automorphism groups survey similarities on mathematical systems, which appear nearly in all mathematical branches, such as those of algebra, combinatorics, geometry, ... and theoretical physics, theoretical chemistry, etc. In geometry, configurations with high symmetry born symmetrical patterns, a kind of beautiful pictures in aesthetics. Naturally, automorphism groups enable one to distinguish systems by similarity. More automorphisms imply more symmetries of that system. This fact has established the fundamental role of automorphism groups in modern sciences. So it is important for graduate students knowing automorphism groups with applications.
Category: Combinatorics and Graph Theory

[1] viXra:1003.0221 [pdf] replaced on 27 Jun 2011

Combinatorial Geometry with Applications to Field Theory

Authors: Linfan Mao
Comments: 502 pages.

Accompanied with humanity into the 21st century, a highlight trend for developing a science is its overlap and hybrid, and harmoniously with other sciences, which enables one to handle complex systems in the WORLD. This is also for developing mathematics. As a powerful tool for dealing with relations among objectives, combinatorics, including combinatorial theory and graph theory mushroomed in last century. Its related with algebra, probability theory and geometry has made it to an important subject in mathematics and interesting results emerged in large number without metrics. Today, the time is come for applying combinatorial technique to other mathematics and other sciences besides just to find combinatorial behavior for objectives. That is the motivation of this book, i.e., to survey mathematics and fields by combinatorial principle.
Category: Combinatorics and Graph Theory