Given an arbitrary graph state $|G\rangle$ represented by the graph $G$, can one use the graphical structure to calculate the number of ebits (entanglement bits) present in the state?
If so, how?
The number of Bell pairs required to construct a given graph state can easily be given an upper bound: $|V|-1$, where $V$ is the set of vertices. You do this simply by preparing the entire state at one site, and teleporting all the other qubits to the relevant party.
I wonder if this is actually all there is to it? If we assume that the entire graph is connected, then every individual qubit is (maximally) entangled with the rest of the graph, and that entanglement must be distributed somehow.
Lower bounds in the multipartite entanglement setting are quite difficult to prove. In a bipartite setting, you'd do it be showing how many Bell states you can extract from asymptotically many copies of the state of interest, but in the regime of multipartite entanglement, that rapidly leads you to MREGS (minimal reversible entanglement generating set), about which very little is known.