I try to find a polynomial for an arbitrary simple graph $G$ that tells whether the graph is connected or not. A graph is st-connected if you can find a path between a vertex $s$ and a vertex $t$ -- an example pair is sink and source.
A special case of this are vertex-induced subgraphs of $G$ and edge-induced subgraphs of $G$: suppose I know that $G$ is st-connected, is $G-v$ st-connected after a vertex deletion? Is $G\backslash e$ st-connected after an edge deletion?
Random graph models
Given a graph $G$, a vertex-induced random subgraph of $G$ is a new graph by vertex deletions and deletions of its incident edges with some probability $p$ on each vertex where vertices are independently deleted. What is the connectivity polynomial in the vertex probability?
Given a graph $G$, a edge-induced random subgraph of $G$ is a new graph by edge deletions and deletions of isolated vertices with some probability $p$ on each edge where edges are independently deleted. What is the connectivity polynomial in the edge probability?
I am trying to understand the connectivity of the random graph models with Percolation theory here and here.
Does there exist a polynomial for the connectivity of a simple graph?
Given two vertices $s$ and $t$ and a graph $G$, which polynomial tells whether a path exist between $s$ and $t$ in $G$?
What is the connectivity polynomial for vertex-induced random subgraph?
What is the connectivity polynomial for the edge-induced random subgraphs?