Search

We consider a construction by which we obtain a simple graph $${\mathrm {Tr}}(H,v)$$ from a simple graph H and a non-isolated vertex v of H. We call this construction “Trung’s construction.” We prove that $${\mathrm {Tr}}(H,v)$$ is well covered, W $$_2$$ or Gorenstein if and only if H is so. Also, we present a formula for computing the independence polynomial of $${\mathrm {Tr}}(H,v)$$ and investigate when the independence complex of $${\mathrm {Tr}}(H,v)$$ satisfies the Charney–Davis conjecture. As a consequence of our results, we show that the independence complex of every Gorenstein planar graph with girth at least four satisfies the Charney–Davis conjecture.

Let $\alpha=\alpha(G)$ be the independence number of a simple graph $G$ with $n$ vertices and $I(G)$ be its edge ideal in $S=K[x_1,\ldots, x_n]$. If $S/I(G)$ is Gorenstein, the graph $G$ is called Gorenstein over $K$ and if $G$ is Gorenstein over every field, then we simply say that $G$ is Gorenstein. In this article, first we state a condition equivalent to $G$ being Gorenstein and using this we give a characterization of Gorenstein graphs with $\alpha=2$. Then we present some properties of Gorenstein graphs with $\alpha=3$ and as an application of these results we characterize triangle-free Gorenstein graphs with $\alpha=3$., Comment: 9 pages, 1 figure

Let $G$ be a simple graph of order $n$. A dominating set of $G$ is a set $S$ of vertices of $G$ so that every vertex of $G$ is either in $S$ or adjacent to a vertex in $S$. The domination polynomial of $G$ is the polynomial $D(G,x)=\sum_{i=1}^{n} d(G,i) x^{i}$, where $d(G,i)$ is the number of dominating sets of $G$ of size $i$. In this paper we show that cycles are determined by their domination polynomials., Comment: To appear in Ars Combinatoria