{"id":"arxiv/2605.04855","url":"https://arxiv.org/abs/2605.04855","tags":["quant-ph","cs.DM","math.CO"],"score":0,"title":"W-state graphs: Structure and Algorithms","domain":"quant-ph","source":"arxiv","authors":["Rishikesh Gajjala","Saurabh Ray","Dimitrios M. Thilikos"],"reviews":0,"subject":"quant-ph","summary":"We study the class of edge-coloured graphs arising from the graph-theoretic representation of quantum photonic experiments that generate multipartite W-states. Abstracting away physical amplitudes and phases, we introduce W-state graphs: matching-covered graphs equipped with a half-edge 2-colouring such that every perfect matching contains exactly one bichromatic edge and every vertex is incident with a red half-edge. Our main contribution is a complete structural characterization of W-state graphs. We show that a graph is a W-state graph if and only if each of its 3-connected components is…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-05-06","reactions":{}}