# 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