Ratio Mathematica Volume 42, 2022

On the Roots and Stability of
Vertex connectivity Polynomial

Priya Krishnan*
Anil Kumar Vasu†

Abstract

The introduction of the concept of vertex connectivity polynomial of
graphs in [Priya and Anil Kumar, 2021b] triggered the need to study
the nature of roots as well as the stability properties of the same for
various graph classes. This paper mainly deals with results about the
nature of roots, stability and schur stability of the vertex connectivity
polynomial.
Keywords: Vertex connectivity polynomial, Vertex-connected ver-
tices, Schur stability.
2020 AMS subject classifications:05C31, 05C40.1

*Department of Mathematics, University of Calicut, Thenhipalam, Kerala-673635, India;
priyakrishna27.clt@gmail.com.

†Department of Mathematics, University of Calicut, Thenhipalam, Kerala-673635, India;
anil@uoc.ac.in.
1Received on March 17th. Accepted on June 25th. Published on June 30th. doi:
10.23755/rm.v41i0.731 . ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper
is published under the CC-BY licence agreement.

145



K. Priya, V. Anil Kumar

1 Introduction
The adjacency property of vertices in a graph is not sufficient to characterize

a graph in terms of its connectedness as the deletion of the corresponding edge
may or may not disconnect the graph. More generally, the connectivity property
of vertices in a graph may not be preserved after the deletion of edges of the
geodesics linking them. This motivated the authors to introduce the concept of
“vertex-connected vertices”, which shares geodesics preserving the connectivity
of a graph. The study of vertex-connected vertices in [Priya and Anil Kumar,
2021a] triggered the need to define vertex connectivity polynomial discussed in
[Priya and Anil Kumar, 2021b] for simple finite connected graphs to explicitly
reveal the number of vertex pairs that disconnect a graph.

A polynomial p(z) is said to be stable, or a Hurwitz polynomial, if all its ze-
ros lie in the open left half-plane [Fuhrmann, 2011] and is schur stable if all its
zeros belong to the open unit disk. Hurwitz polynomials are important in control
systems theory, because they represent the characteristic equations of stable linear
systems [Gajender and Sharma, 2014]. Thus the study of a graph polynomial is
worthy only if it succeeds in predicting the behavior of some stable physical sys-
tems. This motivated the authors to study about the nature of roots and stability of
the vertex connectivity polynomial of a graph. Throughout this paper, G denotes
a finite simple connected graph with vertex set and edge set denoted by V (G) and
E(G) respectively. All the graph theoretic terminology and notations used in the
paper are as in [Harary, 1969].

2 Main Results
Definition 2.1. Let G be a graph of order n. Then, the vertex connectivity poly-
nomial of G, denoted by V [G; x], is defined in [Priya and Anil Kumar, 2021b]
as:

V [G; x] =

diam(G)+1∑
i=1

|Di|xi,

where Di is the set of all vertex pairs which disconnects G into i components.

Definition 2.2. Let G = (V, E) be a graph and let u, v ∈ V . Then, the vertices
u and v are said to be vertex-connected if the deletion of the edges of none of the
geodesics connecting u and v disconnects G into multiple components.
The graph G is vertex-connected if each of its vertex pairs are vertex-connected.
[Priya and Anil Kumar, 2021a]

146



On the Roots and Stability of Vertex connectivity Polynomial

Definition 2.3. Let G = (V, E) be a graph. Then, a pair of vertices (u, v) ∈ V ×V
at a distance d > 0 are said to be d-metrically connective if it disconnects the
graph G into d components.
The graph G is metrically connective if every pair of its vertices are d-metrically
connective for some d > 0.[Priya and Anil Kumar, 2021a]

Theorem 2.4. (Routh-Hurwitz Criteria [Fuhrmann, 2011]) Given a polynomial

P(x) = a0x
n + a1x

n−1 + a2x
n−2 + · · · + an−1x + an,

