[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.

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.