5
$\begingroup$

I'm interested in a family of properties of connected simple graphs that comes up in percolation theory.

Let $G$ be a simple connected graph. Now consider the set of subgraphs of $G$ that I will call "cores". A core $C$ of $G$ is a connected subgraph of $G$ with the property that upon "removing" $C$ from $G$ the resulting graph has no edges. I define "removing" as deleting from $G$ all vertices and edges in $C$. Note that a core is not the same as the induced subgraph of a connected dominating set (which makes reference only to the vertices of $C$ and not its edges). For example, the triangle graph has 1 core which is the triangle graph itself, 3 cores that are chains of 3 vertices, and 3 cores that are chains of 2 vertices.

The properties are defined by sums over all the cores:

$f_k(G)=(-1)^{v(G)+1}\sum_{\mathrm{cores}\, C\in G} v(C)^k (-1)^{e(C)}$.

Here $v(C)$ and $e(C)$ are respectively the number of vertices and edges in $C$, and $k$ is a non-negative integer. I've proved that $f_1(G)=0$ for every connected $G$ except for the 1-vertex graph, for which $f_1=1$. I therefore do not need a name for property $f_1$.

What about $f_2$? Here are some special cases. When $G$ is a tree with $n>1$ vertices, then $f_2(G)=0$ unless it is a path; for that case $f_2(G)=2$. Now consider cycles of length $n$. For these the $f_2$ values are $n(n-1)$ . For the complete graphs $f_2(K_n)=n!$ . Perhaps these special cases will help someone make the connection with a known property.

Addendum: I welcome suggestions for a better term for what I've called a graph "core". Here is a rewording of the definition, in case there is still confusion. A core $C$ of a connected graph $G$ is a subgraph of $G$ induced by a subset of the edges of $G$ and which has the following two properties: (1) $C$ is connected, and (2) every edge of $G$ is incident on a vertex of $C$.

It's not obvious from the definition of $f_k(G)$ that these integers are always nonnegative, but I believe this is true for all positive $k$. Is $f_k(G)$ counting something in $G$? If so, then the definition in terms of cores (and the naming problem) can be avoided.

$\endgroup$
  • 1
    $\begingroup$ When you say "deleting all vertices and edges in C", am I correct that we are deleting all the edges that have at least one endpoint in C? My point is that some edges which aren't edges in C, also get deleted. $\endgroup$ – Hugh Thomas Oct 1 '13 at 19:46
  • $\begingroup$ Yes, that's exactly what I was trying to say. $\endgroup$ – Veit Elser Oct 1 '13 at 22:45
  • $\begingroup$ so a core $C$ IS an induced (connected) subgraph of $G$ such that $G\setminus C$ is an independent set (or it's trivially empty). Right ? What you mean with > 3 cores that are chains of 3 vertices A "chain" of 3 vertices is the triangle itself. So the complete graph on 3 vertices has 4 cores, not 7 $\endgroup$ – Alberto Rivelli Oct 9 '13 at 19:30
  • $\begingroup$ The cores are not induced subgraphs (but they are connected). $\endgroup$ – Benoît Kloeckner Oct 9 '13 at 19:51
  • $\begingroup$ please motivate your comment!! I was trying to give an interpretation of the core definition given in the question, because I understand from the question that what he calls "core" is not the same as core in graph theory. He only names them cores.... $\endgroup$ – Alberto Rivelli Oct 9 '13 at 23:45

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.