where the coefficients ai’s are real constants, the n Hurwitz matrices using the
coefficients ai of the above polynomial are defined as

H1 =
[
a1
]
, H2 =

[
a1 a0
a3 a2

]
, H3 =


a1 a0 0a3 a2 a1
a5 a4 a3


 , · · · ,

Hn =



a1 a0 0 0 · · · 0
a3 a2 a1 a0 · · · 0
a5 a4 a3 a2 · · · 0
...

...
...

... · · ·
...

0 0 0 0 · · · an


 ,

where aj = 0 if j > n. All the roots of the polynomial P(x) are negative or
have negative real part if and only if the determinants of all Hurwitz matrices are
positive: det(Hj) > 0, j = 1, 2, . . . , n.

Definition 2.5. Let G be a graph. Then, the roots of the vertex connectivity poly-
nomial of G are called the vertex connectivity roots of G.

The following are some of the observations about the vertex connectivity roots
of graphs.

(i) (0,∞) is a zero-free interval of the vertex connectivity polynomial V [G; x]
for any graph G.

(ii) If G is metrically connective, then it has at most diam(G) vertex connec-
tivity roots.

(iii) If G is a tree, then it has diam(G) + 1 vertex connectivity roots counting
multiplicities.

Theorem 2.6. Let G be a graph. Then, zero is a vertex connectivity root of G of
multiplicity greater than one iff G is a tree.

147



K. Priya, V. Anil Kumar

Proof. Assume that zero is a vertex connectivity root of G of multiplicity k > 1.
Then, V [G; x] = xkg(x), a polynomial of degree greater than or equal to 2. This
means that every vertex pair of G disconnects the graph into at least two compo-
nents so that none of its edges belongs to a cycle. Hence it follows that G is a tree.
Conversely, if G is a tree, all its edges being cut edges, none of the vertex pairs
are vertex-connected. That is, V [G; x] is a polynomial free of linear coefficient.

This completes the proof.

Theorem 2.7. Let G be a graph of order n. Then, zero is the only vertex connectiv-
ity root of G iff either G is vertex-connected or every vertex pair of G disconnects
the graph into exactly two components.

Proof. Assume that zero is the only vertex connectivity root of G. Then, V [G; x] =
rxk, where r, k > 0. But, V [G; 1] =

∑diam(G)+1
i=1 |Di| =

(
n
2

)
so that r =

(
n
2

)
. That

is,V [G; x] =
(
n
2

)
xk.

Case (i): If k = 1, then V [G; x] =
(
n
2

)
x so that G is vertex-connected.

Case (ii): If k > 1, then all the
(
n
2

)
vertex pairs disconnects the graph into k

components. But if a vertex pair disconnects G into k components, then
corresponding to that there exists a vertex pair disconnecting the graph into
two components. Thus it follows that V [G; x] =

(
n
2

)
x2.

Conversely, if either G is vertex-connected or every vertex pair of G disconnects
the graph into exactly two components, then we get V [G; x] as

(
n
2

)
x and

(
n
2

)
x2

respectively. In both the cases, it follows that zero is the only vertex connectivity
root of G .

This completes the proof.

Corollary 2.8. Let G be a non vertex-connected graph of order n. Then, zero is
the only vertex connectivity root of G iff G = P2.

Proof. Let zero be the only vertex connectivity root of G. Since G is not vertex-
connected, from theorem 2.7 it follows that G is a tree and V [G; x] =

(
n
2

)
x2. This

means that all the
(
n
2

)
vertex pairs disconnects G into two components. Now if

possible assume n > 2. Then, since every edge of G is a cut edge, we can find a
vertex pair at 2 units distance which disconnects G into three components. There-
fore n = 2 and G = P2.

This completes the proof.

148



On the Roots and Stability of Vertex connectivity Polynomial

