Combinatorics and Graph Theory

1209 Submissions

[2] 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

[1] 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