2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Please, provide more attempt of yours. It is now difficult to get into your situation. $\endgroup$ – Léo Léopold Hertz 준영 Jul 8 '16 at 20:54
  • 1
    $\begingroup$ The problem you link to makes me think you are interested in a random graph based on a given graph and want a polynomial in the edge probability. You need to expand your question to be self-contained; otherwise nobody will know what you are asking. $\endgroup$ – Brendan McKay Jul 9 '16 at 3:05
  • 2
    $\begingroup$ You must study the Laplacian polynomial of graphs. The roots of this polynomial gives you the total number of component of an arbitrary graphs. $\endgroup$ – Shahrooz Janbaz Jul 9 '16 at 3:56
  • $\begingroup$ Look up "reliability polynomial". $\endgroup$ – Brendan McKay Jul 9 '16 at 12:57
2
$\begingroup$

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).$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.