Theorem 2.9. Let G be a graph and n1, n2 are respectively be the number of
vertex-connected vertex pairs and the number of vertex pairs which disconnects
G, where n1 > n2 . If n1 is prime, then G lacks non-zero real vertex connectivity
roots.

Proof. Let V [G; x] = xg(x), where g(x) = anxn + an−1xn−1 + . . . a1x + n1,∑n
i=1 ai = n2, for some n. Clearly all the zeros of g(x) are non-zero. Let β be a

zero of g(x) such that |β| ≤ 1. Then,

g(β) = anβ
n + an−1β

n−1 + . . . a1β + n1 = 0.

That is,

|n1| = |anβn + an−1βn−1 + . . . a1β| ≤ |an| + |an−1| + . . . |a1| = n2,

a contradiction. Therefore, |β| > 1.
Now, if possible, assume that β is real. Then, g(x) is reducible over the set of all
real numbers. That is,

g(x) = (x − β)h(x),
where h(x) is a nonconstant integer polynomial. Now,

n1 = g(0) = −βh(0).

Since n1 is prime and since |β| > 1, |h(0)| must be 1. Let β1, . . . , βn−1 be the
zeros of h(x) and a be its leading coefficient. Then,

|β1, . . . βn−1| =
1

|a|
≤ 1.

But β1, . . . , βn−1 are the zeros of g(x) also so that |βi| > 1 ∀i = 1, . . . , n − 1, a
contradiction. Therefore g(x) has no real zeros and hence G lacks non-zero real
vertex connectivity roots.

This completes the proof.

Corollary 2.10. Let G be a graph and n1, n2 are respectively be the number of
vertex-connected vertex pairs and the number of vertex pairs which disconnects
G, where n1 > n2. Then, all the non-zero vertex connectivity roots of G lie strictly
outside the unit circle.

Theorem 2.11. Let G be a graph with |Di| = m ∀i ≤ n, where 2 ≤ n ≤
diam(G) + 1. Then, all the non-zero vertex connectivity roots of G are distinct
and are of unit modulus. In addition, if G is a tree of diameter p, where p is an
odd prime, then G lacks non-zero real vertex connectivity roots.

149



K. Priya, V. Anil Kumar

Proof. Without loss of generality, let G be a graph which is not a tree.
Since |Di| = m, ∀ i = 1, 2, . . . , n,

V [G, x] = m
n∑

i=1

xi = mx[1 + x + . . . + xn−1].

The zeros of the polynomial 1 + x + . . . + xn−1 are the nth roots of unity except
1 and hence it follows that the vertex connectivity roots of G are distinct. Now, if
G is a tree, then V [G; x] is a polynomial of degree diam(G) + 1. That is,

V [G, x] = m

diam(G)+1∑
i=2

xi = mx2[1 + x + . . . + xdiam(G)−1].

Since diam(G) = p, the polynomial 1 + x + . . . + xp−1 is irreducible over the
set of all rationals and hence it has no rational roots. But the only possible real
p − 1th root of unity is −1, which is rational. Therefore, it can be concluded that
G is free of non-zero real vertex connectivity roots.

This completes the proof.

Corollary 2.12. If n is odd, then all the non-zero vertex connectivity roots of Cn
lies on the unit circle. In addition, if n−1

2
is even, then Cn has exactly two real

vertex connectivity roots.

Proof. This follows from the fact that V [Cn; x] =
∑n−1

2
i=1 nx

i for odd n and −1 is
a kth root of unity if k is even.

Theorem 2.13. (i) Let G1 and G2 be two disjoint graphs. If a is a vertex con-
nectivity root of both G1 and G2, then a is also a vertex connectivity root of
G1 + G2.

(ii) Let G be a vertex-connected graph of order n and let G
′

be the graph ob-
tained by adjoining one pendent vertex to m distinct vertices of G, m ≤ n.
Then, the vertex connectivity roots of G

′
are the roots of the polynomial

V [G; x] + nmx2 +
(
m
2

)
x3.

