Multiplicity of negative one of independence polynomials of graphs
July 09, 2026
Abstract
We initiate the study of the multiplicity of negative one of independence polynomials of graphs. In this article, we simply refer to this as the multiplicity of a graph. As applications, we provide a graph-theoretic description of trees whose independence complexes are contractible, give a new sufficient condition for independence polynomials of graphs to be log-concave, and finally, determine possible pairs \((\mathop{\mathrm{mult}}_{-1}P_G, \alpha(G))\), where \(P_G\) denotes the independence polynomial of \(G\), and \(\alpha(G)\) the independence number. The study of the pairs \((\mathop{\mathrm{mult}}_{-1}P_G, \alpha(G))\) is equivalent to finding all pairs of the numerator degree and denominator degree of the Hilbert series of the edge ideal of \(G\). We also use spectral graph theory to obtain results on the multiplicity of line graphs of forests. Finally, we give some translations and applications in combinatorial commutative algebra.
1 Introduction↩︎
All graphs in this article are assumed to be finite and simple. For a graph \(G\), let \(P_G(x)\) denote the independence polynomial of \(G\), i.e., \[P_G(x)=\sum_{i=0}^{\infty} g_ix^i\] where \(g_0=1\), and \(g_i\) denotes the number of independent sets of \(G\) of size \(i\), for each \(i>0\). Independence polynomials are ubiquitous in the literature of graph theory. We refer to [1] for a comprehensive survey. These polynomials are also known in statistical physics as partition functions of hard-core lattice gas [2]. The evaluation \(P_G(-1)\) is sometimes referred to as the modularity of \(G\) [3]. The values of \(P_G(-1)\), and in particular, when one has \(|P_G(-1)|\leq 1\), have been studied extensively in different contexts [4]–[9].
The independent sets of a graph \(G\) form a simplicial complex, called the independence complex of \(G\), denoted by \(\mathop{\mathrm{Ind}}(G)\). Modularity has subtly appeared in the study of independence complex, as we have \(P_G(-1)=-\tilde{\chi}(\mathop{\mathrm{Ind}}(G))\), where \(\tilde{\chi}(\mathop{\mathrm{Ind}}(G))\) denotes the reduced Euler characteristic of \(\mathop{\mathrm{Ind}}(G)\). Recall that a ternary graph is one that does not have any induced cycle of length divisible by 3. It was a conjecture by Galai and Meshulam, now proven by Chudnovsky, Scott, Seymour, and Spirkl [5], that \[\text{G is a ternary graph} \Longleftrightarrow |P_H(-1)|\leq 1 \text{ for any induced subgraph H of G}.\] Kim [10] provided a different characterization for ternary graphs, confirming Engström’s conjecture [11]: \[\begin{gather} \text{G is a ternary graph} \Longleftrightarrow \mathop{\mathrm{Ind}}(H) \text{ is either contractible or homotopy equivalent to a sphere,} \\ \text{for any induced subgraph H of G}. \end{gather}\] These two characterizations are directly related since for any graph \(G\), \(\mathop{\mathrm{Ind}}(G)\) being contractible implies that \(P_G(-1)=0\), and \(\mathop{\mathrm{Ind}}(G)\) being homotopy equivalent to a sphere implies that \(P_G(-1)=\pm 1\). Therefore, providing that \(G\) is ternary, we have an equivalent statement: \(\mathop{\mathrm{Ind}}(G)\) is contractible if and only if \(P_G(-1)=0\). A homological/topological characterization for this was obtained recently by Faridi and Holleben [12].
In this article, we provide a graph-theoretic description of trees \(T\) that satisfy \(P_T(-1)=0\), or equivalently, have a contractible independence complex. This is our first main result.
Theorem 1 (). Let \(T\) be a tree. Then the independence complex \(\mathop{\mathrm{Ind}}(T)\) is contractible if and only if there exists a tree \(T'\) and a family of rooted trees \(\mathcal{C}\) such that \(T\) is isomorphic to \(\mathcal{G}(T',\mathcal{C})\) as graphs.
We refer to Section 3 for the exact definition of the grafting operation \(\mathcal{G}\). As a preview, we present an example of what such trees look like. Let \(T'\) be the path on three vertices. We replace every edge of \(T'\) with a path on four vertices. We call the resulting graph the 3-subdivision of \(T'\). There are four new vertices compared to \(T'\), and we name them \(v_1,v_2,v_3,v_4\). Next, let \(\mathcal{C}=\{(T_1,u_1),(T_2,u_2),(T_3,u_3),(T_4,u_4)\}\) be a family of rooted trees. By a rooted tree, we mean a tree together with a fixed vertex of the tree. The grafting of \(T'\) and \(\mathcal{C}\), denoted by \(\mathcal{G}(T',\mathcal{C})\), is defined to be the graph obtained by identifying \(u_i\) with \(v_i\) for each \(i=1,2,3,4\). We provide a picture below.
We remark that determining \(P_T(-1)\) for a tree \(T\) has been studied before in different areas of mathematics [12]–[14]. However, the known results are based on the output after inputting \(T\) into an algorithm, while Theorem 1 provides the explicit graph-theoretic description of such trees. In this line of attack, we also provide an algorithmic method to determine \(P_T(-1)\), for a larger class of graphs: pseudo-forests (Theorem 5). Our result is closest to [14], with the difference in the output: a tree reduces to a union of isolated vertices via our process, but it reduces to a path via their process.
Next, we initiate the study of the multiplicity of \(x=-1\) of the independence polynomial \(P_G(x)\), which we denote by \(\mathop{\mathrm{mult}}_{-1} P_G\). Throughout this article, we will simply refer to this as the multiplicity of a graph. Let \(\alpha(G)\) denote the independence number of a graph \(G\), i.e., \(\alpha(G)=\deg P_G\). Recall that a polynomial \[a_0+a_1x+\cdots +a_nx^n\] with positive coefficients is called log-concave if \(a_{i}^2\geq a_{i-1}a_{i+1}\) for any \(1\leq i \leq n-1\). A log-concave polynomial is always unimodal. It is a problem of great interest in graph theory to determine which graphs have log-concave/unimodal independence polynomials [15]–[21]. Our next main result gives a new such class of graphs.
Theorem 2 (). If \(\mathop{\mathrm{mult}}_{-1}(G)\geq \alpha(G)-2\), then \(P_G\) is log-concave.
Determining all pairs of \((\mathop{\mathrm{mult}}_{-1} P_G, \alpha(G))\) is the same as determining all pairs of dimensions and degrees of the \(h\)-polynomial of edge ideals, which are all pairs of degrees of the numerator and denominator of the corresponding Hilbert series written as a rational function (see Section 7 for definitions). To that end, our final goal is to determine the following sets: \[\begin{align} \mathcal{MI}(n)&\mathrel{\vcenter{:}}= \{ (\mathop{\mathrm{mult}}_{-1} P_G, \alpha(G)) \mid \text{G is a graph on n vertices} \}, \\ \mathcal{MI}^c(n)&\mathrel{\vcenter{:}}= \{ (\mathop{\mathrm{mult}}_{-1} P_G, \alpha(G)) \mid \text{G is a connected graph on n vertices} \}, \\ \mathcal{MI}&\mathrel{\vcenter{:}}= \bigcup_{n=1}^{\infty} \mathcal{MI}(n), \quad \text{and} \quad \mathcal{MI}^c\mathrel{\vcenter{:}}=\bigcup_{n=1}^{\infty} \mathcal{MI}^c(n), \end{align}\] for each \(n\geq 1\). Except for \(\mathcal{MI}^c(n)\), we have a complete description.
Theorem 3 ( and 18). We have \[\begin{align} \mathcal{MI}(n) &= \{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a< b \leq n-1 \} \cup \{(n,n)\} \text{ for each n\geq 1},\\ \mathcal{MI} &= \{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a\leq b \} \setminus \{(0,0)\},\\ \mathcal{MI}^c &= \{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a< b \} \cup \{(1,1)\}. \end{align}\]
The set \(\mathcal{MI}^c(n)\) is harder to determine, as the requirement that the graph be connected imposes additional restrictions on its invariants. We obtain bounds for \(\mathcal{MI}^c(n)\) together with many realizable points on the boundary. The following is proved throughout Section 5.
Theorem 4 (). Let \(n\geq 2\). We have \[\mathcal{MI}^c(n)\subseteq \{(a,b)\in \mathbb{Z}_{\geq 0}^2 \mid 0\leq a <b \leq n-2\} \cup\{(0,n-1)\}.\] Moreover, if \(n\) is odd, then \[\{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a<b\leq n-2 \text{ and } a\leq \lceil n/2 \rceil-1 \} \setminus \{(\lceil n/2 \rceil-1,n-2)\}\cup \{(0,n-1)\}\subseteq \mathcal{MI}^c(n),\] and if \(n\) is even, then \[\{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a<b\leq n-2 \text{ and } a\leq n/2 -1 \} \cup \{(0,n-1)\}\subseteq \mathcal{MI}^c(n).\]
In fact, the lower bound for \(\mathcal{MI}^c(n)\) in Theorem 4 is exactly the set \(\mathcal{MI}^c(n)\) itself for \(2\leq n\leq 8\). Whether this holds for larger \(n\) reduces to Question 14 and remains open.
Spectral theory is the study of eigenvalues of a matrix, i.e., the roots of the characteristic polynomial of a matrix. Spectral graph theory studies graph properties and invariants via the use of spectral theory. It is thus no surprise that techniques in spectral graph theory can produce interesting information on the multiplicity of graphs. In Section 6, we translate some results in spectral graph theory into our context, giving multiplicity of the line graph of forests.
Finally, we remark that \(\mathop{\mathrm{mult}}_{-1}P_G\) is exactly negative one multiplied with the \(\mathfrak{a}\)-invariant of the edge ideal of \(G\) [22]. In other words, every result we obtain in this article has an equivalent statement in combinatorial commutative algebra. We provide the translations for some, together with some applications, in Section 7. In particular, we obtain many results regarding possible pairs of \(\mathfrak{a}\)-invariants and dimension of edge ideals of graphs. These results align with the large (and growing) literature on constructing graphs with given parameters [6], [23]–[26], and of finding tuples of invariants of edge ideals [27]–[31].
Acknowledgements↩︎
We thank Priyavrat Deshpande, Takayuki Hibi, Do Trong Hoang, Thiago Holleben, and Adam van Tuyl for helpful feedback on an earlier version of this article. The first named author is supported by ANRF National Postdoctoral Fellowship. The first, second, fourth, and sixth named authors are supported by the Infosys Foundation.
2 Graph theory↩︎
Let \(G=(V(G),E(G))\) be a finite simple graph. For a vertex \(v\in V(G)\), a vertex that forms an edge with \(v\) in \(G\) is called its neighbor in \(G\). The set of all neighbors of \(v\) is denoted by \(N_G(v)\), and \(N_G[v]\mathrel{\vcenter{:}}= N_G(v)\cup \{v\}\) is called the closed neighborhood of \(v\). A vertex \(v\in V(G)\) is called a pendant vertex of \(G\) if \(|N_G(v)|=1\). The unique neighbor of a pendant vertex is called a support vertex. Equivalently, a support vertex is a vertex whose neighborhood contains a pendant vertex. When \(G\) is well understood from the context, we will drop the subscripts. For a set of vertices \(U\subseteq V(G)\), let \(G\setminus U\) denote the induced subgraph of \(G\) with the vertex set \(V(G)\setminus U\).
We recall the following classical result on computing independence polynomials.
Lemma 1 (). Let \(G\) be a finite simple graph and \(u\in V(G)\). Then \[P_G(x) = P_{G\setminus \{u\}}(x)+xP_{G\setminus N[u]}(x).\]
We recall a common construction: cone over a set. Let \(G\) be a finite simple graph on \([n]\) and \(U\subseteq V(G)\) be a set of vertices of \(G\). The cone of \(G\) over \(V(G)\setminus U\), denoted by \(\mathop{\mathrm{cone}}(G,U)\), is the graph on \([n+1]\) with \[E(\mathop{\mathrm{cone}}(G,U)) = E(G)\cup \{ \{i,n+1\} \mid i\notin U \}.\] It is straightforward to obtain the independence polynomial of \(\mathop{\mathrm{cone}}(G,U)\) when \(U\) is an independent set.
Lemma 2. Let \(G\) be a finite simple graph and \(U\) an independent set of \(G\). Then \[P_{\mathop{\mathrm{cone}}(G,U)}(x)=P_G(x)+x(1+x)^{|U|}.\] Consequently, we have the following:
if \(\mathop{\mathrm{mult}}_{-1}P_G<|U|<\alpha(G)\), then \[\mathop{\mathrm{mult}}_{-1}P_{\mathop{\mathrm{cone}}(G,U)} = \mathop{\mathrm{mult}}_{-1} P_G \quad \text{and}\quad \alpha(\mathop{\mathrm{cone}}(G,U))=\alpha(G);\]
if \(|U|<\mathop{\mathrm{mult}}_{-1} P_G\), then \[\mathop{\mathrm{mult}}_{-1}P_{\mathop{\mathrm{cone}}(G,U)} = |U| \quad \text{and}\quad \alpha(\mathop{\mathrm{cone}}(G,U))=\alpha(G);\]
if \(|U|=\alpha(G)\) and \(G\) has an edge, then \[\mathop{\mathrm{mult}}_{-1}P_{\mathop{\mathrm{cone}}(G,U)} = \mathop{\mathrm{mult}}_{-1} P_G \quad \text{and}\quad \alpha(\mathop{\mathrm{cone}}(G,U))=\alpha(G)+1.\]
Proof. Assume that \(V(\mathop{\mathrm{cone}}(G,U))= V(G)\cup \{u\}\). Then the independence polynomial formula follows from Lemma 1, remarking that \(\mathop{\mathrm{cone}}(G,U)\setminus N_{\mathop{\mathrm{cone}}(G,U)}[u]=U\) is an independent set of size \(|U|\). The second statement then follows straightforwardly. ◻
For two graphs \(G\) and \(H\), their union, denoted by \(G\sqcup H\), is the graph obtained by merging the vertex and edge sets, i.e., \[V(G\sqcup H) = V(G)\sqcup V(H) \quad\text{and} \quad E(G\sqcup H) = E(G)\sqcup E(H).\] Here we use disjoint unions in the definition to emphasize that \(V(G)\) and \(V(H)\) are considered disjoint in this construction. The following result is standard, hence we do not provide a proof.
Lemma 3. Let \(G\) and \(H\) be two finite simple graphs. Then \(P_{G\sqcup H}(x)=P_G(x)P_H(x)\). In particular, we have \[\mathop{\mathrm{mult}}_{-1} P_{G\sqcup H}= \mathop{\mathrm{mult}}_{-1}P_G + \mathop{\mathrm{mult}}_{-1} P_H \quad \text{and}\quad \alpha(G\sqcup H)=\alpha(G)+\alpha(H).\]
We recall some common graphs. Let \(n\geq 1\) be an integer. The star graph and complete graph on \([n]\), denoted by \(S_n\) and \(K_n\), respectively, are the graphs with the edge sets: \[E(S_n)=\{\{i,n\}\colon 1\leq i\leq n-1\} \quad \text{and}\quad E(K_n)= \{\{i,j\}\colon 1\leq i<j\leq n \}.\] These two graphs, together with the graph of \(n\) isolated vertices, can be fully characterized using independence polynomials. The next three results are standard, and we leave them as exercises to interested readers.
Lemma 4. Let \(G\) be a graph on \(n\geq 1\) vertices. The following are equivalent:
\(G\) is \(\sqcup_{k=1}^n K_1\), the graph of \(n\) isolated vertices;
\(\alpha(G)=n\);
\(\mathop{\mathrm{mult}}_{-1} P_G=\alpha(G)\).
Lemma 5. Let \(G\) be a graph on \(n\geq 1\) vertices. The following are equivalent:
\(G\) is \(K_n\), the complete graph on \(n\) vertices;
\(\alpha(G)=1\);
\(P_G(x)=1+nx\).
Lemma 6. Let \(G\) be a connected graph on \(n\geq 2\) vertices. The following are equivalent:
\(G\) is \(S_n\), the star graph on \(n\) vertices;
\(\alpha(G)=n-1\);
\(P_{G}(x)=(1+x)^{n-1}+x\).
3 Pseudo-forests with positive multiplicity↩︎
The goal of this section is twofold. The first is to establish an algorithmic method to determine the value of \(P_G(-1)\), where \(G\) is a pseudo-forest. The second objective is to provide an explicit description of trees \(T\) with \(P_T(-1)=0\). We start with a key lemma.
Lemma 7 (). Let \(G\) be a finite simple graph and \(v\) be a support vertex of \(G\). Then \[P_G(-1)=(-1)P_{G\setminus N[v]}(-1).\]
Definition 1. For a finite simple graph \(G\), a support sequence of \(G\) is a sequence of vertices \(v_1,\dots, v_t\) such that \(v_i\) is a support vertex of \(G\setminus \cup_{j=1}^{i-1} N[v_j]\) for any \(i\in [t]\).
By definition, a support sequence \(v_1,\dots, v_t\) of \(G\) is maximal if and only if \(G\setminus \cup_{i=1}^{t} N_{G}[v_i]\) has no support vertex if and only if \(G\setminus \cup_{i=1}^{t} N_{G}[v_i]\) has no pendant vertex. It is noteworthy that two maximal support sequences may have different lengths, and the resulting graph \(G\setminus \cup_{i=1}^{t} N_{G}[v_i]\) is dependent on the sequence.
Example 1. Let \(G\) be the following tree.
It is straightforward that \(v_3\) and \(v_2,v_4\) are both maximal support sequences of \(G\). Moreover, we have \(G\setminus
N_G[v_3]=K_1\sqcup K_1\) and \(G\setminus (N_G[v_2]\cup N_G[v_4])=K_1\).
Recall that a pseudo-forest is a graph \(G\) such that any connected component of \(G\) has at most one cycle. We shall compute the value of \(P_G(-1)\) for any pseudo-forest \(G\).
Theorem 5. Let \(G\) be a pseudo-forest and \(v_1,\dots, v_t\) a maximal support sequence of \(G\) for some integer \(t\). Then \(G \setminus \cup_{i=1}^t N_G[v_i]\) is a union of cycles and isolated vertices, and \[P_G(-1)=(-1)^t P_{G \setminus \cup_{i=1}^t N_G[v_i]} (-1).\] Moreover, set \(H=G \setminus \cup_{i=1}^t N_G[v_i]\), and \[\begin{align} a&\mathrel{\vcenter{:}}= \# \text{k-cycles of H where k=0 (mod 6)},\\ b&\mathrel{\vcenter{:}}= \# \text{k-cycles of H where k=2,4 (mod 6)},\\ c&\mathrel{\vcenter{:}}= \# \text{k-cycles of H where k=3 (mod 6)},\\ d&\mathrel{\vcenter{:}}= \# \text{isolated vertices of H}. \end{align}\] Then \[P_G(-1)= \begin{cases} 0 & \text{if } d>0,\\ (-1)^{t+b+c} (2)^{a+c} & \text{if } d=0. \end{cases}\]
Proof. Since \(G\) is a pseudo-forest, the only subgraphs of \(G\) that do not have any pendant vertex are unions of cycles and isolated vertices. The first statement then follows from the fact that \(G \setminus \cup_{i=1}^t N_G[v_i]\) has no pendant vertex, and Lemma 7. The second statement comes from Lemma 3, and the formula \[P_{C_n}(-1)= \begin{cases} 2 & \text{if } n=0 \text{ (mod 6)}\\ 1 & \text{if } n=1,5 \text{ (mod 6)}\\ -1 & \text{if } n=2,4 \text{ (mod 6)}\\ -2 & \text{if } n=3 \text{ (mod 6)} \end{cases} \tag*{(\cite{modularity-thesis}).\qedhere}\] ◻
We obtain a quick corollary about the independence complex of \(G\) where \(G\) is a special class of pseudo-forests.
Corollary 1. Let \(G\) be a ternary pseudo-forest, i.e., a pseudo-forest that does not have any cycle of length divisible by 3. Then the independence complex of \(G\) is contractible if and only if for any maximal support sequence \(v_1,\dots, v_t\) of \(G\), the graph \(G \setminus \cup_{i=1}^t N_G[v_i]\) has an isolated vertex.
Next, we characterize trees whose independence polynomial vanishes at \(-1\). For this, we introduce some terminology.
Definition 2. Let \(T\) be a tree. The \(3\)-subdivision of \(T\), denoted by \(T^*\), is the tree obtained from \(T\) by replacing each edge \(e=\{u,v\}\) with a path of length \(3\). More precisely, for each edge \(e=\{u,v\}\), introduce two new vertices \(w_{u,e}\) and \(w_{v,e}\), and replace \(e\) with the edges \(\{u,w_{u,e}\}\), \(\{w_{u,e},w_{v,e}\}\), and \(\{w_{v,e},v\}\).
We present an example in Figure 3 to illuminate the concept.
Let \(T=(V,E)\) be a tree. For each edge \(e \in E\) and each vertex \(u \in e\), let \[\mathcal{C}=\{(T_{u,e}, r_{u,e}) : e \in E,\; u \in e\}\] denote an indexed family of rooted graphs, where \(T_{u,e}=(V_{u,e},E_{u,e})\) is a graph and \(r_{u,e} \in V_{u,e}\) is a fixed vertex in \(V_{u,e}\). We call such a \(\mathcal{C}\) a family of rooted graphs corresponding to \(T\). Here by a rooted graph, we mean a pair of a graph and a vertex of its.
Definition 3. For a tree \(T=(V,E)\) and a family of rooted graphs \(\mathcal{C}\) corresponding to \(T\), the grafting of \(\mathcal{C}\) on \(T\), denoted by \(\mathcal{G}(T,\mathcal{C})\), is defined as the graph obtained from \(T^*\) by identifying the root \(r_{u,e}\) of \(T_{u,e}\) to the vertex \(w_{u,e}\) of \(T^*\) for every pair \((u,e)\) with \(u \in e\) and \(e \in E\).
Formally, \[\mathcal{G}(T,\mathcal{C}) \;=\; \left( \, T^* \;\sqcup\;\bigsqcup_{\substack{e \in E \\ u \in e}} T_{u,e} \,\right)\Big/ \sim,\] where the relation \(\sim\) identifies the root \(r_{u,e}\) of each \(T_{u,e}\) with the vertex \(w_{u,e}\) in \(T^*\).
Remark 6. As can be seen later (the proof of Theorem 7), when we study \(\mathcal{G}(T,\mathcal{C})\), the structure of the graphs in \(\mathcal{C}\) plays a minimal role. When there are no specific restriction on \(\mathcal{C}\), we will refer to \(\mathcal{G}(T,\mathcal{C})\) as simply a grafting on \(T\).
Example 2. Let \(T\) be the tree as in Figure 3. The edge set \(E= \{(1,2),(2,3),(2,4),(4,5),(4,6)\}\). Consider the following family of rooted trees \[\mathcal{C} = \{(T_{1,(1,2)},r_{1,(1,2)}), (T_{2,(1,2)},r_{2,(1,2)}), \ldots, (T_{4,(4,6)},r_{4,(4,6)}), (T_{6,(4,6)},r_{6,(4,6)})\}.\] The grafting \(\mathcal{G}(T,\mathcal{C})\) of \(\mathcal{C}\) on \(T\) will look like the following tree
Figure 4: 
.
Theorem 7. A tree \(T\) satisfies \(P_T(-1)=0\) if and only if there exist a tree \(T'\) and a family of rooted trees \(\mathcal{C}\) such that \(T \cong \mathcal{G}(T',\mathcal{C})\).
Proof. We prove the forward implication by induction on the number of vertices in \(T\).
If \(|V(T)|=1\), then \(T\) consists of a single vertex. In this case \(P_T(-1)=0\), and we may take \(T'=T\) and \(\mathcal{C}=\emptyset\). Hence the statement holds.
Assume the statement holds for all trees with fewer than \(n\) vertices, and let \(T\) be a tree with \(|V(T)|=n\) such that \(P_T(-1)=0\). Since \(T\) is a tree, it has a pendant vertex. Let \(u\) be a pendant vertex and let \(v\) be its unique neighbor. By Lemma 7, \(P_T(-1)=(-1)\cdot P_{T \setminus N[v]}(-1).\) Since \(P_T(-1)=0\), it follows that \(P_{T \setminus N[v]}(-1)=0.\) Clearly \(T \setminus N[v]\) is a forest. Let its connected components be \(T_1,\dots,T_k\). Then \(P_{T \setminus N[v]}(-1)=\prod_{i=1}^k P_{T_i}(-1)=0,\) so there exists at least one component, say \(T_i\), such that \(P_{T_i}(-1)=0\). By the induction hypothesis, there exist a tree \(T'_i\) and a family \(\mathcal{C}_i\) such that \[T_i \cong \mathcal{G}(T'_i,\mathcal{C}_i).\]
Since \(T_i\) arises from removing \(N[v]\), there exist vertices \(u_i \in V(T_i)\) and \(v_i \in N(v)\) such that \(\{u_i,v_i\}\in E(T)\).
We now reconstruct \(T\) from \(T_i\), for which we consider the following two cases.
Case 1: Suppose that \(u_i \in V(T'_i)\). We define a tree \(T'\) and an indexed family \(\mathcal{C}\) as follows. Let \[V(T') = V(T'_i)\cup\{u\}, \qquad E(T') = E(T'_i)\cup\{\{u,u_i\}\}.\] For the pair \((u,\{u,u_i\})\), set \(w_{u,\{u,u_i\}}=r_{u,\{u,u_i\}}=v\), and let \(T_{u,\{u,u_i\}}\) be the subtree of \(T\) rooted at \(v\) obtained after deleting \(u\) and \(v_i\). Similarly, for the pair \((u_i,\{u,u_i\})\), set \(w_{u_i,\{u,u_i\}}=r_{u_i,\{u,u_i\}}=v_i\), and let \(T_{u_i,\{u,u_i\}}\) be the subtree of \(T\) rooted at \(v_i\) obtained after deleting \(v\) and \(u_i\). Finally, define \[\mathcal{C}=\mathcal{C}_i \cup \{(T_{u,\{u,u_i\}},r_{u,\{u,u_i\}}), (T_{u_i,\{u,u_i\}},r_{u_i,\{u,u_i\}})\}.\] Then, \(T \cong \mathcal{G}(T',\mathcal{C})\), as required.
Case 2: Suppose, \(u_i\) lies in one of the trees \(T_{u',e'}\) of \(\mathcal{C}_i\), say \(u_i \in V(T_{u',e'})\) for some \((T_{u',e'}, r_{u',e'}) \in \mathcal{C}_i\). We define \(T'\) and \(\mathcal{C}\) as follows.
Set \(T' = T'_i\). Let \(T''\) be the subtree of \(T\) rooted at \(u_i\) obtained by deleting \(T_i \setminus \{u_i\}\) from \(T\), and define \[T'_{u',e'} = T_{u',e'} \cup T''.\] Now define \[\mathcal{C} = \big(\mathcal{C}_i \setminus \{(T_{u',e'}, r_{u',e'})\}\big) \cup \{(T'_{u',e'}, r_{u',e'})\},\] where \((T'_{u',e'}, r_{u',e'})\) is indexed by the same pair \((u',e')\) as \((T_{u',e'}, r_{u',e'})\).
In this case as well, we obtain \(T \cong \mathcal{G}(T',\mathcal{C}),\) as desired
For the converse, we need to prove that for any tree \(T\) and any indexed family \(\mathcal{C}\) of rooted trees indexed by pairs of vertices and edges \((u,e)\) of \(T\), where the vertex \(u\) is an adjacent vertex of edge \(e\), \(P_{\mathcal{G}(T,\mathcal{C})}(-1) = 0.\) Let \(u\) be a pendant vertex of \(\mathcal{G}(T,\mathcal{C})\) which is also a pendant vertex of \(T\), and \(v\) be the unique neighborhood of \(u\). Thus, by Lemma 7, we have \[P_{\mathcal{G}(T,\mathcal{C})}(-1) = (-1)P_{\mathcal{G}(T,\mathcal{C}) \setminus N[v]}(-1).\] Now, observe that \(\mathcal{G}(T,\mathcal{C}) \setminus N[v]\) is the disjoint union of \(\mathcal{G}(T\setminus \{v\},\mathcal{C}\setminus \{T_{u,e},T_{v,e}\})\), \(T_{u,e}\setminus N[r_{u,e}]\), and \(T_{v,e}\setminus \{r_{v,e}\}.\) Therefore, by Lemma 3, we get \[P_{\mathcal{G}(T,\mathcal{C})}(-1) = (-1)P_{\mathcal{G}(T\setminus \{v\},\mathcal{C}\setminus \{T_{u,e},T_{v,e}\})}(-1)P_{T_{u,e}\setminus N[r_{u,e}]}(-1)P_{T_{v,e}\setminus \{r_{v,e}\}}(-1).\] Now, consider the graph \(\mathcal{G}(T\setminus \{v\},\mathcal{C}\setminus \{T_{u,e},T_{v,e}\})\) and repeat the same process by choosing a pendant vertex. Continuing this process and using Lemmas 7, 3 iteratively, we get \[P_{\mathcal{G}(T,\mathcal{C})}(-1) = (-1)^{\vert V(T) - 1\vert}P_{K_1}(-1) \prod_{\substack{e \in E \\ u,v \in e}}P_{T_{u,e}\setminus N[r_{u,e}]}(-1)P_{T_{v,e}\setminus \{r_{v,e}\}}(-1).\] Since \(P_{K_1}(-1) = 0\), we get \(P_{\mathcal{G}(T,\mathcal{C})}(-1) = 0\). This completes the proof. ◻
Remark 8. A closer look at the proof of Theorem 7 reveals that in fact if \(T\) is a tree and \(\mathcal{C}\) a family of rooted graphs corresponding to \(T\), then \(P_{\mathcal{G}(T,\mathcal{C})} (-1)=0\). Thus the grafting operation gives more graphs \(G\) such that \(P_G(-1)=0\). It is straightforward to see that if \(G\) is a connected graph with at least one edge, then the whiskered graph \(\mathcal{W}(G)\) (see Definition 4) is a grafting on the path graph on two vertices, \(K_2\). On the other side of the spectrum, not all graphs \(G\) with \(P_G(-1)=0\) can be obtained by grafting. We present a smallest example (in terms of number of vertices) of such a connected graph below.
4 Graphs with high multiplicity↩︎
In this section we study graphs \(G\) with high values of \(\mathop{\mathrm{mult}}_{-1}P_G\). The main result of this section is the following.
Theorem 9. Let \(G\) be a finite simple graph on \(n\geq 1\) vertices. If \(\mathop{\mathrm{mult}}_{-1} P_G \geq \alpha(G)-2\), then \(P_G\) is log-concave.
It is clear that \(\mathop{\mathrm{mult}}_{-1}P_G\leq \alpha(G)\), and equality occurs exactly when \(G\) is \(\sqcup_{k=1}^{\alpha(G)} K_1\) (Lemma 4). For the rest of the section, if \(n \geq 2\), we assume that \(G\) has at least one edge. Then \(\mathop{\mathrm{mult}}_{-1}P_G\leq \alpha(G)-1\). We analyze when the equality occurs in this case.
Lemma 8. Let \(G\) be a finite simple graph on \(n\geq 1\) vertices. Then \(\mathop{\mathrm{mult}}_{-1}P_G= \alpha(G)-1\) if and only if \[P_G(x)=(1+x)^{\alpha(G)-1}\left(1+(n-\alpha(G)+1)x\right),\] and \(G\neq \sqcup_{k=1}^n K_1\). In particular, in this case, \(|E(G)|= \binom{n-\alpha(G)+1}{2}\).
Proof. Since \(P_G\) is a polynomial of degree \(\alpha(G)\), we have \(\mathop{\mathrm{mult}}_{-1}P_G= \alpha(G)-1\) if and only if \(P_G(x)=(1+x)^{\alpha(G)-1}\left(1+cx\right)\) for some constant \(c\) such that \(1-c\neq 0\). Moreover, we know that the coefficient of \(x\) in \(P_G(x)\) is \(n\), which forces \(c=n-\alpha+1\) in this case. Also, \(1-c\neq 0\) is equivalent to \(n\neq \alpha\), which occurs if and only if \(G\neq \sqcup_{k=1}^n K_1\) by Lemma 4. The first statement then follows.
For the second statement, note that the coefficient of \(x^2\) in \(P_G(x)\) is exactly the number of non-edges of \(G\). Therefore we have \[(n-\alpha(G)+1) \binom{\alpha(G)-1}{\alpha(G)-2} + \binom{\alpha(G)-1}{2} =\binom{n}{2} -|E(G)|.\] The result then follows. ◻
Next we investigate the condition \(\mathop{\mathrm{mult}}_{-1}P_G= \alpha(G)-2\).
Lemma 9. Let \(G\) be a finite simple graph on \(n\geq 1\) vertices. Then \(\mathop{\mathrm{mult}}_{-1}P_G= \alpha(G)-2\) if and only if \[P_G(x)=(1+x)^{\alpha(G)-2}\left(1+(n-\alpha(G)+2)x + \left( \binom{n-\alpha(G)+2}{2} - |E(G)| \right)x^2\right)\] and \[|E(G)|\neq \binom{n-\alpha(G)+1}{2}.\] Moreover, in this case, we have \(|E(G)| < \binom{n-\alpha(G)+2}{2}\).
Proof. Since \(P_G\) is a polynomial of degree \(\alpha(G)\), we have \(\mathop{\mathrm{mult}}_{-1}P_G= \alpha(G)-2\) if and only if \(P_G(x)=(1+x)^{\alpha(G)-2}\left(1+ax+bx^2\right)\) for some constants \(a,b\) with \(1-a+b\neq 0\). In this case, we have \[(1+x)^{\alpha(G)-2}\left(1+ax+bx^2\right)=P_G(x)=1+nx+\left(\binom{n}{2}-|E(G)| \right) x^2 + \cdots.\] By matching the first three coefficients, we obtain the system of equations \[\begin{cases} a&=n-\alpha(G)+2\\ (\alpha(G)-2)a + b&= \binom{n}{2}-|E(G)| - \binom{\alpha(G)-2}{2} \end{cases}.\] The first statement then straightforwardly follows from solving this system. For the second statement, observe that by matching the leading coefficients, we have \[\binom{n-\alpha(G)+2}{2}-|E(G)| = b = \#\text{independent sets of G of size \alpha(G)},\] which is positive by definition of \(\alpha(G)\). This concludes the proof. ◻
We are now ready to prove the main result of this section
Proof of Theorem 9. It is known that the product of two log-concave polynomials is log-concave [32]. Thus the result follows if \(\mathop{\mathrm{mult}}_{-1}P_G\geq \alpha(G)-1\), since \(P_G\) factors into linear forms then. In the case \(\mathop{\mathrm{mult}}_{-1} P_G=\alpha(G)-2\), by Lemma 9, we have \[P_G(x)=(1+x)^{\alpha(G)-2}\left(1+(n-\alpha(G)+2)x + \left( \binom{n-\alpha(G)+2}{2} - |E(G)| \right)x^2\right)\] with \(\binom{n-\alpha(G)+2}{2} - |E(G)|>0\). In other words, the polynomial \[1+(n-\alpha(G)+2)x + \left( \binom{n-\alpha(G)+2}{2} - |E(G)| \right)x^2\] has positive coefficients, and since \[(n-\alpha(G)+2)^2 >\binom{n-\alpha(G)+2}{2} \geq\binom{n-\alpha(G)+2}{2} - |E(G)|,\] it is log-concave. The result then follows. ◻
Remark 10. It is tempting to obtain an analog for the next case \(\mathop{\mathrm{mult}}_{-1}P_G=\alpha(G)-3\), which implies that \[P_G(x)=(1+x)^{\alpha(G)-3}(1+ax+bx^2+cx^3)\] for some integers \(a,b,c\). It is straightfroward that \[\begin{align} a&=n-\alpha(G)+3,\\ b&=\binom{n-\alpha(G)+3}{2} - |E(G)|,\\ c&= (\alpha(G)-3)|E(G)|+ \binom{n-\alpha(G)+3}{3} - \binom{n}{3} + \#\text{independent sets of G of size 3}. \end{align}\] It is unclear whether we have \(b>0\). If this is true, then we know at least that \(P_G\) is unimodal by similar arguments as in the proof of Theorem 9, and the fact that the product of a log-concave polynomial and a unimodal one is unimodal [32].
We end this section with a natural question.
Question 11. Which graphs \(G\) satisfy \(\mathop{\mathrm{mult}}_{-1}P_G = \alpha(G)-1\) (or \(\mathop{\mathrm{mult}}_{-1}P_G = \alpha(G)-2\))?
Despite the restrictive conditions that \(\mathop{\mathrm{mult}}_{-1}P_G \in \{ \alpha(G)-2, \alpha(G)-1\}\) imposes on the graph \(G\), there are surprisingly many graphs with either value for \(\mathop{\mathrm{mult}}_{-1} P_G\). We shall recall a method to obtain either class.
Definition 4. For a graph \(G\) on \([n]\), let \(\mathcal{W}(G)\) denote the graph on \([2n]\) with \[E(\mathcal{W}(G))=E(G) \cup \{ \{i,i+n\} \mid i\in [n] \}.\]
Pictorially, \(\mathcal{W}(G)\) is exactly \(G\) with a new pendant vertex each attached to vertices of \(G\). The graph \(\mathcal{W}(G)\) is sometimes called the whiskered graph of \(G\), and can also be obtained by the operation of corona product. We give the example of \(K_4\) and \(\mathcal{W}(K_4)\) below as an illustration.
The independence polynomial of \(\mathcal{W}(G)\) is well understood.
Lemma 10 (). Let \(G\) be a finite simple graph with at least one edge. Then \[\mathop{\mathrm{mult}}_{-1}P_{\mathcal{W}(G)} = |V(G)|- \alpha(G) \quad \text{and} \quad \alpha(\mathcal{W}(G))=|V(G)|.\]
For example, \(G=\mathcal{W}(K_n)\) satisfies \(\mathop{\mathrm{mult}}_{-1}P_G = n-1 = \alpha(G)-1\). In fact we also have \(\mathop{\mathrm{mult}}_{-1} P_{K_n}=0 = \alpha(K_n)-1\). We remark that there are more graphs with this property, even in small number of vertices, and it poses a challenging problem to characterize them all.
5 Pairs of multiplicity and independence number↩︎
The goal of this section is to provide bounds for \(\mathcal{MI}^c(n)\), together with lattice points in \(\mathbb{Z}_{\geq 0}^2\) that can be realized on its boundary. It is clear that \(\mathcal{MI}^c(1)=\{ (1,1) \}\). We note down the sets \(\mathcal{MI}^c(n)\) for \(2\leq n \leq 8\) for an illustration.
For the rest of this section, we assume that \(n\geq 2\). We start with a straightforward upper bound for \(\mathcal{MI}^c(n)\).
Lemma 11. Let \(G\) be a connected graph on \(n\geq 2\) vertices. Then \(0\leq \mathop{\mathrm{mult}}_{-1}P_G < \alpha(G)\leq n-1\). In other words, \[\mathcal{MI}^c(n) \subseteq \{(a,b)\mid 0\leq a<b\leq n-2 \} \cup \{ (0,n-1) \}.\]
Proof. It is straightforward that \[0\leq \mathop{\mathrm{mult}}_{-1}P_G \leq \alpha(G)\leq n.\] However, either \(\alpha(G)=n\) or \(\mathop{\mathrm{mult}}_{-1}P_G = \alpha(G)\) would imply that \(G\) is the graph of \(n\geq 2\) isolated vertices (Lemma 4), a contradiction. On the other hand, by Lemma 6, we have \(\alpha(G)=n-1\) if and only if \(G\) is the star graph \(S_n\), which in turn implies that \(\mathop{\mathrm{mult}}_{-1}P_G=0\). The result then follows. ◻
The next goal is to present a lower bound for \(\mathcal{MI}^c(n)\). To do so, it is necessary to present graph operations where we can control both the multiplicity and independence number of a graph. The cone operation is one such operation. The following is a direct translation of Lemma 2. Thus we do not provide a proof.
Lemma 12. Let \(n\geq 1\) be an integer and \((a,b)\in \mathcal{MI}^c(n)\). Then we have the following:
\((a,b+1)\in \mathcal{MI}^c(n+1)\);
\((a,b) \in \mathcal{MI}^c(n+1)\) if \(a+2\leq b\);
\((a',b)\in \mathcal{MI}^c(n+1)\) for any \(0\leq a'<a\).
A shortcoming of the above lemma is that it does not address the points \((a,a+1)\in \mathcal{MI}^c(n)\). We give a positive answer to this in the next result.
Lemma 13. Let \(n\geq 2\) be an integer and \((a,a+1)\in \mathcal{MI}^c(n)\) for some \(a\geq 0\). Then \((a,a+1)\in \mathcal{MI}^c(n+1)\).
Proof. Since \((0,1)\) is realized by the complete graph \(K_n\) (Lemma 5) for any \(n\geq 2\), we have \((0,1)\in \mathcal{MI}^c(n)\) for any \(n\geq 2\). Thus for the rest of the proof we can assume that \(a\geq 1\).
Let \(G\) be a connected graph on \(n\) vertices with \(\mathop{\mathrm{mult}}_{-1}P_G = a\) and \(\alpha(G)=a+1\). The existence of \(G\) is guaranteed by the hypothesis \((a,a+1)\in \mathcal{MI}^c(n)\). Then by Lemma 8, we have \[P_G(x)=(1+x)^{a}(1+(n-a)x).\] Since we have \(\alpha(G)=a+1\), there exists an independent set \(U\) of \(G\) such that \(|U|=a\). By Lemma 2, we have \[P_{\mathop{\mathrm{cone}}(G,U)} (x)=P_G(x)+x(1+x)^a = (1+x)^{a}(1+(n-a+1)x).\] Remark that \(1+(n-a+1)(-1) = \alpha(G)-n-1 \leq -1\). Thus \[\mathop{\mathrm{mult}}_{-1} P_{\mathop{\mathrm{cone}}(G,U)} = a \quad \text{and} \quad \alpha(\mathop{\mathrm{cone}}(G,U) )=a+1.\] Finally, due to \(a\geq 1\), the graph \(\mathop{\mathrm{cone}}(G,U)\) is connected on \(n+1\) vertices. Thus \((a,a+1)\in \mathcal{MI}^c(n+1)\), as desired. ◻
As a consequence, we show that the set \(\mathcal{MI}^c(n)\) does become larger as \(n\) grows.
Theorem 12. For any \(n\geq 2\), we have \[\mathcal{MI}^c(n)\subseteq \mathcal{MI}^c(n+1).\]
Proof. Let \((a,b)\in \mathcal{MI}^c(n)\). By Lemma 11, we have \(a<b\). If \(a+2\leq b\), then the result follows from Lemma 12 (2). On the other hand, if \(b=a+1\), then the result follows from Lemma 13. This concludes the proof. ◻
We shall construct graphs on the line \(\mathop{\mathrm{mult}}_{-1} P_G=\lceil n/2\rceil -1\).
For each \(r,s\geq 1\), let \(T_{r,s}\) and \(T_{r}\) denote the graphs where the vertex sets are \[V(T_{r,s}) = [r+s+2] \quad \text{and}\quad V(T_r)= [2r+5]\] and the edges sets are \[\begin{gather} E(T_{r,s}) = \{ \{1,2\}, \{1,i\}, \{2,j+r\} \mid 3\leq i \leq r+2 \text{ and } 3\leq j\leq s+2 \} \quad \text{and} \\ E(T_r) = \{ \{1,2\}, \{2,3\}, \{3,4\}, \{3,5\}, \{3,i\}, \{5,i+r\} \mid 6\leq i\leq r+5 \}. \end{gather}\]
Pictorially, \(T_{r,s}\) is a tree of diameter 3, while \(T_r\) is a tree of diameter 4. We illustrate these graphs with some pictures below.
A formula for the independence polynomial for a tree of diameter at most 4 has been obtained in [22], and thus both the multiplicity and independence number of such a graph are known. We record the formulae for our specially constructed graphs below.
Lemma 14 (). For each \(r,s\geq 1\), we have \[\mathop{\mathrm{mult}}_{-1} P_{T_{r,s}} =\min\{r,s\} \quad \text{and} \quad \alpha(T_{r,s})=r+s,\] and \[\mathop{\mathrm{mult}}_{-1} P_{T_r} =r +2 \quad \text{and} \quad \alpha(T_r)=2r+2.\]
We will also need the following lemma.
Lemma 15. Let \(n\geq 2\) be an integer and \((a,b)\in \mathcal{MI}^c(n)\) for some \(a\geq 0\). Then \((a+1,b+1)\in \mathcal{MI}^c(n+2)\).
Proof. Let \(G\) be a connected graph with \(n\) vertices that realizes the pair \((a,b)\), i.e., \(\mathop{\mathrm{mult}}_{-1} P_G=a\) and \(\alpha(G)=b\). The latter implies that there exists an independent set \(U\) of \(G\) of size \(b\). Note that \(U\) is also an independent set of \(G\sqcup K_1\). We then consider the graph \(\mathop{\mathrm{cone}}(G\sqcup K_1,U)\), a connected graph with \(n+2\) vertices by construction. It now suffices to show that \[\label{eq:a431-and-b431} \mathop{\mathrm{mult}}_{-1} P_{\mathop{\mathrm{cone}}(G\sqcup K_1,U)} = a+1 \quad \text{and} \quad \alpha(\mathop{\mathrm{cone}}(G\sqcup K_1,U)) = b+1.\tag{1}\]
Assume that \(b\geq a+2\). Then by Lemma 3, we have \[\mathop{\mathrm{mult}}_{-1} P_{G\sqcup K_1} = a+1 < b< b+1=\alpha(G\sqcup K_1).\] Thus (1 ) follows from Lemma 2.
Now we can assume that \(b=a+1\) since \(b>a\) by Lemma 11. By Lemmas 3 and 8, we have \[P_{G\sqcup K_1}(x) = (1+x)^{b}(1+(n-b+1)x).\] Thus by Lemma 2, we obtain \[P_{\mathop{\mathrm{cone}}(G\sqcup K_1,U)}(x)= (1+x)^{b}(1+(n-b+1)x) + x(1+x)^b = (1+x)^b(1+(n-b+2)x),\] which implies \(\alpha(\mathop{\mathrm{cone}}(G\sqcup K_1,U))=b+1\). On the other hand, since \[1+(n-b+2)(-1) = \alpha(G) -n-1 \leq -1,\] we have \(\mathop{\mathrm{mult}}_{-1} P_{\mathop{\mathrm{cone}}(G\sqcup K_1,U)} = b=a+1\). Thus (1 ) holds, as desired. ◻
We are now ready to give a lower bound for \(\mathcal{MI}^c(n)\).
Theorem 13. Let \(n\geq 2\) be an integer. If \(n\) is odd, then \[\label{eq:MI-c-odd} \{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a<b\leq n-2 \text{ and } a\leq \lceil n/2 \rceil-1 \} \setminus \{(\lceil n/2 \rceil-1,n-2)\}\cup \{(0,n-1)\}\subseteq \mathcal{MI}^c(n),\tag{2}\] and if \(n\) is even, then \[\label{eq:MI-c-even} \{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a<b\leq n-2 \text{ and } a\leq n/2 -1 \} \cup \{(0,n-1)\}\subseteq \mathcal{MI}^c(n).\tag{3}\]
Proof. Note that the results follow from Figure 7 if \(n\leq 8\). We now proceed by induction on \(n\).
Assume that \(n\geq 8\) is even. By induction, (3 ) holds for \(n-2\): \[\begin{align} \{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a<b\leq n-4 \text{ and } a\leq \lceil (n-2)/2 \rceil-1 \} \cup \{(0,n-3)\} \subseteq \mathcal{MI}^c(n-2). \end{align}\] Note that \(\lceil (n-2)/2 \rceil = n/2 -1\) since \(n\) is even. We can then rewrite the above as follows: \[\{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a<b\leq n-4 \text{ and } a\leq n/2 -2 \} \cup \{(0,n-3)\}\subseteq \mathcal{MI}^c(n-2).\] By Lemmas 12 (1) and 15 and Theorem 12, we have \[\begin{align} \mathcal{MI}^c(n) &\supseteq \{(a,b),(a,b+1), (a,b+2), (a+1,b+1)\in \mathbb{Z}_{\geq 0}^2\mid (a,b)\in \mathcal{MI}^c(n-2)\}\\ &\supseteq \{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a<b\leq n-2 \text{ and } a\leq n/2 -1 \} \cup \{(0,n-1)\}\setminus \{(n/2-1,n-2)\}. \end{align}\] On the other hand, the pair \((n/2-1,n-2)\) can be realized by the graph \(T_{n/2-1,n/2-1}\), a tree with \(n\) vertices, by Lemma 14. Thus (3 ) holds, as desired.
Now we can assume that \(n\geq 9\) is odd. By induction, (2 ) holds for \(n-2\): \[\begin{gather} \{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a<b\leq n-4 \text{ and } a\leq \lceil (n-2)/2 \rceil-1 \} \setminus \{(\lceil (n-2)/2 \rceil-1,n-4)\}\\ \cup \{(0,n-3)\}\subseteq \mathcal{MI}^c(n-2) \end{gather}\] Note that \(\lceil (n-2)/2 \rceil = (n-1)/2\) since \(n\) is odd. We can then rewrite the above as follows: \[\begin{gather} \{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a<b\leq n-4 \text{ and } a\leq (n-3)/2 \} \setminus \{((n-3)/2 ,n-4)\}\\ \cup \{(0,n-3)\}\subseteq \mathcal{MI}^c(n-2). \end{gather}\] Note that we have \(((n-3)/2,n-5)\in \mathcal{MI}^c(n-2)\) since \(n\geq 9\). By Lemmas 12 (1) and 15 and Theorem 12, we then have \[\begin{align} \mathcal{MI}^c(n) &\supseteq \{(a,b),(a,b+1), (a,b+2), (a+1,b+1)\in \mathbb{Z}_{\geq 0}^2\mid (a,b)\in \mathcal{MI}^c(n-2)\}\\ &\begin{multlined}[t] \supseteq \{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a<b\leq n-2 \text{ and } a\leq (n-1)/2 \} \cup \{(0,n-1)\}\\ \setminus \{((n-1)/2 ,n-2), ((n-3)/2 ,n-2), ((n-1)/2 ,n-3)\}. \end{multlined} \end{align}\] On the other hand, the pairs \(((n-3)/2 ,n-2)\) and \(((n-1)/2 ,n-3)\) can be realized by the trees \(T_{(n-3)/2,(n-1)/2}\) and \(T_{(n-5)/2}\), respectively, with both on \(n\) vertices, by Lemma 14. Thus (2 ) holds, as desired. ◻
In fact, the lower bound in Theorem 13 is indeed the whole set \(\mathcal{MI}^c(n)\) for \(2\leq n\leq 8\). We believe this to be always the case. It is straightforward to see that the equality reduces to the following question.
Question 14. Given a connected graph \(G\) on \(n\geq 2\) vertices. Is it true that \(\mathop{\mathrm{mult}}_{-1}P_G\leq \lceil n/2\rceil -1\)?
We fell short of determining \(\mathcal{MI}^c(n)\). Instead we will determine the realizable points along its boundary, which according to Lemma 11 is determined by the three lines \(a=0\), \(b=n-2\), and \(b=a+1\) in the plane \(\mathbb{Z}^2_{\geq 0}\). We start with the horizontal line \(b=n-2\).
Theorem 15. Let \(n\geq 2\) be an integer. Then \[\mathcal{MI}^c(n) \cap \{(a,n-2)\in \mathbb{Z}_{\geq 0}^2\} = \{ (a,n-2) \in \mathbb{Z}_{\geq 0}^2\mid 0\leq a\leq \lfloor n/2 \rfloor -1 \}.\]
Proof. \((\subseteq):\) Let \(G\) be a graph \(n\) vertices with \(\alpha(G)=n-2\). We can then set \(V(G)=[n]\) such that \([n-2]\) is an independent set of \(G\). We want to show that \(\mathop{\mathrm{mult}}_{-1}P_G \leq \lfloor n/2 \rfloor-1\). Set \[\begin{align} r&= |\{ i\in [n-2] \mid \text{i is adjacent to n-1, but not n} \}| &= |N_G(n-1)\setminus N_G(n)|,\\ s&= |\{ i\in [n-2] \mid \text{i is adjacent to n, but not n-1} \}|&=|N_G(n)\setminus N_G(n-1)|,\\ t&= |\{ i\in [n-2] \mid \text{i is adjacent to n-1 and n} \}|&=|N_G(n-1)\cap N_G(n)|. \end{align}\] In particular we have \(r+s+t=n-2\). Applying Lemma 1, we have \[\label{eq:ind-poly-alpha61n-2} P_G(x)= P_{G\setminus \{n\}} (x) + xP_{G\setminus N[n]}(x).\tag{4}\] We have two cases.
Case 1: Assume that \(\{n-1,n\}\notin E(G)\). Then \(G\setminus \{n\}\) is the disjoint union of the star graph \(S_{r+t+1}\) with \(s\) isolated vertices, and that \(G\setminus N[n]\) is the star graph \(S_{r+1}\). Thus (4 ) gives \[P_G(x)= (1+x)^s \left( (1+x)^{r+t} +x \right) + x\left((1+x)^{r}+x\right) = (1+x)^{n-2} + x(1+x)^r + x(1+x)^s +x^2.\] Note that \(n\geq 3\), as \(n=2\) would imply that \(G\) is the graph of two isolated vertices, a contradiction to the hypothesis that \(G\) is connected. Thus \[\mathop{\mathrm{mult}}_{-1}P_G = \begin{cases} 0 &\text{if r=s=0 or r,s>0},\\ 1 &\text{if exactly one between r and s is 0}. \end{cases}\] If \(n=3\), then \(G\) being connected forces \(r=s=0\) and \(t=1\). Then \(\mathop{\mathrm{mult}}_{-1}P_G=\mathop{\mathrm{mult}}_{-1}P_{S_3}=0 \leq \lfloor 3/2\rfloor -1\), as desired. On the other hand, if \(n\geq 4\), then \(\mathop{\mathrm{mult}}_{-1} P_G \leq 1 \leq \lfloor n/2\rfloor -1\), as desired.
Case 2: Assume that \(\{n-1,n\}\in E(G)\). Then \(G\setminus \{n\}\) is the disjoint union of the star graph \(S_{r+t+1}\) with \(s\) isolated vertices, and that \(G\setminus N[n]\) is the graph of \(r\) isolated vertices. Thus (4 ) gives \[P_G(x)= (1+x)^s \left( (1+x)^{r+t} +x \right) + x(1+x)^{r} = (1+x)^{n-2} + x(1+x)^r+x(1+x)^s.\] Thus \[\mathop{\mathrm{mult}}_{-1}P_G = \min \{r,s\}\leq \left\lfloor \frac{n-2}{2} \right\rfloor =\left\lfloor \frac{n}{2} \right\rfloor-1,\] as desired, where the inequality is due to the condition \(r+s+t=n-2\).
\((\supseteq):\) This follows from Theorem 13. ◻
All the possible points on the vertical line \(a=0\) can be realized.
Corollary 2. Let \(n\geq 2\) be an integer. Then \[\mathcal{MI}^c(n) \cap \{(0,b)\in \mathbb{Z}_{\geq 0}^2\} = \{ (0,b) \in \mathbb{Z}_{\geq 0}^2\mid 0<b\leq n -1 \}.\]
Proof. The inclusion \((\subseteq)\) is from Theorem 11, while \((\supseteq)\) follows from Theorem 13. ◻
The line \(b=a+1\) is a lot trickier. Intuitively, the points \((a,a+1)\) with low values of \(a\) can be realized. This is supported by Theorem 13. The question becomes how large \(a\) can be, in terms of a function in \(n\), provided that \((a,a+1)\) can be realized in \(\mathcal{MI}^c(n)\).
Proposition 16. For any \(n\geq 2\), if \((a,a+1)\) can be realized in \(\mathcal{MI}^c(n)\) for some integer \(a\), then \[a\leq n-\frac{1+\sqrt{8n-7}}{2},\] with equality implying that the graph that realizes \((a,a+1)\) is a tree.
Proof. Let \(G\) be a connected graph on \(n\) vertices with \(\mathop{\mathrm{mult}}_{-1}P_G=a\) and \(\alpha(G)=a+1\). Since \(G\) is connected, it has at least \(n-1\) edges. By Lemma 8, we have \[\binom{n-\alpha(G)+1}{2} \geq n-1.\] Solving this inequality, we obtain \[\text{either} \quad \alpha(G) \geq \frac{2n+1+\sqrt{8n-7}}{2} \quad \text{or} \quad \alpha(G) \leq \frac{2n+1-\sqrt{8n-7}}{2}.\] The former is not possible since it would imply that \(\alpha(G) \geq \frac{2n+1+\sqrt{8n-7}}{2} > n\). We thus obtain \[\alpha(G) \leq \frac{2n+1-\sqrt{8n-7}}{2}.\] Substituting \(\alpha(G)=a+1\), we obtain the desired result. ◻
Remark 17. Unfortunately, not all lattice points \((a,a+1)\) with \(a\leq n-\frac{1+\sqrt{8n-7}}{2}\) can be realized in \(\mathcal{MI}^c(n)\). Let \(n=\frac{k^2+7}{8}\) where \(k\) is an odd positive integer. We then have\[n-\frac{1+\sqrt{8n-7}}{2} = \frac{k^2-4k+3}{2}.\] Consider the point \[A_k=\left( \frac{k^2-4k+3}{2}, \frac{k^2-4k+5}{2}\right).\] By Proposition 16, if a connected graph on \(n=\frac{k^2+7}{8}\) vertices realizes \(A_k\), it must be a tree. Experiments show that \(A_3, A_5, A_7\) can be realized, while \(A_1, A_9, A_{11}\) cannot, a somewhat surprising observation.
All pairs that can be realized by connected graphs, without the restriction on the number of vertices, can be determined easily.
Corollary 3. We have \[\bigcup_{n=1}^\infty \mathcal{MI}^c(n) = \{(a,b) \in \mathbb{Z}_{\geq 0}^2\mid 0\leq a< b \} \cup \{(1,1)\}.\]
Proof. The containment \((\subseteq)\) follows from Lemma 11 and the fact that \(\mathcal{MI}^c( 1) = \{(1,1)\}\), while \((\supseteq)\) follows from Theorem 13. ◻
Finally, we compute \(\mathcal{MI}(n)\) for any \(n\geq 1\). Allowing disconnected graphs essentially means that the union operation can be used in graph construction.
Lemma 16. If \((a,b)\in \mathcal{MI}(n)\) for some integers \(a,b,n\), then \((a+1,b+1)\in \mathcal{MI}(n+1)\).
Proof. If \(G\) is a graph on \(n\) vertices with \(\mathop{\mathrm{mult}}_{-1}P_G=a\) and \(\alpha(G)=b\), then \(\mathop{\mathrm{mult}}_{-1}P_{G\sqcup K_1}=a+1\) and \(\alpha(G\sqcup K_1)=b+1\) by Lemma 3. The result then follows. ◻
Theorem 18. Let \(n\geq 1\) be an integer. We have \[\mathcal{MI}(n) = \{(a,b)\in \mathbb{Z}_{\geq 0}^2\mid 0\leq a< b \leq n-1 \} \cup \{(n,n)\}.\]
Proof. \((\subseteq):\) It is clear that \(0\leq \mathop{\mathrm{mult}}_{-1} P_G\leq \alpha(G) \leq n\) for any graph \(G\) on \(n\) vertices. However, note that either \(\mathop{\mathrm{mult}}_{-1}P_G= \alpha(G)\) or \(\alpha(G)=n\) implies that \(\mathop{\mathrm{mult}}_{-1}P_G= \alpha(G)=n\) by Lemma 4. The inclusion \((\subseteq)\) then follows.
\((\supseteq):\) It is straightforward that \(\mathcal{MI}(1)=\{(1,1)\}\) and \(\mathcal{MI}(2)=\{(0,1),(2,2)\}\). These settle the result in the cases \(n\in \{1,2\}\). By induction, we assume that \[\mathcal{MI}(n-1) = \{(a,b)\mid 0\leq a< b \leq n-2 \} \cup \{(n-1,n-1)\}\] for some \(n\geq 3\). Then by Lemma 16, we have \[\{(a,b)\mid 1\leq a< b \leq n-1 \} \cup \{(n,n)\} \subseteq \mathcal{MI}(n).\] It now suffices to realize the pairs \((0,b)\) where \(1\leq b\leq n-1\) with graphs on \(n\) vertices. If \(b=1\), then the complete graph \(K_n\) realizes \((0,b)=(0,1)\) by Lemma 5. If \(b=n-1\), then the star graph \(S_n\) realizes the pair \((0,b)=(0,n-1)\) by Lemma 6. Now we can assume that \(2\leq b\leq n-2\). Equivalently, we have \(b\geq 2\) and \(n-b\geq 2\). Then it is straightforward that the pair \((0,b)\) is realized by the graph \(S_{b}\sqcup K_{n-b}\) by Lemmas 3, 5, and 6. This concludes the proof. ◻
6 From spectral graph theory: multiplicity of line graph of forests↩︎
In this section, we examine the relationship between the independence polynomial of the line graph of a forest and two other polynomials associated to graphs, namely, characteristic polynomial and matching polynomial. We use these connections to investigate when \(-1\) is a root of the independence polynomial, beginning with some preliminary definitions.
Let \(G\) be a simple graph on the vertex set \(\{1, \dots, n\}\). The adjacency matrix of \(G\) is the \(n \times n\) symmetric matrix \(A(G) = [a_{ij}]\) where \[a_{ij} = \begin{cases} 1 & \text{if vertices } i \text{ and } j \text{ are adjacent,} \\ 0 & \text{otherwise.} \end{cases}\] By definition, \(a_{ii} = 0\) for all \(i \in \{1, \dots, n\}\), and \(a_{ij} = a_{ji}\) for all \(1 \leq i, j \leq n\). The characteristic polynomial of \(G\) is the polynomial \(\phi_G(x)=\det\,(xI-A(G))\), and its roots are the eigenvalues of \(G\).
A matching \(M\) in a graph \(G\) is a set of edges such that no two share a vertex in common. If \(|M|=k\), then \(M\) is called a \(k\)-matching. Let \(m_k(G)\) denote the number of \(k\)-matchings in \(G\), with the convention that \(m_0(G)=1\). The matching number of \(G\), denoted by \(\nu_G\), is the maximum \(k\) such that \(m_k(G)\neq 0\). The matching polynomial is defined by \[\mu_G(x)=\sum_{k=0}^{\nu_G}(-1)^k\, m_k(G)\, x^{n-2k}.\]
The line graph \(L(G)\) of a graph \(G\) is the graph whose vertices are the edges of \(G\), and where two vertices of \(L(G)\) are adjacent if and only if the corresponding edges in \(G\) share a common vertex. We denote by \(e_{i,j}\) the vertex in \(L(G)\) corresponding to the edge between vertices \(i\) and \(j\) in \(G\). It is easy to see that \(L(P_n)=P_{n-1}\) and \(L(C_n)=C_n\).
Line graphs of trees have a particularly simple structure. The following lemma provides a characterization of line graphs of trees in terms of block graphs.
Lemma 17 (). A graph is the line graph of a tree if and only if it is a connected block graph in which every cutpoint belongs to exactly two blocks.
The following classical result establishes a bridge between matchings in \(G\) and independent sets in \(L(G)\). For the sake of completion, we provide a self-contained proof.
Theorem 19. For any graph \(G\), \[P_{L(G)}(x)= \sum_{k\geq 0} m_k(G)\, x^k\]
Proof. By definition, an independent set of size \(k\) in \(L(G)\) is a set of \(k\) vertices of \(L(G)\) with no two of which are adjacent. Since the vertices of \(L(G)\) correspond to the edges of \(G\), two vertices in \(L(G)\) are adjacent if and only if the corresponding edges in \(G\) share an endpoint. Therefore, an independent set of size \(k\) in \(L(G)\) corresponds precisely to a matching of size \(k\) in \(G\). This completes the proof. ◻
Remark 20. Let \(Q_G(x):=\sum_{k\geq 0} m_k(G)\, x^k\). Then it is easy to see that \(\mu_G(x) = x^n\, Q_G(-x^{-2}).\) Thus, \[\mu_G(x)=x^n\, P_{L(G)} (-x^{-2}).\]
The matching polynomial of a graph encodes information about its matchings, while the characteristic polynomial of a graph captures its spectral properties. For general graphs these polynomials differ, but they coincide precisely when the graph has no cycles.
Theorem 21 (). For a graph \(G\), \(\phi_G(x)=\mu_G(x)\) if and only if \(G\) is a forest.
By Remark 20 and Theorem 21, it follows that for any forest \(F\) on \(n\) vertices, \[\label{eq:char61in} \phi_F(x) = x^n P_{L(F)} (-x^{-2}).\tag{5}\] Putting \(x=1\) and \(x=-1\) in 5 , we see that if either \(1\) or \(-1\) is an eigenvalue of \(F\), then \(P_{L(F)}(-1)=0\). Hence, \(-1\) is a root of the independence polynomial of \(L(F)\). We now compare the corresponding multiplicities. Since \(F\) is a forest, it is bipartite, and therefore its nonzero eigenvalues occur in pairs \(\pm\lambda\) with the same multiplicity. In particular, the multiplicities of \(1\) and \(-1\) as eigenvalues of \(F\) are equal. Moreover, the factor \(x^n\) in 5 is nonzero at \(x=1\) and at \(x=-1\). The change of variable \(t=-x^{-2}\) is locally invertible at both points, since \(\frac{d}{dx}(-x^{-2})=2x^{-3},\) is nonzero at \(x=1\) and at \(x=-1\). Therefore, the order of vanishing of \(P_{L(F)}(t)\) at \(t=-1\) is equal to the order of vanishing of \(\phi_F(x)\) at \(x=1\), and also to the order of vanishing of \(\phi_F(x)\) at \(x=-1\). Consequently, the multiplicity of \(-1\) as a root of \(P_{L(F)}\) is equal to the common multiplicity of \(1\) and \(-1\) as eigenvalues of \(F\).
Let the connected components of \(F\) be the trees \(T_1, \dots, T_r\). Since the characteristic polynomial of a disjoint union is the product of the characteristic polynomials of its components, we have \(\phi_F(x) = \prod_{i=1}^r \phi_{T_i}(x)\). Thus, \(\pm1\) is a root of \(\phi_{F}(x)\) if and only if it is a root of \(\phi_{T_i}(x)\) for some \(1 \leq i \leq r\).
Similarly, the connected components of \(L(F)\) are exactly the line graphs of the components of \(F\), namely \(L(T_1), \dots, L(T_r)\). It then follows that \(P_{L(F)}(x) = \prod_{i=1}^{r} P_{L(T_i)}(x)\). Consequently, \(\pm1\) is a root of \(P_{L(F)}(x)\) if and only if \(\pm1\) is a root of \(P_{L(T_i)}(x)\) for some \(1 \leq i \leq r\).
Our goal is to study the case when \(-1\) is a root of the independence polynomial of the line graph of a forest \(F\). By the preceding discussion, it suffices to consider the case where \(F\) is a tree and \(-1\) is its eigenvalue.
For trees, two characterizations of the multiplicity of \(-1\) as an eigenvalue are known in terms of the number of pendant vertices. Using these characterizations, we determine line graphs whose independence polynomials have \(-1\) as a root of a given multiplicity. Before proceeding, we introduce some terminology.
Let \(T\) be a tree on \(n\) vertices with \(p\) pendant vertices. A major vertex in \(T\) is a vertex that is adjacent to at least three other vertices. For any two vertices \(x\) and \(y\) in \(T\), the distance \(d(x,y)\) is defined as the length of the unique path between them.
In [33], Wang et. al.established an upper bound for \(\mathop{\mathrm{mult}}_{\lambda} \phi_T\) in terms of the number of pendant vertices as follows.
Theorem 22 (). Let \(T\) be a tree with \(p\) pendant vertices. Then \[\mathop{\mathrm{mult}}_{\lambda} \phi_T \leq p - 1.\]
In [34], the authors provide a complete characterization of the trees that attain this upper bound for \(\lambda=-1\).
Theorem 23 (). Let \(T\) be a tree with \(p \geq 2\) pendant vertices. Then \(\mathop{\mathrm{mult}}_{-1} \phi_T=p-1\) if and only if one of the following conditions holds.
\(T \cong P_n\) with \(n \equiv 2 \pmod 3\);
\(d(v, u) \equiv 2 \pmod 3\) for every pendant vertex \(v\) and major vertex \(u\) of \(T\).
We elucidate this through an example.
Example 3. Consider the tree \(T\) illustrated in Figure 11. This tree has five pendant vertices \(\{1, 11, 13, 15, 20\}\) and two major vertices \(\{3, 9\}\). Since \(T\) satisfies condition (ii) of Theorem 23, the multiplicity of the eigenvalue \(-1\) is \(\mathop{\mathrm{mult}}_{-1} \phi_T = 4\). Furthermore, Equation 5 implies that \(-1\) is also a root of the independence polynomial \(P_{L(T)}(x)\) with multiplicity four.
Direct computation yields the characteristic polynomial of \(T\): \[\phi_T(x) = (x-1)^4(x+1)^4(x^{12}-15x^{10}+83x^8-204x^6+202x^4-39x^2+1),\] and the independence polynomial of the line graph \(L(T)\): \[P_{L(T)}(x) = (x+1)^4(x^6+39x^5+202x^4+204x^3+83x^2+15x+1).\] It is easily verified that these polynomials satisfy the relationship \(\phi_T(x) = x^{20} P_{L(T)}(-x^{-2})\).
In [35], the authors characterize trees that have an eigenvalue \(\lambda\) with multiplicity two less than the number of pendant vertices. To provide this characterization, they recursively define two families of trees, \(\{\Gamma_i(\lambda)\}_{i\geq0}\) and \(\{\Gamma_i^2(\lambda)\}_{i\geq0}\). We define these families for the particular case \(\lambda=-1\), and for the sake of simplicity, we write \(\Gamma_i(-1)\) as \(\Gamma_i\) and \(\Gamma_i^2(-1)\) as \(\Gamma_i^2\). The first family \(\{\Gamma_j\}_{j\geq 0}\) of trees is defined as follows.
\(\Gamma_0:=\{P_n:n\equiv 2 \pmod 3\}.\)
\(\Gamma_1\) denotes the set of trees \(T\) containing a unique major vertex \(w_1\) such that the forest \(T-w_1\), obtained by deleting \(w_1\), is the union of at least three components from \(\Gamma_0\), where the neighbor of \(w_1\) in each component is a pendant vertex of that component.
For \(j \ge 2\), \(\Gamma_j\) consists of all trees \(T\) satisfying:
\(T\) has exactly \(j\) major vertices;
there exists a major vertex \(w_j\) of \(T\) such that \(T - w_j\) has exactly one component from \(\Gamma_{j-1}\) and all other components belong to \(\Gamma_0\);
the neighbor of \(w_j\) in each component of \(T - w_j\) is a pendant vertex of that component.
Using the family \(\{\Gamma_j\}\), we now define the second family \(\{\Gamma_j^2\}_{j\geq 0}\) of trees.
\(\Gamma_0^2:=\{P_n:n\equiv 1 \pmod 3\}.\)
\(\Gamma_1^2\) denotes the set of trees \(T\) with a unique major vertex \(w_1\) satisfying either of the following conditions:
\(T-w_1\) has exactly three components, all from \(\Gamma_0^2\) such that the neighbor of \(w_1\) in each component is a pendant vertex of that component.
\(T-w_1\) has exactly one component from \(\Gamma_0^2\) and all other components from \(\Gamma_0\) such that the neighbor of \(w_1\) in each component is a pendant vertex of that component.
\(\Gamma_2^2\) denotes the set of trees \(T\) with exactly two major vertices, and there is a major vertex \(w_2\) of \(T\) such that either of the following conditions holds:
\(T-w_2\) has exactly one component from \(\Gamma_1^2\) and all the other components from \(\Gamma_0\) such that the neighbor of \(w_2\) in each component is a pendant vertex of that component.
\(T-w_2\) has exactly one component, say \(T_1\), from \(\Gamma_1\) and all other components from \(\Gamma_0\), where the unique neighbor of \(w_2\) lying in \(T_1\) is not a pendant vertex of \(T_1\); other neighbors of \(w_2\) in each component are pendant vertices of those components.
For \(j \ge 3\), \(\Gamma_j^2\) consists of all trees \(T\) with exactly \(j\) major vertices, and there is a major vertex \(w_j\) such that one of the following conditions holds:
\(T-w_j\) has exactly one component from \(\Gamma_{j-1}^2\) and all other components from \(\Gamma_0\) such that the neighbor of \(w_j\) in each component is a pendant vertex of that component.
\(T-w_j\) has exactly one component, say \(T_1\), from \(\Gamma_{j-1}\) and all other components from \(\Gamma_0\), where the unique neighbor of \(w_j\) lying in \(T_1\) is not a pendant vertex of \(T_1\); other neighbors of \(w_j\) in each component are pendant vertices of those components.
\(T-w_j\) has exactly one component, say \(T_2\), from \(\Gamma_{j-1}\); exactly one component, say \(T_2\) from \(\Gamma_{0}^2\) and all other components from \(\Gamma_0\) such that the neighbor of \(w_j\) in each component is a pendant vertex of that component.
The following result from [35] provides a characterization of trees that have \(-1\) as an eigenvalue with a multiplicity exactly two less than the number of pendant vertices.
Theorem 24 (). Let \(T\) be a tree with \(p \geq 3\) pendant vertices and \(m\) major vertices, and suppose that \(-1\) is an eigenvalue of \(T\). Then \(\mathop{\mathrm{mult}}_{-1} \phi_T=p-2\) if and only if \(T \in \Gamma_k^2\).
Example 4. Consider the tree \(T\) in Figure 13. Observe that \(T \in \Gamma_3^2\) with \(w_3=10\), and that \(T\) has seven pendant vertices. By Theorem 24, we obtain \(\mathop{\mathrm{mult}}_{-1} \phi_T=5.\) By Equation 5 , it follows that \(\mathop{\mathrm{mult}}_{-1} P_{L(T)}=5\).
Direct computation yields the characteristic polynomial of \(T\): \[\phi_T(x)=x^2 (x - 1)^5 (x + 1)^5 (x^2 - 3)^2 (x^{12} - 16x^{10} + 93x^8 - 237x^6 + 249x^4 - 70x^2 + 5)\] and the independence polynomial of the line graph \(L(T)\): \[P_{L(T)}(x)=(3x + 1)^2 (x + 1)^5 (5x^6 + 70x^5 + 249x^4 + 237x^3 + 93x^2 + 16x + 1).\] It is easily verified that these polynomials satisfy the relationship \(\phi_T(x) = x^{28} P_{L(T)}(-x^{-2})\).
7 To commutative algebra: \(\mathfrak{a}\)-invariant and regularity↩︎
Let \(\mathbb{K}\) be a field, and \(A = \bigoplus_{i\geq 0}A_i\) be a standard graded \(\mathbb{K}\)-algebra. The Hilbert series of \(A\) is defined as \[H_A(t) = \sum_{i \geq 0} \mathrm{dim}_{\mathbb{K}}A_i~t^i.\] Let \(d\) be the krull dimension of \(A\), it is known that the Hilbert series of \(A\) can be written as a rational function \[H_A(t) = \frac{h_A(t)}{(1-t)^d},\] for a unique integer polynomial \(h_A(t)\) with \(h_A(1)\neq 0\). The polynomial \(h_A(t)\) is known as the \(h\)-polynomial of \(A\), and the difference between the degree of \(h\)-polynomial and the dimension of \(A\) (i.e. \(\mathrm{deg}~h_A(t) - \mathrm{dim}~A\)) is known to be the \(\mathfrak{a}\)-invariant of \(A\), denoted by \(\mathfrak{a}(A)\).
Throughout this section let \(R = \mathbb{K}[x_1,\ldots,x_n]\) denote the standard graded polynomial ring in \(n\) variables over the field \(\mathbb{K}\). Let \(G\) be a finite simple graph, then one can associate a quadratic square-free monomial ideal \(I(G)\) to \(G\), known as the edge ideal of \(G\), as following: \[I(G) = (x_ix_j \mid \{i,j\} \in E(G)) \subseteq R.\]
By [36], one has \[\label{h-degree95reg95ineq} \mathrm{deg}~h_{R/I(G)}(t) - \operatorname{reg}(R/I(G)) \leq \mathrm{dim}(R/I(G)) - \mathrm{depth}(R/I(G)).\tag{6}\]
Since, \(\mathrm{deg}~h_{R/I(G)}(t)= \mathfrak{a}(R/I(G)) + \mathrm{dim}(R/I(G))\), we have \[\operatorname{reg}(R/I(G)) \geq \mathfrak{a}(R/I(G)) + \mathrm{depth}(R/I(G)).\]
Furthermore, if \(I(G)\) is a Cohen–Macaulay ideal [37] or \(I(G)\) has a pure resolution [38], then equality holds in (6 ). In particular, if \(I(G)\) is a Cohen–Macaulay ideal, then \[\operatorname{reg}(R/I(G)) = \mathfrak{a}(R/I(G)) + \mathrm{dim}(R/I(G))\]
For a graph \(G\), it is known that the independence number \(\alpha(G)\) is equal to the Krull dimension of \(R/I(G)\) (e.g., see [22]). Also, by [22], we have \[\mathfrak{a}(R/I(G)) + \mathrm{dim}(R/I(G)) = \mathrm{deg}~h_{R/I(G)}(t) = \alpha(G)- \mathop{\mathrm{mult}}_{-1}P_G.\] Thus, one can observe that \(\mathfrak{a}(R/I(G)) = - \mathop{\mathrm{mult}}_{-1}P_G.\) Using this correspondence, our results from previous sections can be translated directly into interesting algebraic results.
Our first algebraic result translates Theorem 5, concerning the vanishing of the \(\mathfrak{a}\)-invariant of the graded algebra \(R/I(G)\) associated with pseudo-forests.
Theorem 25. Let \(G\) be a pseudo-forest and \(v_1,\dots, v_t\) a maximal support sequence of \(G\) for some integer \(t\). Let \(H = G \setminus \cup_{i=1}^t N_G[v_i]\). Then the \(\mathfrak{a}\)-invariant of \(R/I(G)\) vanishes if and only if \(H\) has no isolated vertex.
The next result translates Theorem 7, which provides a structural characterization of trees for which the \(\mathfrak{a}\)-invariant vanishes.
Theorem 26. Let \(T\) denote a tree. The \(\mathfrak{a}\)-invariant of \(R/I(T)\) is non-zero if and only if \(T\) is isomorphic to a grafting on some other tree \(T'\).
As a consequence of the previous results, we obtain families of graphs for which the Castelnuovo–Mumford regularity of \(R/I(G)\) is bounded below by the depth of \(R/I(G)\). Note that, in general, there is no direct relationship between \(\operatorname{reg}(R/I(G))\) and \(\operatorname{depth}(R/I(G))\), even when \(G\) is a tree. In fact, for trees, the depth can exceed the regularity by an arbitrarily large amount.
To see this, let \(P_n\) denote the path on \(n\) vertices and consider the whiskered graph \(G=\mathcal{W}(P_n)\). By Lemma 10, we have \[\dim(R/I(G))=\alpha(G)=n.\] Since the whiskering of any graph is Cohen–Macaulay (see [39]), it follows that \[\operatorname{depth}(R/I(G))=\dim(R/I(G))=n.\] On the other hand, by [40], \[\operatorname{reg}(R/I(G) = \left\lfloor \frac{n+1}{2}\right\rfloor.\] Therefore, \[\operatorname{depth}(R/I(G)) - \operatorname{reg}(R/I(G)) = n-\left\lfloor \frac{n+1}{2}\right\rfloor,\] which grows arbitrarily large as \(n\) increases. Consequently, even within the class of trees, the depth of \(R/I(G)\) can be substantially larger than its Castelnuovo–Mumford regularity.
The following result provides nontrivial families of graphs for which the inequality goes in the opposite direction, namely, \(\operatorname{reg}(R/I(G)) \geq \operatorname{depth}(R/I(G)).\)
Corollary 4. Let \(G\) be a graph. Then \[\operatorname{reg}(R/I(G)) \geq \mathrm{depth}(R/I(G))\] in each of the following cases:
\(G\) is a pseudo-forest admitting a maximal support sequence \(v_1,\dots,v_t\) such that the graph \(G \setminus \cup_{i=1}^t N_G[v_i]\) has no isolated vertex;
\(G\) is a tree that is not a grafting on another tree.
The following result provides lower bounds for the \(\mathfrak{a}\)-invariant and the Castelnuovo–Mumford regularity of connected graphs whose edge ideals satisfy \(\dim(R/I(G)) = n-2\). These bounds are obtained as a consequence of Theorem 15 and depend only on the number of vertices of \(G\).
Theorem 27. Let \(G\) be a connected graph on \(n \geq 2\) vertices such that \(\dim(R/I(G)) = n-2\). Then \[\mathfrak{a}(G) \geq 1-\left\lfloor \frac{n}{2}\right\rfloor,\] and if \(I(G)\) is Cohen–Macaulay or admits a pure resolution, \[\operatorname{reg}(R/I(G)) \geq \left\lceil \frac{n}{2}\right\rceil -1.\]
The following result is immediate from the correspondence between the \(\mathfrak{a}\)-invariant and multiplicity of graph, dimension and the independence number, and the definitions of the sets \(\mathcal{MI}(n)\) and \(\mathcal{MI}^c(n)\).
Theorem 28. A lattice point \(p\) in \(\mathbb{Z}^2\) can be realized as a pair \((\mathfrak{a}(R/I(G)), \mathrm{dim}~R/I(G))\) for some graph \(G\) on \(n\) vertices if and only if \(p\) belongs to the reflection of the set \(\mathcal{MI}(n)\) along ordinate axis, and can be realized as a pair \((\mathfrak{a}(R/I(G)), \mathrm{dim}~R/I(G))\) for some connected graph \(G\) on \(n\) vertices if and only if \(p\) belongs to the reflection of the set \(\mathcal{MI}^c(n)\) along ordinate axis.
Now, from our study of the sets \(\mathcal{MI}(n)\) and \(\mathcal{MI}^c(n)\), we can classify the lattice points in \(\mathbb{Z}^2\) that can be realized as pairs consisting of the \(\mathfrak{a}\)-invariant and the dimension of the algebra \(R/I(G)\) for a graph \(G\) on \(n\) vertices. The following result follows from the Theorem 18.
Theorem 29. Let \(n\) be a fixed positive integer. Let \(p\) be a lattice point in \(\mathbb{Z}^2\). Then \(p = (\mathfrak{a}(R/I(G)), \mathrm{dim}~R/I(G))\) for some graph \(G\) on \(n\) vertices if and only if \[p \in \{(a,b) \in Q_2 \cap \mathbb{Z}^2 \mid 0 \leq -a < b \leq n-1\} \cup \{(-n,n)\},\] where \(Q_2\) denotes the upper-left quadrant of the Euclidean plane.
As we do not know the set \(\mathcal{MI}^c(n)\) completely, we can not completely classify the lattice points in \(\mathbb{Z}^2\) that can be realized as pairs consisting of the \(\mathfrak{a}\)-invariant and the dimension of the algebra \(R/I(G)\) for a connected graph \(G\) on \(n\) vertices. However, when we do not have any restriction on number of vertices, we can completely classify the lattice points in \(\mathbb{Z}^2\) that can be realized as pairs consisting of the \(\mathfrak{a}\)-invariant and the dimension of the algebra \(R/I(G)\) for some connected graph \(G\). The following result follows from the Theorems 3 and 18.
Theorem 30. Let \(p\) be a lattice point in \(\mathbb{Z}^2\). Then
\(p = (\mathfrak{a}(R/I(G)), \mathrm{dim}~R/I(G))\) for some graph \(G\) if and only if \[p \in \{(a,b) \in Q_2 \cap \mathbb{Z}^2 \mid 0 \leq -a \leq b\}\setminus \{(0,0)\}.\]
\(p = (\mathfrak{a}(R/I(G)), \mathrm{dim}~R/I(G))\) for some connected graph \(G\) if and only if \[p \in \{(a,b) \in Q_2 \cap \mathbb{Z}^2 \mid 0 \leq -a < b\} \cup \{(-1,1)\}.\]