pith. sign in

arxiv: 1511.00159 · v2 · pith:PZ4VEQMTnew · submitted 2015-10-31 · 🧮 math.CO

On mathcal{D}-equivalence classes of some graphs

classification 🧮 math.CO
keywords graphmathcalequivalencegraphspolynomialbarbellclassdomination
0
0 comments X
read the original abstract

Let $G$ be a simple graph of order $n$. 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$. The $n$-barbell graph $Bar_n$ with $2n$ vertices, is formed by joining two copies of a complete graph $K_n$ by a single edge. We prove that for every $n\geq 2$, $Bar_n$ is not $\mathcal{D}$-unique, that is, there is another non-isomorphic graph with the same domination polynomial. More precisely, we show that for every $n$, the $\mathcal{D}$-equivalence class of barbell graph, $[Bar_n]$, contains many graphs, which one of them is the complement of book graph of order $n-1$, $B_{n-1}^c$. Also we present many families of graphs in $\mathcal{D}$-equivalence class of $K_{n_1}\cup K_{n_2}\cup \cdots\cup K_{n_k}$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.