(iii) Let G be metrically connective and let d = diam(G). Then, G has exactly
d vertex connectivity roots counting multiplicities.

Proof. (i) This follows from the fact that V [G1+G2; x] = V [G1; x]+V [G2; x].

(ii) Since G is vertex-connected, the newly adjoined vertices along with every
vertex of G disconnects G

′
into exactly two components and mutually dis-

connects G
′

into three components.
Therefore, V [G

′
; x] = V [G; x] + nmx2 +

(
m
2

)
x3.

150



On the Roots and Stability of Vertex connectivity Polynomial

(iii) This follows from the fact that the degree of V [G; x] is d.

This completes the proof.

Theorem 2.14. Let G be a graph of order n and diameter d. Then, any vertex
connectivity root β of G either has nonpositive real part or satisfies

|β| <
1 +

√
1 + 2n(n − 1)

2
.

Proof. Let β be a non-zero vertex connectivity root of G. If |β| ≤ 1, then the
result holds trivially since

1+
√

1+2n(n−1)
2

> 1.

Case(i) : Let G be a tree. Then, the degree of V [G; x] is d + 1.
We have, V [G; x] = x2g(x), where g(x) = ad−1xd−1 + . . . + a1x + a0.
Since

∑d−1
i=0 ai =

(
n
2

)
, |ai| ≤

(
n
2

)
∀i = 0, 1, . . . , d − 1. Now, if |β| > 1 and

Re(β) > 0, then

|g(β)|
|βd−1|

= |ad−1 +
ad−2
β

+ . . . +
a1

βd−2
+

a0
βd−1

|

≥ |ad−1 +
ad−2
β

| −
n(n − 1)

2
[
1

|β2|
+ . . . +

1

|βd−1|
]

> Re(ad−1) + ad−2Re(
1

β
) −

n(n − 1)
2

[
1

|β2| − |β|
]

≥ 1 −
n(n − 1)

2
[

1

|β2| − |β|
], since ad−1, ad−2 ≥ 1 and Re(β) > 0.

=
|β2| − |β| − n(n−1)

2

|β2| − |β|
≥ 0,

whenever |β2| − |β| − n(n−1)
2

≥ 0.

That is, if |β| ≥
1+

√
1+4

n(n−1)
2

2
=

1+
√

1+2n(n−1)
2

and Re(β) > 0, then
|g(β)|
|βd−1| > 0 so that β cannot be a zero of g(x).

Case(ii) Let G be a graph which is not a tree. Then at least one edge of G is a
part of some cycle so that the linear coefficient of V [G; x] is non-zero. Let
V [G; x] = xh(x), where h(x) = am−1xm−1 + . . . + a1x + a0. Here also∑m−1

i=0 ai =
(
n
2

)
, |ai| ≤

(
n
2

)
∀i = 0, 1, . . . , m − 1, so that similar calculation

as in case(i) yields that if |β| ≥ 1+
√

1+2n(n−1)
2

and Re(β) > 0, then β can-
not be a zero of g(x). .

151



K. Priya, V. Anil Kumar

Therefore, from the above two cases we get that every vertex connectivity root
of the graph G either has nonpositive real part or has modulus strictly less than
1+
√

1+2n(n−1)
2

.

This completes the proof.

Theorem 2.15. Let G be a tree with diameter d ≤ 2. Then, all the non-zero
vertex connectivity roots of G lie in the left half plane. In addition, if the leading
coefficient of V [G; x] dominates, then the polynomial is schur stable.

Proof. Case(i): If d = 1, then G = P2 so that V [G; x] = x2. Thus, the result
holds trivially.

Case(ii): If d = 2, then V [G; x] = x2(ax + b), a cubic polynomial where a, b >
0. Thus the only non-zero zero x = −b

a
of V [G; x] lies in the left half

plane. Now if the leading coefficient of V [G; x] dominates, then | b
a
| < 1

