I am trying to find polynomial, indicator function or sometimes called structure function to express whether a vertex-induced random subgraph $H$ of $G$ is connected or not. The polynomial $\phi(G')$ should be the undirected version while I am trying to figure out the direction version. So

enter image description here

where I cannot fully understand the second line: it multiplies all $p_i$ of $V(H)$ and then multiplies the probabilities of the rest vertices. What does this tell about connectivity?

What are the connectivity polynomials (also called indicator function or structure function) for the vertex-induced random subgraphs of $G$?

  • $\begingroup$ Could you give a bit more context to your question, give a reference maybe? $\endgroup$ – Graffitics Jul 11 '16 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.