()

 Abstract [Randomized graph states] We introduce a class of mixed multi-qubit states, that corresponds to a randomized version of graph states . It is shown that unitary equivalences are lost by randomization using a rank argument. We study the entanglement features of these states by investigating both bipartite and genuine multipartite entanglement. Bipartite entanglement is shown to be present as a randomized edge exists across the bipartition. The presence of multipartite entanglement is characterized by witness operators which are subsequently adapted to study non-local properties through the violation of suitable Bell inequalities. At the end we present results on the entanglement detection of particular randomized graph states. [X-chain] Besides, the trace of the witness operators, which are employed in the detection of genuine multipartite entanglement of randomized graph states, is calculated by a class of special graph state stabilizers. These stabilizers contain solely $\sigma_x$ Pauli-operators. The underlying vertex sets of such stabilizers are called X-chains. We find that X-chains exhibit a group structure. A general search algorithm for X-chains is then proposed based on the properties of X-chain groups. X-chains are useful mathematical tools for the calculation of graph state scalar products, the orthogonality and balance of graph states, and the construction of multipartite Bell inequalities.