and thus all the vertex connectivity roots of G lies inside the unit circle.
Hence V [G; x] is schur stable.

Corollary 2.16. V [K1,n; x] is schur stable iff n > 3.

Theorem 2.17. Every vertex connectivity root of the path graph Pn lie in the
closed left half plane iff n ≤ 5

Proof. We have, V [Pn; x] =
∑n−1

i=1 (n − i)x
i+1. Thus the result holds trivially for

n = 2 and n = 3.
Now for n ≥ 4, let V [Pn; x] = x2g(x).
When n = 4, g(x) = x2 + 2x + 3 so that

H1 =
[
2
]
, H2 =

[
2 1
0 3

]
are having positive determinants.
If n = 5, then g(x) = x3 + 2x2 + 3x + 4 so that all the Hurwitz matrices

H1 =
[
2
]
, H2 =

[
2 1
4 3

]
, H3 =


2 1 04 3 2
0 5 4




have positive determinant.
For n = 6, g(x) = x4 + 2x3 + 3x2 + 4x + 5.

H3 =


2 1 04 3 2
0 0 4




152



On the Roots and Stability of Vertex connectivity Polynomial

so that det(H3) < 0.
For n ≥ 7,

H3 =


2 1 04 3 2
6 5 4




so that det(H3) = 0. Thus for n ≥ 6, g(x) is not stable so that all the vertex
connectivity roots of Pn does not belong to the closed left half plane.

This completes the proof.

A bistar graph Bm,m is the union of two identical star graphs K1,m whose centres
joined together to form a new edge.

Theorem 2.18. The vertex connectivity roots of the bistar graph Bm,m always lie
in the closed left half plane and are all real iff m ≥ 7. Also, for all m ≥ 2, zero is
the only vertex connectivity root of multiplicity > 1.

Proof. We have, V [Bm,m; x] = x2[m2x2 + m(m + 1)x + (2m + 1)].[Priya and
Anil Kumar, 2021b]
The zeros of the polynomial g(x) = m2x2 + m(m + 1)x + (2m + 1) are

x =
−m(m + 1) ±

√
m2(m + 1)2 − 4m2(2m + 1)

2m2

=
−(m + 1) ±

√
m2 − 6m − 3

2m
.

Since
√
m2 − 6m − 3 <

√
m2 < m + 1, all the zeros of g(x) lie in the left half

plane. The zeros of g(x) are real iff m2 − 6m − 3 ≥ 0 iff m ≥ 3 +
√
12 or

m ≤ 3 −
√
12. Since m is a positive integer and since 6 < 3 +

√
12 < 7, we

get that the vertex connectivity roots of Bm,m are all real iff m ≥ 7. Now, since
m2 − 6m − 3 is never zero for any integer m, all the zeros of g(x) are distinct.

This completes the proof.

Corollary 2.19. For m ≥ 3, V [Bm,m; x] is schur stable.

Proof. In the proof of theorem 2.18, the zeros of g(x) are −(m+1)±
√
m2−6m−3

2m
. It

can be observed that |−(m+1)±
√
m2−6m−3

2m
| < 1 for m ≥ 3 so that all the vertex

connectivity roots of Bm,m lie inside the unit circle.

This completes the proof.

153



K. Priya, V. Anil Kumar

Theorem 2.20. Let P(z) = anzn + an−1zn−1 + . . . + a1z + a0 be a complex
polynomial such that |ak| > |a0| + |a1| + . . . + |ak−1| + |ak+1| + . . . + |an| for
some 0 ≤ k ≤ n. Then exactly k zeros of P lie strictly inside the unit circle, and
the other n − k zeros of P lie strictly outside the unit circle.[Zhao, 1947]

