| Izvestiya: Mathematics |
|
|
|
|
|
On stability of weighted spanning tree degree enumerators P. K. Prozorova, D. D. Cherkashinb a Saint Petersburg State University b Institute of Mathematics and Informatics, Bulgarian Academy of Sciences
Bibliographic databases:
    § 1. IntroductionLet
$$
\begin{equation*}
\mathbb{H}:=\{ z \in\mathbb{C}\mid \operatorname{Im}(z)>0\}
\end{equation*}
\notag
$$
be the upper complex half-plane. A polynomial $P(x_1,x_2, \dots,x_n)$ with complex coefficients is called stable if $P(z_1,z_2, \dots, z_n)\neq 0$ for all $z_1,z_2,\dots, z_n \in \mathbb{H}$; it is called real stable if, in addition, all the coefficients of $P$ are real. Clearly, any non-zero polynomial
$$
\begin{equation*}
a_1x_1+a_2x_2+\dots+a_nx_n, \qquad a_i \in \mathbb{R}_+,
\end{equation*}
\notag
$$
is real stable, and it is obvious that the product of two (real) stable polynomials is also a (real) stable polynomial. The following result is well known (see, for example, [2]). Proposition 1. Let $P(x_1,x_2, \dots, x_n)$ be a stable polynomial. Then the following polynomials are also stable (or vanish identically): (i) $x_1^{d_1}P(-1/x_1, x_2, \dots, x_n\bigr)$, where $d_1$ is the degree of $P$ on the variable $x_1$; (ii) $\partial P(x_1,x_2, \dots, x_n)/\partial x_1$; (iii) $Q(x_1,x_2, \dots, x_{n-1}) := P(x_1,x_2, \dots, x_{n-1},a)$ for any real $a$. Real stability of a polynomial with combinatorially meaningful coefficients is mainly used for delivering inequalities on these coefficients. For more on stable polynomials and their applications, see the surveys [2], [3] (and also the comments in §§ 1 and 4 of [1]). Let $G=(V, E)$ be a finite simple connected undirected graph, $|V|=n$, $|E|=k$. Let $N_G(v)=\{u\in V\colon vu\in E\}$ be the neighbourhood of vertex $v$, and $\deg_G(v)$ be the degree of a vertex $v$ in the graph $G$. Given a subset of vertices $U \subset V$, the induced subgraph $G[U]$ is defined as the graph whose vertices are elements of $U$, and whose edges are the edges of the graph $G$ with both end-points in $U$. Let $\mathcal{S}(G)$ be the set of all spanning trees of a graph $G$. By $K_n$ we denote the complete $n$-vertex graph. A biconnected graph is a connected graph that remains connected with removal of any vertex (and all the incident edges) from the graph. We enumerate the edges of $G$ with numbers from $1$ to $k$, and, with each edge, we associate the variable $x_i$, $i=1,\dots,k$. The edge spanning polynomial of a graph $G$ is defined by
$$
\begin{equation*}
Q_G(x_1,x_2, \dots, x_k )=\sum_{T\in \mathcal{S}(G)}\prod_{j \in E(T)}x_j.
\end{equation*}
\notag
$$
According to [4], the polynomial $Q_G$ is real stable for any finite connected simple graph $G$ containing at least two vertices. Let us enumerate the vertices from $1$ to $n$ by assigning the variables $x_1,\dots,x_n$ to these vertices. The vertex spanning polynomial is defined by
$$
\begin{equation*}
P_G(x_1, x_2, \dots, x_n)=\sum_{T \in \mathcal{S}(G)} \prod_{v \in V}x_v^{\deg_T(v)-1}.
\end{equation*}
\notag
$$
This polynomial is not always real stable. We say that a graph $G$ is stable if the polynomial $P_G$ is real stable. A graph is said to be distance-hereditary if, for any connected induced subgraph, the distance between any two vertices in the subgraph is equal to that between these vertices in the original graph (for more details on distance-hereditary graphs, see § 2). In [1], it was shown that these classes coincide. Theorem 1 (see [1]). A finite simple connected graph $G$ is stable if and only if it is distance-hereditary. The paper [1] also gives a combinatorial motivation and applications of Theorem 1, and formulates some related open questions. In the present paper, we solve one of these questions: we obtain a classification of stable weighted graphs. Without loss of generality we may assume that the weight function $w$ does not vanish (such edges can be removed). Let the degree of a vertex $v$ in a weighted graph $(G,w)$ coincide with the degree of $v$ in $G$. The weighted vertex spanning polynomial of a graph $G$ with weight function $w$ from $E(G)$ to $\mathbb{C}$ is defined by
$$
\begin{equation*}
P_{G,w}(x_1, x_2, \dots, x_n)= \sum_{T \in \mathcal{S}(G)} \prod_{e \in T}w(e) \prod_{v \in V} x_v^{\deg_T(v)-1}.
\end{equation*}
\notag
$$
A weighted graph $(G,w)$ will be called stable if so is the polynomial $P_{G,w}$ (with complex coefficients). The next lemma shows that the case of arbitrary weights can be elementarily reduced to that of real and positive weights. Lemma 1. If a biconnected weighted graph $(G,w)$ is stable, then $w$ has the same argument on all edges of $G$. Proof. Suppose the contrary. Then there are two edges in the graph on which $w$ has different arguments. By connectedness, there are two edges ($vu_1$ and $vu_2$, say) with common end-point on which $w$ assumes different arguments. Substituting $x_v=0$, we obtain
$$
\begin{equation*}
P_G(x_1, \dots, x_n) = P_{G \setminus v} (x_1, \dots, x_n) \cdot \biggl(\sum_{t \in N(v)} w(v,t)x_t\biggr).
\end{equation*}
\notag
$$
The graph $G$ is biconnected, and hence $G \setminus v$ is connected. Hence each of the factors is not identically zero, and so they are both stable. By Proposition 1, (iii), the second polynomial remains stable if all the variables except $x_{u_1}$ and $x_{u_2}$ are replaced by zeros. However, this contradicts the fact that the polynomial $ax_{u_1} + \,bx_{u_2}$ is stable only if the arguments of $a$ and $b$ are equal. This proves the lemma. So, the argument of $w$ is constant on each biconnected component, (because by Lemma 5 the biconnected components are weight-stable themselves), and the componentwise multiplication by complex numbers does not change the stability of the graph (see Lemma 3). We also note that the proofs of Lemma 5 and 3 are self-contained and never use the fact that the coefficients are real. So, it suffices to classify the graphs with positive weights (an arbitrary weighted graph is stable if and only if it is obtained by multiplications by complex numbers in the biconnected components of a stable weighted graph with positive weights). In what follows, we assume that all the graphs are weighted, and the weights are positive, unless otherwise specified. The following theorem gives an explicit (polynomial time checkable) characterization of stable weighted graphs. Theorem 2. The class of stable connected weighted graphs with positive weight function $w$ coincides with the class of graphs obtained from a one-vertex graph by weight-preserving copying of vertices (with or without adding an edge of an arbitrary positive weight between the copies), by joining two stable weighted graphs at a vertex, and by multiplying by a positive number the weights of all edges incident to the same vertex. Theorem 2 can also be applied to multigraphs — to this end, it suffices to consider multiple edges as a single edge whose weight is equal to the sum of the original weights. The method of the proof of Theorem 1 cannot be directly applied to weighted graphs (or multigraphs). The key new idea in the proof is to strengthen the (necessity) part of the theorem to Proposition 2. Note that the class of stable weighted graphs cannot be reduced to the class of stable graphs by merely rescaling on vertices. An illustrative example is a complete graph on four vertices, whose five edges are of unit weight, and the sixth edge has weight 2. Structure of the paperIn § 2, we give equivalent definitions of distance-hereditary graphs, of which some will be used. The main theorem is proved in § 3. The relation between the resulting polynomial definition of a distance-hereditary weighted graph and other definitions is discussed in § 4. Summary and conclusions are given in § 5. § 2. Distance-hereditary graphsRecall that a distance-hereditary graph is a connected graph in which any connected induced subgraph preserves the distance between any two vertices. More details about distance-hereditary graphs can be found, for example, in the paper [5] and the book [6]. In particular, this book gives the following equivalent definitions of the class of distance-hereditary graphs: (i) these are the graphs such that any induced path is a shortest path; (ii) these are the graphs such that any cycle of length at least $5$ has two or more diagonals and any cycle of length $5$ has at least one pair of intersecting diagonals; (iii) these are the graphs in which any cycle of length $5$ or more has at least one pair of intersecting diagonals; (iv) these are the graphs in which, for any four vertices $u$, $v$, $w$ and $x$, at least two of the three sums of distances $d(u,v)+d(w,x)$, $d(u,w)+d(v,x)$ and $d(u,x)+d(v,w)$ are equal; (v) these are еру graphs without the following induced subgraphs: a cycle of $\geqslant 5$, a gem, a house, or a domino (see Fig. 1); (vi) these are the graphs that can be created from a single vertex using a sequence of the following three operations:
Note that the proof of Theorem 1 relies on the equivalence of definitions (v) and (vi). The proof of Theorem 2 also uses definitions (v) and (vi), as well as the idea underlying definition (iv). Another algebraic definition appeared later in [7]. We will discuss this definition in detail in § 4. § 3. Proof of Theorem 2Recall that all the graphs considered here are assumed to be weighted with positive weights. 3.1. The constructed weighted graphs are stableThe following lemmas are weighted generalizations of the lemmas from [1]. Lemmas 2, 3, and 4 ensure the preservation of stability for copying, gluing, and multiplication operations, respectively. Lemma 2 (on copying). Let $(G,w)$ be an $n$ vertex weighted graph. Consider the weighted graph $(G_1,w_1)$ obtained from $(G,w)$ by adding a vertex $v_{n+1}$, connecting it to the vertices from $N(v_n)$ by edges equal in weight to the edges from $v_n$, and to the vertex $v_n$ by an edge of weight $p \geqslant 0$ (the case $p=0$ corresponds to the absence of this edge). Then Proof. The argument is similar to that in the case of unweighted graphs. Indeed, note that any tree in the graph $G$ is as follows: some forest is taken on all vertices, except $v_n$, such that each component has at least one vertex from $N_G(v_n)$, and then the vertex $v_n$ is connected to exactly one vertex from each component. We denote by $\mathcal{L}$ the set of all such forests, and by $t(K)$, the number of connected components in the forest $K$; let $A_1, A_2, \dots, A_t$ be the intersections of the set $N_G(v_n)$ with the connected components of the forest $K$. Let
$$
\begin{equation*}
W(K) = \prod_{i=1}^{n-1}x_i^{-1}\prod_{uv \in K}w(uv)x_ux_v.
\end{equation*}
\notag
$$
By the above
$$
\begin{equation*}
P_{G,w}(x_1, x_2, \dots, x_n) = \sum_{K \in \mathcal{L}} \biggl(W(K) x_n^{t(K)-1} \prod_{i=1}^{t(K)}\biggl(\sum_{v \in A_i}w(v_nv)x_v\biggr)\biggr).
\end{equation*}
\notag
$$
All the trees in the graph $G_1$ break out into the class $\mathcal{S}_1$ of trees that do not contain the edge $v_nv_{n+1}$ and r into the class $\mathcal{S}_2$ of trees that contain this edge. We have
$$
\begin{equation*}
\begin{aligned} \, &P_{G_1,w_1}(x_1, \dots, x_{n+1})=\sum_{T \in \mathcal{S}(G)} \prod_{e \in T}w(e) \prod_{v \in V} x_v^{\deg_T(v)-1} \\ &\qquad=\sum_{T \in \mathcal{S}_1} \prod_{e \in T}w(e) \prod_{v \in V} x_v^{\deg_T(v)-1}+\sum_{T \in \mathcal{S}_2} \prod_{e \in T}w(e) \prod_{v \in V} x_v^{\deg_T(v)-1} \\ &\qquad=P_1(x_1, \dots, x_{n+1})+P_2(x_1, \dots, x_{n+1}). \end{aligned}
\end{equation*}
\notag
$$
The trees in $\mathcal{S}_1$ are as follows. As in the original graph, we consider a forest $K$ that contains all the vertices except $v_n$, $v_{n+1}$, and such that each of its components contains at least one vertex of $N_G(v_n)$; we then connect one of the components to both $v_n$ and $v_{n+1}$, and connect each of the remaining $t(K)-1$ components to exactly one of these vertices. Note that, from the viewpoint of the weight of the tree, it does not matter to which of the vertices $v_n$, $v_{n+1}$ the subsequent component is connected, because, by construction, $w(v_nv)=w_1(v_nv)=w_1(v_{n+1}v)$ for any vertex $v \in N(v_n)$. So, we have
$$
\begin{equation*}
\begin{aligned} \, &P_1(x_1, \dots, x_{n+1}) \\ &=\sum_{K \in \mathcal{L}}\biggl(W(K)\sum_{i=1}^{t(K)} \biggl(\biggl(\sum_{v \in A_i} w(v_nv)x_v\biggr)^2 \prod_{\substack{j=1\\ j \neq i}}^n \biggl(\sum_{v \in A_j}w(v_nv)x_v\biggr)(x_n+ x_{n+1})^{t(K)-1}\biggr)\biggr) \\ &=\sum_{K \in \mathcal{L}}\biggl(W(K)\sum_{i=1}^{t(K)} \biggl(\biggl(\sum_{v \in A_v} w(v_nv)x_v\biggr) \prod_{j=1}^n\biggl(\sum_{v \in A_j}w(v_nv)x_v\biggr)(x_n+ x_{n+1})^{t(K)-1}\biggr)\biggr) \\ &=\biggl(\sum_{v \in N_G(v_n)}w(v_nv)x_v\biggr) \cdot\sum_{K \in \mathcal{L}} \biggl(W(K)\prod_{j=1}^n\biggl(\sum_{v \in A_j}w(v_nv)x_v\biggr) (x_n+ x_{n+1})^{t(K)-1}\biggr). \end{aligned}
\end{equation*}
\notag
$$
Now we can see that the second factor is $P_{G,w}(x_1, \dots, x_n+x_{n+1})$.
The trees from $\mathcal{S}_2$ are as follows: we again take a forest $K$ with the same conditions, connect each component to exactly one of the vertices $v_n$ and $v_{n+1}$, and connect $v_n$ and $v_{n+1}$. As above, the weight of the tree is independent of the particular vertex $v_n$, $v_{n+1}$ to which the components are connected. So, we have
$$
\begin{equation*}
\begin{aligned} \, P_2(x_1, \dots, x_{n+1}) &=p\sum_{K \in \mathcal{L}} \biggl(W(K)\prod_{i=1}^{t(K)} \biggl(\sum_{v \in A_i} w(v_nv)x_v \biggr) ( x_n+x_{n+1})^{t(K)}\biggr) \\ &= p(x_n+x_{n+1}) \cdot P_{G,w}(x_1, x_2, \dots, x_n+x_{n+1}). \end{aligned}
\end{equation*}
\notag
$$
Note that the factor $p$ multiplying the sum is taken from the edge $v_nv_{n+1}$ under consideration, and the factors $x_n$ and $x_{n+1}$ are cancelled with $-1$ in the degrees of the variables. As a result, we have
$$
\begin{equation*}
\begin{aligned} \, &P_{G_1,w_1}(x_1, \dots, x_{n+1}) =P_1(x_1, \dots, x_{n+1})+ P_2(x_1, \dots, x_{n+1}) \\ &\qquad=P_{G,w}(x_1, \dots, x_n + x_{n+1}) \cdot \biggl(\sum_{v \in N(v_n)}w(v_nv)x_v \biggr) \\ &\qquad\qquad+ P_{G,w}(x_1, \dots, x_n + x_{n+1}) \cdot (px_n +px_{n+1}) \\ &\qquad=P_{G,w} (x_1, \dots, x_n + x_{n+1}) \cdot\biggl(\sum_{v \in N(v_n)}w(v_nv)x_v +p(x_n + x_{n+1}) \biggr), \end{aligned}
\end{equation*}
\notag
$$
proving Lemma 2. Lemma 3 (on articulation points). Let $G$ be a connected weighted graph $G$ with an articulation point $v$, and let the set of vertices of graph $G$ decompose, after removing $v$, into connected components with vertex sets $V_1,V_2, \dots, V_s$. We set $G_i = G[V_i \cup \{v\}]$. Then where the variables corresponding to the vertices belonging to $G_i$ are substituted to $P_{G_i}$. Proof. Obviously, each spanning tree in the graph $G$ uniquely corresponds to the set of spanning trees in $\{G_i\}$, and the degree of a vertex $v$ is exactly the sum of its degrees in the spanning trees $G_i$, which corresponds to multiplication of polynomials. This proves the lemma. Lemma 4 (on multiplication). Let $P_{G,w}$ be the vertex spanning enumerator of a weighted graph $G$. Then the multiplication of the weights of all edges incident to some vertex $v$ by a real $c>0$ does not change the weighted stability of $G$. Proof. The new and old polynomials are either both stable or ubstable, since the multiplication corresponds to replacing the variable $x_v$ by $cx_v$ in $v$, and $cx_v\in \mathbb{H}$ if and only if $x_v\in \mathbb{H}$. This proves the lemma. The definition of the neighbourhood of a vertex in a weighted graph $(G,w)$ is inherited from $G$. A pair of vertices $x_1$ and $x_2$ is called contractible if their neighbourhoods in the graph $G$ coincide (possibly modulo $x_1$ and $x_2$), and the ratio $w(vx_1)/w(vx_2)$ is the same for all vertices $v$ connected to $x_1$ and $x_2$. Note that the multiplication of the weights of all edges incident to a vertex by a positive constant does not change the set of contractible pairs of the graph. In the proof, we will often use this property and apply Lemma 4. 3.2. The induction base for four verticesAny four-vertex biconnected graph is either a complete graph $K_4$, a cycle $C_4$, or a cycle with diagonal $C_4^+$. The case of $C_4$Let us show that, in a stable $C_4$, we can make all weights equal by using some multiplication operations. By applying Lemma 4 at the vertices $1$, $2$ and $3$, we can make sure that the weight of each edge, except one, is 1. We need to show that the last edge ($v_4v_1$, say) also has weight $1$. In this case, our polynomial has the form
$$
\begin{equation*}
P_{C_4,w} = x_2x_3+w(v_1v_4)\cdot (x_1x_2+x_3x_4+x_1x_4).
\end{equation*}
\notag
$$
Let $w(v_1v_4)=1/t$. Then
$$
\begin{equation*}
P_{C_4,w} = \frac{1}{t}(tx_2x_3+x_1x_2+x_3x_4+x_1x_4).
\end{equation*}
\notag
$$
For $t>1$, consider the substitution $x_3=x_4=1$. We have This polynomial has the root
$$
\begin{equation*}
x_1=i, \qquad x_2=\frac{-(1+i)(1-ti)}{t^2+1}=\frac{-(t+1)+(t-1)i}{t^2+1},
\end{equation*}
\notag
$$
which contradicts stability. The second case ($t<1$) is dealt with similarly. Hence $t=1$, the result required. The case of $K_4$By a multiplication at the vertices $1$, $2$, and $3$, we can make sure that the edges from the vertex $4$ are of weight 1. By Lemma 4, these operations do not affect the stability property of the graph. We set $e_1 = w(2,3)$, $e_2 = w(1,3)$, $e_3 = w(1,2)$. In the new notation, $P_{K_4,w}$ has the form
$$
\begin{equation*}
\begin{aligned} \, &x_4^2+x_4(x_1(e_2+e_3)+x_2(e_1+e_3)+x_3(e_1+e_2)) \\ &\qquad+ (x_1+x_2+x_3)(x_1e_2e_3+x_2e_1e_3+x_3e_1e_2). \end{aligned}
\end{equation*}
\notag
$$
This expression is quadratic with respect to the variable $x_4$, and hence, by Proposition 1, (iii), for any real substitution $x_1$, $x_2$, $x_3$, the discriminant $D$ of the corresponding quadratic trinomial is $\geqslant 0$. For all real $x_1$, $x_2$, $x_3$,
$$
\begin{equation*}
\begin{aligned} \, 0 \leqslant D &= (x_1(e_2+e_3)+x_2(e_1+e_3)+x_3(e_1+e_2))^2 \\ &\qquad-4(x_1+x_2+x_3)(x_1e_2e_3+x_2e_1e_3+x_3e_1e_2) \\ &=x_1^2(e_2-e_3)^2+x_2^2(e_3-e_1)^2+x_3^2(e_1-e_2)^2-2x_1x_2(e_2-e_3)(e_3-e_1) \\ &\qquad-2x_2x_3(e_3-e_1)(e_1-e_2)-2x_3x_1(e_1-e_2)(e_2-e_3). \end{aligned}
\end{equation*}
\notag
$$
If any two variables of $e_1$, $e_2$, $e_3$ are different, we can substitute
$$
\begin{equation*}
x_1=\frac{1}{e_2-e_3},\qquad x_2=\frac{1}{e_3-e_1},\qquad x_3=\frac{1}{e_1-e_2},
\end{equation*}
\notag
$$
which gives $D =-3$. This contradicts the non-negativity of the discriminant. So, among the three values $e_1$, $e_2$, $e_3$ there are two equal ones. Hence some two products of opposite edges are equal. This proves the required result for $K_4$. The case of $C_4^+$This case is similar to the previous one if we substitute $e_1 = 0$. Moreover, in this case we have $e_2=e_3$, since otherwise $G$ is a triangle with pendant edge, which is not biconnected. Thus, one of the contractible pairs in $C_4^+$ is a pair not connected by an edge. 3.3. Any stable weighted graph can be constructed by operations from Theorem 2The induced weighted subgraph $G[U]$ is defined similarly to the unweighted case with preservation of weights. Lemma 5. Let $G = (V,E)$ be a stable connected weighted graph and let $U\subset V$ be such that the weighted graph $G[U]$ is connected. Then $G[U]$ is also stable qua weighted graph. Proof. Let us start with the case $|V\setminus U|=1$, say, $V = U \sqcup \{n\}$ and $U=\{1,\dots,n-1\}$. Then $Q(x_1,\dots,x_{n-1}):=P_{G}(x_1,\dots,x_{n-1},0)$ is either identically zero or a stable polynomial according to assertion (iii) of Proposition 1. Note that $Q$ is the sum of the monomials of $P_G$ corresponding to the spanning trees of the graph $G$ in which the degree of the vertex $n$ is 1. Each such a tree is obtained by gluing together a leaf tree in the graph $G[U]$ and an edge from $n$ to some neighbour of $n$. This corresponds to the equality of the polynomials Since $G[U]$ is connected, both multipliers on the right-hand side are not identically zero, and hence they both are stable polynomials.
By removing the vertices one by one with preservation of connectedness, we complete the proof. By Lemma 4, we can multiply all edges around a vertex by a positive constant, bringing the weight function to a convenient form. Lemma 6. Assume that, for some graph $G$ and a weight function $w$, the polynomial $P_{G,w}$ is stable. Then $G$ is stable qua unweighted graph. Proof. Suppose the contrary. Then $G$ is not stable qua unweighted graph, that is, by Theorem 1, $G$ is not distance-hereditary, and so, by the equivalent definition (v), $G$ contains either a long cycle, a domino, a house, or a gem as an induced subgraph. By Lemma 5, the corresponding weighted induced subgraph is weight-stable. Let us consider all cases of forbidden induced subgraphs, and show that, in each case, the weights on the induced subgraph can be made to be 1 by several operations of multiplication of all edges incident to a vertex by a positive number. By Lemma 4, stability does not change, and a contradiction is obtained by Proposition 1, (iii).
CyclesBy Lemma 4, any cycle of length $5$ can be reduced to a cycle in which each edge has weight $1$, and the unweighted cycle is unstable by Theorem 1. Consider a weighted cycle $C_n$, $n \geqslant 6$, with no chords. By applying Lemma 4 consecutively to all but one vertices, we obtain unit weight on all but one edges. If the last edge is $v_1v_n$, then the weight of each tree is $w(v_1v_n)$, except the one obtained by removing $v_1v_n$. So, we can proceed verbatim as in the proof for weight-free cycles, because the different summand in our substitution is zero. Indeed, using the above scaling, we have
$$
\begin{equation*}
\begin{aligned} \, P_{C_n}(x_1,x_2, \dots.x_n) &= \sum_{i=1}^{n-1} x_ix_{i+1}w(v_1v_n)+ x_nx_1 \\ &=w(v_1v_n) \cdot \biggl(\sum_{i=1}^{n-1}x_ix_{i+1} + \frac{1}{w(v_1v_n)} x_1x_n\biggr). \end{aligned}
\end{equation*}
\notag
$$
Substituting $x_3=x_6 =\dots=x_n=0$ and $x_4=x_5=1$, we find that the polynomial $x_1x_2+1$ is stable, which is incorrect (this polynomial becomes zero with substitution $x_1=x_2=i$). DominoLet $v_1v_4$ be the edge not included in the cycle $v_1v_2 \dots v_6v_1$ (see Fig. 1). Applying Lemma 4 in succession, we get the equations Considering the set $v_1,v_6,v_5,v_4$, we find that $w(v_4v_1)=1$; similarly, for the set $v_2,v_1,v_5,v_3$, we have $w(v_2v_3)=1$. This gives us a simple (unweighted) domino, which is unstable by Theorem 1.HouseWe apply Lemma 4 several times so that the edges of the cycle $C_5$ would have weight $1$. Consider the subgraph $C_4$, formed by the vertices $v_1v_2v_4v_5$. This graph, which contains three edges of weight 1, is stable by Lemma 5. Hence the fourth edge is also of weight $1$, as shown in the case of $C_4$. So, we have an unweighted house, which is unstable by Theorem 1. GemLet $v$ be the vertex of degree $4$. We apply Lemma 4 several times so that the weights of the edges of the induced cycle of length $5$ would be 1. If the vertices of degree $2$ are removed, we have subgraphs of the form $C_4^+$ (a complete graph without an edge), in which three edges from the cycle have weight $1$; by Lemma 5, they are stable. In $C_4^+$, the diagonal pair is always contractible, and hence, the products of the opposite edges of the cycle are equal, that is, if three of them are of weight $1$, then the fourth edge is also of weight 1. So, both diagonals in our $C_5$ are of weight $1$, because each of them is an edge of the cycle from $C_4^+$ in one of them (and in the other one it is a diagonal). Hence all edges are now of weight $1$, and so we have a simple gem, which it is unstable. This proves Lemma 6. Let us return to the proof of Theorem 2. Note that if the graph $G$ is not biconnected, then it suffices to verify the conclusion of the theorem for each biconnected component. In § 3.4, we will prove a somewhat stronger result (Proposition 2). The proof is by induction on the number of vertices. Proposition 2. Let, for some biconnected graph $G$ on at least four vertices and a weight function $w$, the polynomial $P_{G,w}$ be stable. Then $G$ contains at least two non-intersecting contractible pairs. The induction base for four vertices was verified in § 3.2. 3.4. The induction stepIn the rest of the proof, we will frequently use Lemma 5 on stability of a connected weighted subgraph of a stable graph. The following technical lemma will be required in the proof of the induction step in Proposition 2. Lemma 7. Let $G$ be a graph and $w$ be a weight function. Assume that $G$ cobtains two induced subgraphs $G_1$, $G_2$ whose union covers $G$, and let $x_1$, $x_2$, $y$ be three vertices lying in both subgraphs, let $G$ (and hence, $G_1$ and $G_2$) have edges $x_1y$ and $x_2y$ in $G$, and let the pair $x_1x_2$ be contractible in both $G_1$ and $G_2$. Then the pair $x_1x_2$ is also contractible in $G$. Proof. The subgraphs $G_1$ and $G_2$ contain all vertices of $G$, and the vertices $x_1$ and $x_2$ are graphically equivalent in $G$. Consider an arbitrary vertex $v$ connected to $x_1$ and $x_2$; for this vertex, we have since $v$ belongs to $G_1$ or to $G_2$, and since the pair $x_1x_2$ is contractible ($G_1$ or in $G_2$). So, the ratio $w(vx_1)/w(vx_2)$ is independent of the choice of $v$. This proves the lemma. Let us return to the induction step in the proof of Proposition 2. Let $G$ be a graph and $w$ be a weight function such that $P_{G,w}$ is stable. By Lemma 6 and Theorem 1, the graph $G$ is distance-hereditary. By definition (vi) of the class of distance-hereditary graphs, $G$ can be constructed by copying and adding pendant vertices, and since $G$ biconnected, the last operation was copying. This means that $G$ contains vertices $v$ and $v'$ such that their neighbourhoods coincide (modulo the vertices $v$ and $v'$), that is, Consider the weighted graph $H = G[V\setminus \{v'\}]$. Since $G$ is biconnected, the graph $H$ is weight-stable by Lemma 5. The case of non-biconnected $H$The graph $G$ is biconnected, and hence $H$ has at most one articulation vertex; it is clear that the only articulation vertex is $v$. Let us prove that $v$ and $v'$ are weight-contractible in $G$. Indeed, let $A_1, A_2, \dots, A_m$ be the neighbourhoods of $v$ in different biconnected components of $H$. Recall that the operation of multiplication does not change vertex contractibility, and so several applications of Lemma 4 ensures that all edges incident to $v$, except possibly an edge from $v'$, are of weight $1$. Let us show that all the weights for the vertex $v'$, except possibly $w(vv')$, are equal. To do this, it suffices to show that $w(v'x) = w(v'y)$ for arbitrary vertices $x \in A_i$, $y \in A_j$, $i \neq j$, adjacent to $v$ and $v'$. Consider the quadruple $v, v', x, y$. The vertices $x$ and $y$ lie in different biconnected components, and hence $G$ does not contain the edge $xy$. Hence this quadruple is either $C_4$ or $C_4^+$. In both these cases (which are considered in the induction base), the contractible pairs are $vv'$ and $xy$. Now the required equality follows, since the pair $xy$ is contractible. Thus, for non-biconnected $H$, we have found one contractible pair ($vv'$) in $G$. Let $H_1, H_2, \dots, H_m$, $m \geqslant 2$, be the biconnected components of $H$ (they all contain $v$). There are several cases to consider. $\bullet$ There exists an index $s$ such that $|H_s| \geqslant 4$. Since $|H_s| < |H|$, it follows from the induction base that $H_s$ contains two non-intersecting contractible pairs, of which one ($xy$, say) does not contain $v$. If $v$ is not adjacent to $x$ and $y$, then, on returning to $G$, the neighbourhoods of $x$ and $y$ are not changed, and the weights of the edges emanating from these vertices are also unchanged, and, hence, are contractible in $G$. If $v$ lies in the neighbourhood, then $v'$ is also contained in their congruent neighbourhoods. Hence $w(vx)/w(vy)=w(v'x)/w(v'y)$, and so the contractility is also preserved. $\bullet$ There is $s$ such that $|H_s|=3$. In this case, $H_s$ is the three-vertex cycle $vu_1u_2$, that is, the vertices $u_1$ and $u_2$ have a congruent neighbourhood (except for each other) consisting of the single vertex $v$. In other words, $u_1u_2$ is a contractible pair in $H_s$, and hence in $H$ and $G$ for the same reason. $\bullet$ Each of the graphs $H_s$ contains exactly two vertices, that is, each $H_i$ is an edge (which we denote by $u_iv$). In this case, $G$ has a contractible pair $u_1u_2$, because the neighbourhoods $v$ and $v'$ of $u_1$ and $u_2$, and $w(u_1v)/w(u_2v)=w(u_1v')/w(u_2v')$ since $vv'$ is contractible in $G$. So, if the graph $H$ is not biconnected, then the conclusion of the theorem holds. The case of a biconnected $H$ is much more involved. Lemma 8. The conclusion of Proposition 2 holds for any complete weighted graph $G$ and any weight function $w$. Proof. It is easily seen that any graph on at most three vertices is stable. The proof is by induction, the induction base (the case of four vertices) was verified in § 3.2.
The induction step. Suppose the contrary. Then $G$ contains at most one contractible pair. Consider the case where $G$ has no contractible pair. Let us remove an arbitrary vertex $x$. By Proposition 1, (iii), the remaining complete weighted graph $F$ is stable, and so by the induction base, there are two non-intersecting contractible pairs in $F$; we denote these pairs by $v_1v_2$ and $u_1u_2$. Let us apply Lemma 4 several times so as to have (to do this, we first equate by scaling the weights of the edges incident to $u_2$, and then by scaling in $u_2$ we can make sure that the weights in the remaining edge are equal to the weight of any edge incident to $u_2$). The pair $u_1u_2$ is contractible in $F$, and hence $w(v_2u_1) = 1$.So, for each vertex $q$ that is still not considered, we have $w(qu_1)=w(qu_2)$ and $w(qv_1)=w(qv_2)$, since the pairs $u_1u_2$ and $v_1v_2$ are contractible in the graph $F$. We assumed that, in the original graph, none of the pair $u_1u_2$ and $v_1v_2$ is contractible. Hence $w(xv_1) \neq w(xv_2)$ and $w(xu_1) \neq w(xu_2)$. Consider the graphs
$$
\begin{equation*}
G[\{x,v_1,u_1, u_2\}] \quad \text{and} \quad G[\{x, v_2, u_1, u_2\}].
\end{equation*}
\notag
$$
These graphs are stable, and hence, two of the three numbers $w(xv_1)$, $w(xu_1)$, $w(xu_2)$, (and of $w(xv_2)$, $w(xu_1)$, $w(xu_2)$) are equal. Hence we either have $w(xv_1)=w(xu_1)$ and $w(xv_2)=w(xu_2)$, or $w(xv_1)=w(xu_2)$ and $w(xv_2)=w(xu_1)$. Without loss of generality we can assume that the first case holds.
Let us show that $w(v_1v_2)=1$. Suppose that $w(v_1v_2)= t \neq 1$, and let $w(xv_1)=w(xu_1)=a$ and $w(xv_2)=w(xu_2)=b$. Considering the graphs $G[\{x,v_1,v_2, u_1\}]$ and $G[\{x, v_1, v_2, u_2\}]$, we see that among $b$, $a$, $at$ (and among $a$, $b$, $bt$) there are some equal numbers. Since $a \neq b$ and $t \neq 1$, we have $a = bt$ and $b = at$. But this is impossible, since $t > 0$. This contradiction shows that $w(v_1v_2)=1$. The edge $u_1v_1$ is not contractible in our graph, and so there is a vertex $y$ such that $w(yu_1)\neq w(yv_1)$. Note that $y$ is different from $x$, $ v_2$, and $u_2$, because these vertices do not distinguish between $u_1$ and $v_1$. So, $w(yv_1)=w(yv_2)$ and $w(yu_1)=w(yu_2)$. We apply Lemma 4 at the vertices $x$ and $y$ so as to have $w(xv_1)=w(xu_1)=1$ and $w(yu_1)=w(yu_2)=1$. Now all the weights depend on three variables: $a=w(xv_2)=w(xu_2)$, $b=w(yv_1)=w(yv_2)$, $c=w(xy)$, and we also know that $a,b \neq 1$. Considering the induced subgraphs on all possible quadruples of vertices consisting of $x$ and $y$ and of two more vertices from $\{u_1,v_1,u_2,v_2\}$, we see that each of the multisets
$$
\begin{equation*}
\{a,c,1\},\quad \{b,c,1\},\quad \{a,b,c\},\quad \{1,ab,c\},\quad \{c,a,ab\},\quad \{c,b,ab\}
\end{equation*}
\notag
$$
contains a pair of equal numbers. From the first two multisets, we either have $c=1$ or $a=b=c$. In the first case, from the third multiset we have $a=b$, and then the fifth multiset is $\{a, a^2, 1\}$. In the second case, the fourth multiset is also of the form $\{1,a,a^2\}$. In both cases, we get a contradiction, since $\{a, a^2, 1\}$ contains two equal numbers, but $a \notin\{0,1\}$ by the assumption.
It remains to consider the case where $G$ contains exactly one contractible pair; let $v_1v_2$ be such a pair. Applying Lemma 4, we normalize the edges incident to $v_2$ so as to have $w(uv_2)=w(uv_1)$ for some vertex $u$. Hence $w(uv_2)=w(uv_1)$ for any vertex $u$, because the pair $v_1v_2$ is contractible. By the induction assumption, the graph $G[V\setminus\{v_2\}]$ has two non-intersecting contractible pairs. Let $u_1u_2$ be any of the pairs that does not contain $v_1$. Note that the pair $u_1u_2$ is contractible in the original graph, because $w(u_1x)/w(u_2x)$ is the same for all $x \neq v_1$, and this value also coincides for $x = v_1$ and $x = v_2$. So, we found two non-intersecting contractible pairs in the graph $G$, the result required. This proves Lemma 8. Let us now consider an arbitrary $G$. As above, we start by finding a contractible pair in $G$. Since $H$ is biconnected, the induction assumption applies, and so, $H$ contains two non-intersecting contractible pairs $x_1x_2$ and $y_1y_2$. The vertex $v$ either lies in one of these pairs, or fails to. Case 1The vertex $v$ does not lie in either of the two selected contractible pairs in $H$. We have $N_G(v) \setminus \{v'\} = N_G(v') \setminus \{v\}$ and $N_H(x_1) \setminus \{x_2\} = N_H(x_2) \setminus \{x_1\}$, and hence the edges $x_1v$, $x_1v'$, $x_2v$, $x_2v'$ either all lie in $G$ or all fail to lie in $G$. If there are no such edges, then $x_1x_2$ is contractible in $G$, because it is contractible in $H$, and, in this case, the required pair is found. In the remaining case, $G$ contains these four edges, and a similar analysis shows that the edges $y_1v$, $y_1v'$, $y_2v$, $y_2v'$ are also in $G$. If the edge $vv'$ does not lie in $G$, then the base for the graph $G[\{x_1,x_2,v,v'\}]$ (which is isomorphic to $C_4$ or $C_4^+$) gives the contractible pairs $x_1x_2$ and $vv'$, because there is a cycle on this quadruple of vertices, and there is no edge $vv'$; and now the pair $x_1x_2$ is contractible in $G$. Similarly, considering the graphs $G[\{x_1,x_2,v,v'\}]$ and $G[\{y_1,y_2,v,v'\}]$, we find that the edges $x_1x_2$ and $y_1y_2$ lie in $G$. Now let us show that $G$ contains all edges of the form $x_iy_j$, $i,j \in \{1,2\}$. As in the previous paragraph, $G$ either contains all these edges or fail to contain any such edge. Assuming that there are no such edges, consider the graph $G[\{v,v',x_i,y_j\}]$. This graph has a cycle on all vertices, and has no edge $x_iy_j$. Hence the pairs $vv'$ and $x_iy_j$ are contractible in this graph. By definition of contractility, for $i=1$, $j=1,2$, and so $y_1y_2$ is a contractible pair in $G[\{vv'y_1y_2\}]$. Hence the pair $y_1y_2$ is contractible in $G$ by Lemma 7 with $H$ and $G[\{vv'y_1y_2\}]$. Hence all edges of the form $x_iy_j$ lie in $G$.Consequently, the graph $F = G[\{x_1,x_2,y_1,y_2,v'\}]$ is complete, and hence contains two non-intersecting contractible pairs by Lemma 8. If one of these pairs contains $v'$, then we can assume without loss of generality that this is the pair $v'x_1$. Hence $w(x_1y_1)/w(v'y_1)=w(x_1y_2)/w(v'y_2)$, which implies that $w(x_1y_1)/w(x_1y_2)=w(v'y_1)/w(v'y_2)$. Therefore, the pair $y_1y_2$ is contractible in $G$. So, two non-intersecting pairs from the set $\{x_1,x_2,y_1,y_2\}$ are contractible in $F$. If these are the pairs $x_1x_2$ and $y_1y_2$, then $w(x_1y_1)/w(x_2y_1)=w(x_1v')/w(x_2v')$, and the pair $x_1x_2$ is contractible in $G$, which would complete the analysis of Case 1. So, it remains to consider the case, where $x_1y_1$ and $x_2y_2$ are contractible pairs in $F$. In this case, the graph $G[\{x_1,x_2,y_1,y_2\}]$ has four contractible pairs of vertices, and hence, by applying Lemma 4, we can normalize the weights of edges in $G[\{x_1,x_2,y_1,y_2\}]$ so that all six edges among these four vertices would be of weight $1$. The pairs $x_1x_2$ and $y_1y_2$ are contractible in $H$, and hence, for any vertex $u \notin \{v',x_1,x_2\}$, the edges $ux_1$ and $ux_2$ are either both absent in $G$ or both lie in $G$. Hence $w(ux_1) = w(ux_2)$, and, for any vertex $u \notin \{v',x_1,x_2\}$, the edges $uy_1$ and $uy_2$ are either both absent in $G$ or both lie in $G$. Hence $w(uy_1) = w(uy_2)$. The pairs $x_1y_1$ and $x_2y_2$ are contractible in $F$, and hence $w(v'y_1) = w(v'x_1)$ and $w(v'y_2) = w(v'x_2)$. Since $x_1x_2$ and $y_1y_2$ are not contractible in $G$, we have $w(v'x_1) \neq w(v'x_2)$. Consider the pair $x_1y_1$. This pair is not contractible in $G$, and hence either there is a vertex $u \in (N_G(x_1) \Delta N_G(y_1)) \setminus \{x_1,y_1\}$, or there is a vertex $z \in N_G(x_1) \cap N_G(y_1)$ such that $w(zx_1) \neq w(zy_1)$ (recall the normalization from the last paragraph for which the weights in the subgraph $G[\{x_1,x_2,y_1,y_2\}]$ are unit). In the first case, we can assume without loss of generality that $ux_1 \in E$, $uy_1 \notin E$. Since $N_H(x_1) \setminus \{x_2\} = N_H(x_2) \setminus \{x_1\}$ we have $ux_2 \in E$, $uy_2 \notin E$. If the graph $G$ has no edge $uv'$, then the graph $G[\{v',x_1,x_2, u\}]$ has a cycle and does not contain the edge $uv'$. Hence $x_1x_2$ is a contractible pair, but this contradicts the fact that $w(x_1u)=w(x_2u)$ (since $w(y_1x_1)=w(y_1x_2)$ and the pair $x_1x_2$ is contractible in $H$) and $w(v'x_1) \neq w(v'x_2)$. So, the edge $uv'$ belongs to $G$. Consider the graphs $G[\{u, v', x_1, y_1\}]$ and $G[\{u, v', x_1, y_2\}]$. In each of these graphs, the pair $v'x_1$ is contractible, because there is a cycle and there is no edge $uy_j$. This, however, is a contradiction, since
$$
\begin{equation*}
w(y_1v')=\frac{w(y_1v')}{w(y_1x_1)}=\frac{w(uv')}{w(ux_1)} =\frac{w(y_2v')}{w(y_2x_1)}=w(y_2v').
\end{equation*}
\notag
$$
In the second case, the edges $zx_2$, $zy_2$ also lie in $G$, and have weights $w(zx_1)$ and $w(zy_1)$, respectively, because $z \neq v'$, so $z \in H$. We also have $z \notin \{x_1,x_2, y_1,y_2,v'\}$. Let us multiply all edges incident to the vertices $v'$ and $z$ so as to have $w(v'x_1)=w(zx_1)=1$ (this does not change the weights inside $G[\{x_1,x_2,y_1,y_2\}]$). As a result, $w(v'y_1)=w(zx_2)=1$. Let $a=w(zy_1)=w(zy_2)$ and $b=w(v'x_2)=w(v'y_2)$. By definition of $z$, $a \neq 1$, and further, since $x_1$ and $x_2$ are non-contractible in $G$, we have $b \neq 1$. Note that if $G$ has no edge $zv'$, then the graph $G[\{x_1,x_2,v',z\}]$ has five edges out of six, and hence the pair $v'z$ is contractible in this graph, but $w(x_1z)=1=w(x_2z)$, and $w(x_2v') = b \neq 1 = w(x_1v')$, a contradiction. Hence $G$ has the edge $zv'$. By Lemma 8, the graph $J = G[\{x_1,x_2, y_1,y_2,z, v'\}]$ has two contractible pairs. No pair inside the set $U := \{ x_1,x_2,y_1,y_2\}$ is contractible, because any pair except $x_1x_2$ and $y_1y_2$ has different weights on the edges leading to the vertex $z$, and the pairs $x_1x_2$ and $y_1y_2$ have different weights on the edges leading to the vertex $v'$. Hence each of the contractible pairs in $J$ contains a vertex not from $U$, and so one of them is $v't$, where $t \in U$. Hence $t$ does not belong to any of the pairs $x_1x_2$, $y_1y_2$ (without loss of the generality, we assume that this is the pair $x_1x_2$). Considering the induced subgraph $G[\{t,v',x_1,x_2\}]$, we get the pairs $v't$ and $x_1x_2$, which are contractible in this graph. Hence by Lemma 7, the pair $x_1x_2$ is also contractible in $G$. This completes the case where $v$ does not belong to any contractible pair in $H$. Case 2Now let $v$ belong to one of the pairs $x_1x_2$ and $y_1y_2$ (we assume without loss of generality that $v = x_1$). Recall that by definition $N_G(v) \setminus \{v'\} = N_G(v') \setminus \{v\}$, $N_H(x_1) \setminus \{x_2\} = N_H(x_2) \setminus \{x_1\}$, and $N_H(y_1) \setminus \{y_2\} = N_H(y_2) \setminus \{y_1\}$. Then either $G$ contains the six edges $x_1y_1$, $x_1y_2$, $x_2y_1$, $x_2y_2$, $v'y_1$, $v'y_2$ or fails to contain any of these edges. If $G$ has no these edges, then the pair $y_1y_2$ is contractible in $G$. It remains to consider the case where $G$ contains all these six edges. Considering the graphs $G[\{x_1,v',y_1,y_2\}]$ and $G[\{x_2,v',y_1,y_2\}]$, we see that either the pair $y_1y_2$ is contractible in these graphs, and hence by Lemma 7 this pair is contractible in $G$), or $G$ has the edges $v'x_1$, $v'x_2$ and $y_1y_2$. Similarly, looking at the graph $G[\{v',x_1,x_2,y_1\}]$, we see that either $G$ contains the edge $x_1x_2$ or $x_1x_2$ is a contractible pair. So, if no contractible pair is found, then the subgraph $G[\{x_1,x_2,y_1,y_2,v'\}]$ is complete, and hence by Lemma 8 two non-intersecting pairs of vertices are contractible in this subgraph. Hence one of these pairs does not contain $v'$, and this pair is distinct from $x_1x_2$ and $y_1y_2$, because otherwise this pair would be contractible in $G$ by Lemma 7. In addition, none of these pairs contains $v'$, because otherwise we can consider the induced graph on this pair and on a pair from $x_1x_2$, $y_1y_2$ disjoint from this pair. Hence the corresponding pair from $x_1x_2$, $y_1y_2$ would be contractible in $G$ by Lemma 7. So, it remains to consider the case where $x_1y_1$ and $x_2y_2$. are contractible pairs in the graph $G[\{x_1,x_2,y_1,y_2,v'\}]$. The further argument proceeds as at the end of Case 1: Lemma 4 allows one to achieve unit weights inside $G[\{x_1,x_2,y_1,y_2\}]$ due to the four contractible pairs in $G[\{x_1,x_2,y_1,y_2\}]$, and the subsequent scaling of all edges incident to the vertex $v'$ gives $1 = w(v'x_1) = w(v'y_1)$ and $a = w(v'x_2) = w(v'y_2) \neq 1$. The pair $y_1$ and $x_1$ is not contractible in $G$, and so there exists a vertex $z$ that distinguishes these vertices. Hence we either have $z \in (N_G(x_1) \Delta N_G(y_1)) \setminus \{x_1,y_1\}$, or $z \in N_G(x_1) \cap N_G(y_1)$ and $w(zx_1) \neq w(zy_1)$. Suppose that $z$ distinguishes the neighbourhoods of vertices. There are two subcases to consider: in the first one, $z$ is connected to $x_1$, $x_2$, $v'$; consider the graphs of $G[\{z,v',x_1,y_1\}]$ and $G[\{z,v',x_1,y_2\}]$. The $zx_1$ and $v'y_i$ are contractible in these graphs, and so
$$
\begin{equation*}
w(y_1v')=\frac{w(y_1v')}{w(y_1x_1)}=\frac{w(zv')}{w(zx_1)} =\frac{w(y_2v')}{w(y_2x_1)}=w(y_2v'),
\end{equation*}
\notag
$$
and $y_1y_2$ is contractible in $G$. In the second subcase, $z$ is connected to $y_1$ and $y_2$. Consider the graph $G[\{z,v',y_2,y_1\}]$. This graph has no edge $v'z$, and hence the pairs $v'z$ and $y_1y_2$ are contractible in this graph. By Lemma 7, the pair $y_1y_2$ is contractible in the whole $G$. In the second case, $z \notin \{x_1,x_2,y_1,y_2,v'\}$, and $G$ contains all edges between $z$ and the already considered five vertices $x_1x_2y_1y_2v'$, and so Lemma 8 applies to the graph $G[\{x_1,x_2,y_1,y_2,v',z\}]$. Completion of the proof of Theorem 2In both cases, we have found a contractible pair $xy$ in $G$. Let us go back to the beginning of the proof, and consider this pair as a pair $vv'$. Namely, consider the graph $H' = G[V\setminus \{x\}]$. The case of non-biconnected $H'$ was analyzed at the beginning of the proof. If $H'$ is biconnected, then, by the induction assumption, it has two non-intersecting contractible pairs; let us consider the one which does not contain $y$ (and call it $uv$). The pairs $xy$ and $uv$ are the required non-intersecting contractible pairs in $G$. This completes the proofs of Proposition 2 and Theorem 2. § 4. Distance-hereditary weighted graphsBy analogy with Theorem 1, we define the class of distance-hereditary weighted graphs as the class of stable weighted graphs. We will show that this definition is natural. By Lemma 6, the support of a distance-hereditary weighted graph is a distance-hereditary graph. We will next show that our definition coincides with another algebraic definition from [7]. We let $\operatorname{rk}(M)$ denote the rank of a matrix $M$. Let a weighted graph $G$ and its adjacency matrix $M_G$ be given; for arbitrary subsets $A,B \subset V(G)$, we set $\operatorname{rk}_G(A,B) := \operatorname{rk}(M_G[A,B])$, where $M[A,B]$ is the submatrix with column set corresponding to $A$ and the row set corresponding to $B$. We set $\operatorname{cutrk}(A)=\operatorname{rk}_G(A, V(G) \setminus A)$. It is clear that $\operatorname{cutrk}(A) = \operatorname{cutrk}(V(G) \setminus A)$, since the matrix $M_G$ is symmetric. Consider an arbitrary abstract tree $T$ (with vertex set $V(T) \supset V(G)$) whose pendant vertices (leaves) are exactly the vertices of $G$ and all other vertices are of degree $3$. Any edge $e$ of this tree defines a partition of the vertices of $G$ into two sets $A(e)$ and $B(e)$ consisting of the leaves of the connected components of the graph $T \setminus e$. The width of an edge $e$ is defined by $\operatorname{cutrk}(A(e)) = \operatorname{cutrk}(B(e))$. The width of a graph is defined the minimum, over all trees $T$, of the maximum width of an edge in $T$. In [7], it was shown that the class of unweighted graphs (any weight in this graph is $1$) of width $1$ coincides with the class of distance-hereditary graphs. Theorem 3. The class of distance-hereditary weighted graphs coincides with the class of $1$-width weighted graphs. Proof.
We further assume that all graphs under consideration are connected and have at least $3$ vertices. Note that the width of a connected graph is at least $1$ (otherwise there would exist a partition of its vertices into two sets with no edges between them).
The proof in one directionLet $G = (V,E)$ be a stable weighted graph $G = (V,E)$. We claim that its width is $1$. To do this, we need to find a tree in which the width of any edge is $1$. We will construct this tree by induction on $n=|V|$. The induction base: $n \leqslant 3$If the graph has at most $3$ vertices, then there is only one tree, and this is the tree we need, because in any partition there is a part of size $\geqslant 1$, so of rank $>1$. The induction stepThe graph $G$ has at least four vertices, and hence by Theorem 2 the stable weighted graph $G$ is either not biconnected or contains a contractible pair. The non-biconnected case. In this case, $G$ contains an articulation point $u$, that is, $G [V\setminus u]$ decomposes into the connected components $A_1, \dots, A_s$. Let $H_1 = G[A_1 \cup u]$, $H_2 = G[V \setminus A_1]$. By Proposition 1 (iii), $H_1$, $H_2$ are stable weighted graphs with fewer vertices, and so there exist width-1 trees $T_1$, $T_2$ for these graphs. Consider the tree $T=T_1 \cup T_2$, where the pendant vertices are exactly the vertices of the graph $G$, except $u$, the degree of each vertex, except $u$, is $3$ or $1$, and the vertex $u$ has degree $2$. Let us call the current vertex $u$ a vertex $v$, and connect the vertex $u$ only with $v$ (we denote the resulting tree by $T'$). Now the degree of each vertex is either $3$ or $1$, and the pendant vertices are exactly the vertices of $G$. It remains to verify that $T'$ has width $1$. Indeed, let $e$ be an edge of $T'$; by definition, $E(T') = E(T_1) \cup E(T_2) \cup \{uv\}$. The width of the edge $uv$ is $1$, because the size of one of the sets of the partition is $1$. Let $e$ be an edge of $T_i$ (we may assume without loss of generality that $i=1$). Hence the edge $e$ splits the vertices of $G$ into two sets, of which one set ($A = A(e)$) lies entirely in $H_1 \setminus u$. We have
$$
\begin{equation*}
\operatorname{cutrk}_G(e)=\operatorname{rk}(M_G[A,G \setminus A]) =\operatorname{rk}(M_G[A, H_1 \setminus A]),
\end{equation*}
\notag
$$
because these matrices differ by several zero lines. On the other hand,
$$
\begin{equation*}
\operatorname{rk}(M_G[A, H_1 \setminus A]) =\operatorname{rk}(M_{H_1}[A,H_1 \setminus A])=\operatorname{cutrk}_{H_1}(e) = 1
\end{equation*}
\notag
$$
by the induction assumption. So, the width of $e$ is $1$ for any edge $e$, that is, the width of $T'$ is $1$. In the biconnected case, the graph $G$ is obtained by copying some vertex $u$ from the graph $G_1$, that is, the graph $G$ has vertices $u$, $u_1$, which form a contractible pair (in other words, $G_1=G[V \setminus u_1]$). Since $G_1$ is weight-stable, there exists a tree $T_1$ of width $1$. Consider its pendant vertex corresponding to $u$, let $z$ be its only neighbour. We remove the edge $uz$ from $T_1$ and add the vertex $v$ together with the edges $vz$, $vu$, $vu_1$; we denote the resulting tree by $T$. The pendant vertices of $T$ are exactly the vertices of $G$, and the degree of each of the remaining vertices is $3$. It remains to check that $T$ has width $1$. Consider an arbitrary edge in $T$; this is either the edge $vu$, or $vu_1$, or an edge of $T_1$. In the first two cases, it is obvious that their width is $1$, because one of the sets in the partition has size $1$. Now consider an edge from $T_1$. This edge splits the vertex set of $G$ into two subsets, of which one set ($A = A(e)$) does not contain the vertices $u$, $u_1$ (because $e$ does not belong to the path between $u$ and $u_1$ in $T$). We have
$$
\begin{equation*}
\operatorname{cutrk}_G=\operatorname{rk}(M_G[A,G\setminus A]) =\operatorname{rk}(M_G[A,G_1\setminus A]),
\end{equation*}
\notag
$$
since the column corresponding to vertex $u_1$ is proportional to the column corresponding to $u$ since the pair $uu_1$ is contractible (by definition of a contractible pair, the zeros are located in the same rows, and the ratios of non-zero values are equal). In this case.
$$
\begin{equation*}
\operatorname{rk}(M_G[A,G_1\setminus A]) =\operatorname{rk}(M_{G_1}[A,G_1\setminus A]) =\operatorname{cutrk}_{G_1}(e)=1.
\end{equation*}
\notag
$$
Hence the width of the tree $T$ is also $1$. Proof in the other directionLet us show that a weighted graph $G$ with weight function $w$ of width $1$ is weighted distance-hereditary. We argue by induction on the number of vertices. The induction baseIf the graph has $\leqslant 3$ vertices, then this graph is always weighted distance-hereditary. The induction stepLet $G$ be a weighted graph $G$ and let $T$ be a width-1 tree with degrees of vertices $3$ and $1$. The tree $T$ contains a vertex $v$ which is adjacent to exactly two pendant vertices $u$ and $u_1$. We claim that these vertices form a contractible pair in $G$. Indeed, consider a partition along the third edge incident to $v$; let us call it $e = vz$. The sets of this partition are as follows: $A(e) = \{u, u_1\}$ and $B(e) = V(G) \setminus \{u, u_1\}$. By definition of $T$, the width of $e$ is $1$, that is, the vectors $a_i = w(uv_i)$ and $b_i = w(u_1v_i)$ are proportional. If the coefficient of proportionality is zero, then one of the vertices $u$, $u_1$ has no neighbours in the graph $G$ outside the set $u$, $u_1$. If the coefficient of proportionality is non-zero, then $w(uv_i)=0$ if and only if $w(u_1v_i)=0$, and, for non-zero weights, $w(uv_i)/w(u_1v_i)$ does not depend on the choice of $v_i \in B(e)$. So, in the pair $uu_1$, either one of the vertices is pendant and hangs on the other one (without loss of generality, we assume that $u_1$ hangs on $u$), or they form a contractible pair. Consider the graph $G \setminus u_1$, and find, for $G$, a width-1 tree. To this end, we replace in the tree $T$ the vertices $v$, $u$, $u_1$ with all incident edges by a single vertex $u$ with edge $uz$; let $T'$ be the resulting tree. Note that the partitions of set $V \setminus \{u_1\}$ given by the tree $T'$ are obtained from the partitions of set $V$ by the tree $T$ by removing the vertex $u_1$. So, the width of each partition is $1$, and $T'$ is a width-1 tree. Hence the graph $G[V \setminus u]$ has weighted width $1$; by the induction assumption, $G[V \setminus u]$ is a distance-hereditary weighted graph, and the graph $G$ was obtained from $G[V \setminus u]$ by copying a vertex or adding a pendant vertex. By Theorem 2, the graph $G$ is a distance-hereditary weighted graph. This proves Theorem 3. § 5. ConclusionsOur central Theorem 2 and Lemma 1 give an explicit characterization of stable weighted graphs with complex weights. Similarly to the unweighted case, it follows from Theorem 2 and Lemma 2 and 3 that the degree enumerator of a stable weighted graph decomposes into linear multipliers. The result allows us to define the class of distance-hereditary weighted graphs as the set of stable graphs. It turns out that this approach corresponds to a natural generalization of another algebraic definition [7]. We can also formulate a necessary and sufficient condition on the stability of a weighted graph in terms of forbidden induced weighted subgraphs (similarly to definition (v) for the unweighted case): the unstable induced weighted subgraphs on at most six vertices, as well as the unstable weighted cycles, should be forbidden. The proof of the equivalence essentially repeats that of the main theorem. Some related open questions can be found in [1]. We also pose the question on classification of the (weighted) graphs whose vertex spanning polynomial is Lorentzian (for a rather long definition of Lorentzian polynomials and their combinatorial properties, see [8]). AcknowledgementThe authors are grateful to Fedor Petrov for his attention to the work and useful advice. 
Citation in format AMSBIB
\Bibitem{ProChe25} |
|
||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|