We present a new necessary and sufficient condition to determine the entanglement status of an arbitrary N-qubit quantum state (maybe pure or mixed) represented by a density matrix. A necessary condition satisfied by separable bipartite quantum state
s was obtained by A. Peres, [1]. A. Peres showed that if a bipartite state represented by the density matrix is separable then its partial transpose is positive semidefinite and has no negative eigenvalues. In other words, if the partial transpose is not positive semidefinite and so one or more of its eigenvalues are negative then the state represented by the corresponding density matrix is entangled. It was then shown by M. Horodecki et.al, [2], that this necessary condition is also sufficient for two-by-two and two-by-three dimensional systems. However, in other dimensions, it was shown by P. Horodecki, [3], that the criterion due to A. Peres is not sufficient. In this paper, we develop a new approach and a new criterion for deciding the entanglement status of the states represented by the density matrices corresponding to N-qubit systems. We begin with a 2-qubit case and then show that these results for 2-qubit systems can be extended to N-qubit systems by proceeding along similar lines. We discuss few examples to illustrate the method proposed in this paper for testing the entanglement status of few density matrices.
A new characterisation of Hamiltonian graphs using f-cutset matrix is proposed. A new exact polynomial time algorithm for the travelling salesman problem (TSP) based on this new characterisation is developed. 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 utilisation of ordered weighted adjacency list and the simple properties that any path or circuit must satisfy. This algorithm performs checking of sub-lists, containing (p-1) entries (edge pairs) for paths and p 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 in a weighted complete graph of p vertices. The procedure has intrinsic advantage of landing on the desired solution in quickest possible time and even in worst case in polynomial time. A new characterisation of shortest Hamiltonian tour for a weighted complete graph satisfying triangle inequality (i.e. for tours passing through every city on a realistic map of cities where cities can be taken as points on a Euclidean plane) is also proposed. Finally, we propose a classical algorithm for unstructured search and also three new quantum algorithms for unstructured search which exponentially speed up the searching ability in the unstructured database and discuss its effect on the NP-Complete problems.
We settle the Path Decomposition Conjecture (P.D.C.) due to Tibor Gallai for minimally connected graphs, i.e. trees. We use this validity for trees and settle the P. D. C. using induction on the number of edges for all connected graphs. We then obtai
n a new bound for the number of paths in a path cover in terms of the number of edges using idea of associating a tree with a connected graph. We then make use of a spanning tree in the given connected graph and its associated basic path cover to settle the conjecture of Tibor Gallai in an alternative way. Finally, we show the existence of Hamiltonian path cover satisfying Gallai bound for complete graphs of even order and discuss some of its possible ramifications.
We propose a new algorithm to obtain max flow for the multicommodity flow. This algorithm utilizes the max-flow min-cut theorem and the well known labeling algorithm due to Ford and Fulkerson [1]. We proceed as follows: We select one source/sink pair
among the n distinguished source/sink pairs at a time and treat the given multicommodity network as a single commodity network for such chosen source/sink pair. Then applying standard labeling algorithm, separately for each sink/source pair, the feasible flow which is max flow and the corresponding minimum cut corresponding to each source/sink pair is obtained. A record is made of these cuts and the paths flowing through the edges of these cuts. This record is then utilized to develop our algorithm to obtain max flow for multicommodity flow. In this paper we have pinpointed the difficulty behind not getting a max flow min cut type theorem for multicommodity flow and found out a remedy.
P. J. Kelly conjectured in 1968 that every diregular tournament on (2n+1) points can be decomposed in directed Hamilton circuits [1]. We define so called leading diregular tournament on (2n+1) points and show that it can be decomposed in directed Ham
ilton circuits when (2n+1) is a prime number. When (2n+1) is not a prime number this method does not work and we will need to devise some another method. We also propose a general method to find Hamilton decomposition of certain tournament for all sizes.
We show that we cannot avoid the existence of at least one directed circuit of length less than or equal to (n/r) in a digraph on n vertices with out-degree greater than or equal to r. This is well-known Caccetta-Haggkvist problem.
Simple cubic lattice (SC lattice) can be viewed as plane triangular lattice (PT lattice) by viewing it along its principle diagonal lines. By viewing thus we establish the exact one-to-one correspondence between the closed graphs on SC lattice and th
e corresponding closed graphs on PT lattice. We thus see that the propagator for PT lattice (with suitable modifications) can be used to solve, at least in principle, the 3D Ising problem for SC lattice in the absence of external magnetic field. A new method is then proposed to generate high temperature expansion for the partition function. This method is applicable to 2D as well as 3D lattices. This method does not require explicit counting of closed graphs and this counting is achieved in an indirect way and thus exact series expansion can be achieved up to any sufficiently large order.
We propose an algorithm to reduce a k-chromatic graph to a complete graph of largest possible order through a well defined sequence of contractions. We introduce a new matrix called transparency matrix and state its properties. We then define correct
contraction procedure to be executed to get largest possible complete graph from given connected graph. We finally give a characterization for k-chromatic graphs and use it to settle Hadwigers conjecture.
The theory of colorful graphs can be developed by working in Galois field modulo (p), p > 2 and a prime number. The paper proposes a program of possible conversion of graph theory into a pleasant colorful appearance. We propose to paint the usual bla
ck (indicating presence of an edge) and white (indicating absence of an edge) edges of graphs using multitude of colors and study their properties. All colorful graphs considered here are simple, i.e. not having any multiple edges or self-loops. This paper is an invitation to the program of generalizing usual graph theory in this direction.
