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(4) - 1211(2)
2013 - 1303(1) - 1304(3) - 1305(2)
Any replacements are listed further down
[32] viXra:1305.0050 [pdf] submitted on 2013-05-08 10:15:41
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
[31] viXra:1305.0038 [pdf] submitted on 2013-05-06 20:09:16
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
[30] viXra:1304.0100 [pdf] submitted on 2013-04-20 13:12:55
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
[29] viXra:1304.0004 [pdf] submitted on 2013-04-02 01:26:20
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
[28] viXra:1304.0002 [pdf] submitted on 2013-04-01 07:25:24
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
[27] viXra:1303.0172 [pdf] submitted on 2013-03-22 20:54:42
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
[26] viXra:1211.0081 [pdf] submitted on 2012-11-14 10:59:09
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
[25] viXra:1211.0074 [pdf] submitted on 2012-11-13 09:11:35
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
[24] viXra:1210.0161 [pdf] submitted on 2012-10-27 09:09:57
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
[23] viXra:1210.0127 [pdf] submitted on 2012-10-22 16:31:15
Authors: Patrick A Devlin
Comments: 5 Pages.
In number theory, and especially the study of the diophantine approximation, the Lonely Runner Conjecture is a conjecture with important and widespread applications in mathematics.
This paper attempts to prove the conjecture for any n runners in the special case of speeds with specially correlated prime factors.
Category: Combinatorics and Graph Theory
[22] viXra:1210.0081 [pdf] submitted on 2012-10-16 23:30:24
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Authors: Dainis Zeps
Comments: 61 pages
Tutorial
Category: Combinatorics and Graph Theory
[2] viXra:1001.0029 [pdf] submitted on 22 Jan 2010
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
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
[10] viXra:1304.0002 [pdf] replaced on 2013-04-11 15:24:12
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 123….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
[9] viXra:1210.0127 [pdf] replaced on 2012-10-25 09:52:07
Authors: Patrick A Devlin
Comments: 5 Pages.
In number theory, and especially the study of the diophantine approximation, the Lonely Runner Conjecture is a conjecture with important and widespread applications in mathematics.
This paper attempts to prove the conjecture for any n runners in the special case of integers with particularly correlated prime factors.
Category: Combinatorics and Graph Theory
[8] viXra:1209.0021 [pdf] replaced on 2012-09-11 22:39:16
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
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
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
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
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
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
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
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