Computer Science – Discrete Mathematics
Scientific paper
2010-05-13
Computer Science
Discrete Mathematics
The present article introduces a new algebraic technique which generalizes the notion of counting modulo 2 via applying fields
Scientific paper
In Graph Theory a number of results were devoted to studying the computational complexity of the number modulo 2 of a graph's edge set decompositions of various kinds, first of all including its Hamiltonian decompositions, as well as the number modulo 2 of, say, Hamiltonian cycles/paths etc. While the problems of finding a Hamiltonian decomposition and Hamiltonian cycle are NP-complete, counting these objects modulo 2 in polynomial time is yet possible for certain types of regular undirected graphs. Some of the most known examples are the theorems about the existence of an even number of Hamiltonian decompositions in a 4-regular graph and an even number of such decompositions where two given edges e and g belong to different cycles (Thomason, 1978), as well as an even number of Hamiltonian cycles passing through any given edge in a regular odd-degreed graph (Smith's theorem). The present article introduces a new algebraic technique which generalizes the notion of counting modulo 2 via applying fields of Characteristic 2 and determinants and, for instance, allows to receive a polynomial-time formula for the number modulo 2 of a 4-regular bipartite graph's Hamiltonian decompositions such that a given edge and a given path of length 2 belong to different Hamiltonian cycles - hence refining/extending (in a computational sense) Thomason's result for bipartite graphs. This technique also provides a polynomial-time calculation of the number modulo 2 of a graph's edge set decompositions into simple cycles each containing at least one element of a given set of its edges what is a similar kind of extension of Thomason's theorem as well.
No associations
LandOfFree
A new algebraic technique for polynomial-time computing the number modulo 2 of Hamiltonian decompositions and similar partitions of a graph's edge set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A new algebraic technique for polynomial-time computing the number modulo 2 of Hamiltonian decompositions and similar partitions of a graph's edge set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new algebraic technique for polynomial-time computing the number modulo 2 of Hamiltonian decompositions and similar partitions of a graph's edge set will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-640443