Ratio Mathematica Volume 47, 2023 On Real Roots of Complement Degree Polynomial of Graphs Safeera K.* Anil Kumar V.† Abstract Many studies have been carried out on the roots of graph polynomi- als such as the matching polynomials, the characteristic polynomial, the chromatic polynomial, and many others. In this paper, we study the real roots of the complement degree polynomials of some graphs. Moreover, we investigate the location of the roots of the complement degree polynomials of some graphs. Keywords: complement degree polynomial, cd-roots. 2020 AMS subject classifications: 05C31,30C15 1 *Department of Mathematics, University of Calicut, Malappuram, Kerala, India 673 635; safeerakoralatil@gmail.com. †Department of Mathematics, University of Calicut, Malappuram, Kerala, India 673 635; anil@uoc.ac.in. 1Received on June 13, 2022. Accepted on February 6, 2023. Published on March 10, 2023. doi: 10.23755/rm.v41i0.795. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is published under the CC-BY licence agreement. 79 1 Introduction In mathematics, a graph polynomial is a graph invariant whose values are polynomials. In algebraic graph theory, invariants of this kind are explored [Shi et al., 2016]. These are some crucial graph polynomials: characteristic polyno- mial, chromatic polynomial, dichromatic polynomial, flow polynomial, Ihara zeta function, Martin polynomial, matching polynomial, reliability polynomial, Tutte polynomial. There is a lot of research on the roots of graph polynomials, in- cluding the characteristic polynomial, the chromatic polynomial, the matching polynomial, and many others. The location and nature of the roots have been important research areas for several graph polynomials. Recently, the present au- thors[Safeera and Kumar, a] introduced the complement degree polynomial of a graph. Definition 1.1. Let G = (V, E) be a finite simple graph of order n and let CD(G, i) be the set of vertices of degree i in complement graph G and let Cdi(G) = |CD(G, i)|. Then complement degree polynomial of G is the polynomial: CD[G, x] = ∆(G)∑ i=δ(G) Cdi(G)x i, (1) where δ(G) and ∆(G) respectively denote the minimum degree and maximum degree of the complement graph G [Safeera and Kumar, a]. The authors also derived the complement degree polynomial of some well- known graphs and some graph operations [Safeera and Kumar, a,b]. In this paper, we study the real roots of the complement degree polynomial of some graphs obtained in [Safeera and Kumar, a]. In particular, we investigate the location of the roots of the polynomials so obtained. 2 Main Results The roots of several graph polynomials have drawn a lot of interest, both for what they represent and what their nature and location indicated. In this section, we investigate the roots of the complementary degree polynomial investigated in [Safeera and Kumar, a]. Definition 2.1. The roots of polynomial defined in equation (1) are called cd-roots of G. The number of real cd-roots of a graph G where the multiplicities counted, is denoted by cd(G). 80 Theorem 2.1. Zero is a cd-root of a complement degree polynomial of a graph G with n vertices if and only if ∆(G) ≤ n − 2. Proof. Let G be a graph of order n and zero is a cd-root of the polynomial CD[G, x]. If G has a vertex, say v which is adjacent to all other vertices, then v is an isolated vertex in G. This implies that CD[G, x] has a constant term. This is a contradiction because zero is a cd-root of CD[G, x]. Therefore, G has no vertices adjacent to all other vertices. Conversely, assume that ∆(G) ≤ n − 2. Then δ(G) ≥ 1. Equivalently, Cd0(G) = 0. This tells us that the constant term of CD[G, x] is zero, and hence the result follows.2 Corolary 2.1. If G has no isolated vertices, then zero is a root of CD[G, x] with multiplicity δ(G). Theorem 2.2. If G is the non complete graph of order n, then zero is the only cd-root of CD[G, x] if and only if G is a regular graph. Proof. First, assume that zero is the only cd-root of a graph G with n vertices. Then it follows that the complement degree polynomial of G is CD[G, x] = nxr. This implies that the degree of every vertex in G is the same. Equivalently, G is regular. Conversely, assume that G is a r-regular graph. Then we have CD[G, x] = nxn−r−1. It follows that zero is only cd-root of CD[G, x]. 2 Corolary 2.2. If G is the r-regular graph with n vertices, then cd(G) = n−r−1. Theorem 2.3. Let G be a graph with n vertices. Then (1) CD[G, x] is a strictly increasing function in [0, ∞). (2) Let G be a graph and H be any spanning subgraph of G. Then the degree of CD[G, x]) is less than or equal to the degree of CD[H, x]. (3) Let G be a graph and H be any induced subgraph of G. Then the degree of CD[G, x]) greater than equal to the degree of CD[H, x]. (4) Let G be a graph of order n with t isolated vertices in G and r isolated vertices in G. Then Cd0(G) = r and Cdn−1(G) = t. Proof Proof of the above result follows from the definition of complement degree polynomial of a graph. Theorem 2.4. For a cosplitting graph CS(G) of r-regular graph G with n ver- tices, cd(CS(G)) = n. 81 Proof. Observe that CD[CS(G), x] = nxn−1(1 + xr) [Safeera and Kumar, a]. It is clear that x = 0 is a cd-root of G with multiplicity n − 1. Note that the polynomial 1 + xr has no real roots if r is even and one real root if r is odd. Thus we have, cd(CS(G)) = { n − 1 if r is even, n if r is odd . This completes the proof.2 Theorem 2.5. For a path graph Pn, cd(Pn) = { 0, n = 2 n − 2, n ≥ 3. Proof. For a path graph Pn, we have [Safeera and Kumar, a]: CD[Pn, x] = { 2xn−2, n = 2 (n − 2)xn−3 + 2xn−2, n ≥ 3 . Here we consider two cases: If n = 2, then CD[P2, x] = 2, which has no zeros. If n > 2, then we have CD[Pn, x] = x n−3(2x + n − 2). Obviously, x = 0 is the cd-root of CD[Pn, x] with multiplicity n − 3 and x = −(n − 2)/2 is the another cd-root of CD[Pn, x]. Thus cd(Pn) = { 0, n = 2 n − 2, n ≥ 3. This completes the proof.2 Theorem 2.6. Let G be a graph with order n and G=G ∪ G ∪ . . . ∪ G (m times). Then cd(G) = n(m − 1) + cd(G). Proof. Let G be a graph of order n and G=G ∪ G ∪ . . . ∪ G (m times). Then, CD[G, x] = mx(m−1)nCD[G, x]. Observe that x = 0 is a zero of CD[G, x] of multiplicity n(m−1). Consequently, cd(G) = n(m−1)+cd(G). This completes the proof.2 Theorem 2.7. For a ladder graph Ln, cd(Ln) = 2n − 3 for n ≥ 2. Proof. Obviously, cd-roots of CD[Ln, x] are x = 0 with multiplicity 2n − 4 and x = −n − 2/2 with multiplicity one. Hence the result follows.2 Theorem 2.8. For a cocktail party graph CPn, cd(CPn) = 3 for n ≥ 2. 82 Proof. In [Safeera and Kumar, a], the authors proved that CD[CPn, x] = 2x2(2+(n−2)x). It follows that CD[CPn, x] has cd-roots x = 0 with multiplicity 2 and x = −2/(n − 2) with multiplicity one. Thus cd(CPn) = 3. Hence the proof follows.2 Theorem 2.9. If S(G) is a splitting graph of a graph G with n vertices, then cd(S(G)) ≥ 1. Proof. Observe that CD[S(G), x] do not have a constant term(see [Safeera and Kumar, a]). Hence the result2. Theorem 2.10. For a bull graph Bl, cd(Bl) = 1. Proof. Note that CD[Bl, x] = x(2x2 + x + 2) [Safeera and Kumar, a]. The roots of this polynomial are x = 0, −1±i √ 15 4 . Obviously, x = 0 is the only real root of CD[Bl, x]. Hence the result follows.2 Theorem 2.11. For a sunlet graph Sln, cd(Sln) = 2n − 4 for n ≥ 3 . Proof. Note that CD[Sln, x] = nx2n−4(1 + x2) [Safeera and Kumar, a]. Then the cd-roots are x = 0 with multiplicity 2n − 4 and x = ±i. Thus cd(Sln) = 2n − 4.2 Theorem 2.12. For a tadpole graph Tm,n, cd(Tm,n) = m + n − 2 for m ≥ 3 and n ≥ 1. Proof. Note that CD[Tm,n, x] = xm+n−4(x2 + (m + n − 2)x + 1) [Safeera and Kumar, a]. Since the discriminant of the polynomial x2 +(m+n−2)x+1 is always greater than or equal to zero, it follows that cd(Tm,n) = m + n − 2. This completes the proof.2 Theorem 2.13. For a bistar graph Bn,n (n ≥ 1), cd(Bn,n) = { n if n is even n + 1 if n is odd. Proof. Note that CD[Bn,n, x] = 2xn(nxn + 1). If n is even, then nxn + 1 has only complex roots. If n is odd, then nxn + 1 has only one real root and n − 1 complex roots. Hence , cd(Bn,n) = { n if n is even n + 1 if n is odd. This completes the proof.2 83 Theorem 2.14. For a web graph Wbn, cd(Wbn) = 3n − 4 for n ≥ 3. Proof. Note that CD[Wbn, x] = nx3n−5(x3 + x + 1). Obviously, the cd-roots of CD[Wbn, x] are 0 with multiplicity 3n − 5, −0.68233, 0.34116 ± 1.16154i. Hence cd(Wbn) = 3n − 4.2 Theorem 2.15. For a armed crown graph Cn ⊙ Pm, cd(Cn ⊙ Pm) = { n(m + 1) − 4, if m=1,2 n(m + 1) − 2, if m≥ 3. Proof. Note that CD[Cn ⊙ Pm, x] = x 2 + (m − 1)x + 1. For m = 1, 2, the zeros of x2 + (m − 1)x + 1 are complex numbers. If m > 2, the zeros of x2 + (m − 1)x + 1 are real numbers. Thus cd(Cn ⊙ Pm) = { n(m + 1) − 4 if m=1,2 n(m + 1) − 2 if m≥ 3. This completes the proof.2 Theorem 2.16. For a sungraph Sn, n ≥ 3, cd(Sn) = { n − 2, if n is odd n − 1, if n is even. Proof. Note that CD[Sn, x] = nxn−2(xn−1 +1). Since xn−1 +1 has real roots if and only if n is even. This tells us that the real cd-roots of CD[Sn, x] are 0 and −1 if n is even. If n is odd x = 0 is the only real root of CD[Sn, x]. Therefore, we have cd(Sn) = { n − 2, if n is odd n − 1, if n is even. This completes the proof.2 Theorem 2.17. For a bipartite cocktaill party graph bn(n ≥ 2), we have cd(Bn) = n. Proof. The result follows from the fact that CD[Bn, x] = 2nxn.2 84 3 Location of the cd-roots of the some graphs In this section, we investigate the location of the roots of some complement degree polynomials. Here need the following result [Prasolov, 2009]. Theorem 3.1. Let f(z) = zn + a1zn−1 + . . . + an, where ai ∈ C. Then, inside the circle |z| = 1 + max|ai|, there are exactly n roots of f, multiplicities counted. Theorem 3.2. All the cd-roots of the gear graph Gn lie inside the circle with center (0, 0) and radius n + 1. Proof. Observe that CD[Gn, x] = xn + nx2n−3 + nx2n−2. In this case max|ai| = n, where a′is are the coefficients of CD[Gn, x] for i = 1, 2, . . . , 2n−2. Then by theorem 3.1, the result follows.2 Theorem 3.3. All the cd-roots of the wheel graph Wn lie inside the circle with center (0, 0) and radius n. Proof. It follows from the fact that CD[Wn, x] = (n − 1)xn−4 + 1.2 Theorem 3.4. All the cd-roots of the bull graph Bl lie on the unit circle centered at the origin. Proof. Note that the cd-roots of Bl are x = 0, −1±i √ 15 4 . These three roots lie on the unit circle centered at the origin.2 Theorem 3.5. All the cd-roots of the sunlet graph Sln lies in the disk |z| ≤ 1. Proof. The cd-roots of the sunlet graph CD[Sln, x] are x = 0 and x = ±i. Hence the result follows. 2 Theorem 3.6. All the cd-roots of the sun graph Sn lies in the disk |z| ≤ 1. Proof. Note that CD[Sn, x] = nx2n−3 + nxn−2 = nxn−2(xn−1 + 1). Obvi- ously, roots of xn−1 + 1 lie on the unit circle. Hence the result.2 4 Conclusions In this paper, we introduced cd-roots of the complement degree polynomial of some graphs. Moreover, we investigated the location of the cd- roots of some complementary degree polynomials. 85 Acknowledgements The authors are grateful to the referee for valuable suggestions. The first au- thor acknowledges Council of scientific and industrial research(CSIR) for finan- cial support. References A. Anto and P. P. Hawkins. Vertex polynomial of graphs with new results. Global journal of Pure and Applied Mathematics, 15:469–475, 2019. F. Harary. Graph Theory. Springer, New York, 1969. V. V. Prasolov. Polynomials. Springer, New York, 2009. K. Safeera and V. A. Kumar. Complement degree polynomial of graphs. Gulf Journal of Mathematics (Communicated), a. K. Safeera and V. A. Kumar. Complement degree polynomials of some graph operations. Palestine Journal of Mathematics (Communicated), b. K. Safeera and V. A. Kumar. Stability of complement degree polynomial of graphs. South East Asian Journal of Mathematics and Mathematical Sciences( Communicated), c. Y. Shi, M. Dehmer, X. Li, and I. Gutman. Graph polynomials. CRC Press, 2016. M. Shikhi. A Study on common Neighbor Polynomial of Graphs. PhD thesis, 2019. S. S. R. V. Jeba Rani and T. S. I. Mary. Vertex polynomial of ladder graphs. Infokara Research, 8:169–179, 2019. 86