Existence of a Connectivity Polynomial for a simple graph?

Question

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

1. 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?

2. 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?

1. Given two vertices $s$ and $t$ and a graph $G$, which polynomial tells whether a path exist between $s$ and $t$ in $G$?

2. What is the connectivity polynomial for vertex-induced random subgraph?

3. What is the connectivity polynomial for the edge-induced random subgraphs?

Answer 1

An answer which seems snide (but isn't!) is $$P(G)=x^k$$ where $k$ is the number of connected components. Another which is possible but maybe not as reasonable is the constant polynomial $Q(G)=k.$

Recall that a proper coloring has vertices connected by an edge required to have unequal colors. Define $\chi (G,c)$ to be the number of proper colorings of $G$ with $c$ colors. It turns out this is a polynomial in $c$ which can (perhaps with some effort) be calculated recursively by the relations

• $\chi(s)=x$ for a graph $s$ consisting of a single point

• $\chi(G)=\chi(H)\chi(H')$ if $G$ is the union of disjoint graphs $H,H'$

• $\chi(G)=\chi(G-e)-\chi(G_e)$ Where $G-e$ is $G$ with the edge $e$ removed (but endpoints retained) and $G_e$ is $G$ with the endpoints of $e$ identified (and resulting multiple edges replaced with a single edge.)

Define a highly improper coloring to be one where vertices connected by an edge are required to have the same color and let $P(G,c)$ be the number of highly improper colorings with $c$ colors. This turns out to be a polynomial, in fact the one given above. It is no effort to compute but there are relations which are almost the same:

• $P(s)=x$ for a graph $s$ consisting of a single point

• $P(G)=P(H)P(H')$ if $G$ is the union of disjoint graphs $H,H'$

• $P(G)=P(G_e).$

Of course it is also easy to get $Q(G)=k$ with

• $Q(s)=1$ for a graph $s$ consisting of a single point

• $Q(G)=Q(H)+Q(H')$ if $G$ is the union of disjoint graphs $H,H'$

• $P(G)=P(G_e).$