A helm Hn is obtained by adding pendent edges to every vertex on the graph
obtained as the join of the cycle Cn−1 and K1. A webgraph WBn is obtained
by joining the pendent vertices of Hn to form a cycle and then adding a single
pendent edge to each vertex of the outer cycle. A butterfly graph is a double shell
with same apex along with exactly two pendent edges at the apex.

Theorem 2.21. (i) For n > 3, the helm Hn is not schur stable.

(ii) For n > 3, the web graph WBn is not schur stable. But all the vertex
connectivity roots of WBn are real and belong to the closed left half plane.

(iii) For n > 4, the butterfly graph BFn is not schur stable. But all the vertex
connectivity roots of BFn are real and belong to the closed left half plane.

Proof. (i) From [Priya and Anil Kumar, 2021b], we get the vertex connectivity
polynomial of Hn as V [Hn; x] =

(
n−1
2

)
x3 + n(n − 1)x2 +

(
n
2

)
x .

Here, the quadratic coefficient n(n−1) >
(
n−1
2

)
+
(
n
2

)
so that from theorem

2.20 it follows that only two zeros of V [Hn; x] lie inside the unit circle and
one zero outside the unit circle. Hence Hn is not schur stable.

(ii) We have, V [WBn; x] =
(
n−1
2

)
x3 + (2n − 1)(n − 1)x2 +

(
2n−1

2

)
x.

That is, V [WBn; x] =
(
n−1
2

)
x[x2 +

2(2n−1)
n−2 x +

2(2n−1)
n−2 ]. Since the dis-

criminant of the quadratic polynomial p(x) = x2 + 2(2n−1)
n−2 x +

2(2n−1)
n−2 is

12(2n−1)
(n−2)2 > 0, it follows that all the vertex connectivity roots of WBn are

real. The remaining results follows easily from the fact that the zeros of

p(x) are exactly
−2(2n−1)±

√
12(2n−1)

2(n−2) .

(iii) From [Priya and Anil Kumar, 2021b], it follows that the vertex connec-
tivity polynomial of BFn is V [BFn; x] = x3 + (2n − 4)x2 +

(
n−2
2

)
x.

For n = 5, 6, 7, the non-zero vertex connectivity roots of BFn are ex-
actly −3 ±

√
6, −4 ±

√
10 and −5 ±

√
15 respectively so that in all those

cases the graph is not schur stable. Now for n > 7, the linear coefficient(
n−2
2

)
> 1+2n−4 and hence by theorem 2.20, only one zero of V [BFn; x]

lie inside the unit circle and the other two zeros lie outside the unit circle.
Hence for n > 4, BFn lacks schur stability. Now, since 2n − 4 is greater
than the magnitude of the square of the discriminant of the quadratic factor
in V [BFn; x] and since the discriminant is positive, it follows that all the

154



On the Roots and Stability of Vertex connectivity Polynomial

non-zero vertex connectivity roots of BFn belong to the left half plane.

This completes the proof.

3 Conclusions
In this paper, the nature of roots and stability properties of some well known

graphs were discussed in detail and inferences were made about its stability. More
general properties regarding the graph stability can be inferred only after studying
the same for graph operations.

4 Acknowledgements
The first author would like to thank the University Grants Commission of India

for funding this research.

References
Paul A Fuhrmann. A polynomial approach to linear algebra. Springer Science &

Business Media, 2011.

Gaurav Gajender and Himanshu Sharma. Hurwitz polynomial. International jour-
nal of innovative research in technology, 1(7):340–342, 2014.

F Harary. Graph Theory. Addison-Wesley, 1969.

K Priya and V Anil Kumar. On the vertex connectivity index of graphs. Chinese
Journal of Mathematical Sciences, 1(1):49–59, 2021a.

K Priya and V Anil Kumar. On the vertex connectivity polynomial of graphs.
Advances and Applications in Discrete Mathematics, 26(2):133–147, 2021b.

Yufei Zhao. Integer polynomials. MOP 2007 Black Group,
https://yufeizhao.com, 69(1):17–20, 1947.

155