ISSN 2148-838Xhttps://doi.org/10.13069/jacodesmath.863113 J. Algebra Comb. Discrete Appl. 8(1) • 23–29 Received: 23 January 2020 Accepted: 13 September 2020 0 Journal of Algebra Combinatorics Discrete Structures and Applications Clique polynomials of 2-connected K5-free chordal graphs Research Article Hossein Teimoori Faal Abstract: In this paper, we give a generalization of the author’s previous result about real rootedness of clique polynomials of connected K4-free chordal graphs to the class of 2-connected K5-free chordal graphs. The main idea is based on the graph-theoretical interpretation of the second derivative of clique polynomials. Finally, we conclude the paper with several interesting open questions and conjectures. 2010 MSC: 05C31, 05C69, 30C15 Keywords: Chordal Graphs, Clique Polynomials, Clique Roots, Clique Value 1. Introduction Polynomials with only real roots are appeared in many branches of theoretical and applied mathe- matical sciences. In combinatorics, having all roots real property is equivalent to being log-concave and unimodal using Newton’s well-known theorem [3]. Indeed if A = {ak}k≥0 is a combinatorial sequence and it’s generating function pA(x) = ∑n k=0 akx k has only real roots, then the sequence A′ = { ak (nk) } k≥0 is log-concave. This immediately implies that A is also log-concave. Moreover, if A positive and log-concave then A is also unimodal. A complete subgraph of a graph G with i vertices is called an i-clique. The (ordinary) generating function of i-cliques of G denoted by C(G,x) is called the clique polynomial of G [4]. A real root of C(G,x) is called a clique root of G. In [4] Hajiabolhassan and Mehrabadi proved that any simple graph G has a clique root in [−1, 0). They also showed that the class of triangle-free graphs has only clique roots. This immediately implies another algebraic proof of Mantel’s theorem [1]. Hossein Teimoori Faal; Department of Mathematics and Computer Science, Allameh Tabataba’i University, Tehran, Iran (email: hossein.teimoori@atu.ac.ir). 23 https://orcid.org/0000-0001-5861-6287 H. T. Faal / J. Algebra Comb. Discrete Appl. 8(1) (2020) 23–29 In [8], the author obtained a generalization of clique-rootedness of the class of triangle-free graphs. Indeed, he showed that an intersting subclass of chordal graphs has only clique roots. Indeed, using the idea of breadth-first search tree the author of this paper proved the following result. Theorem 1.1. The class of K4 - free connected chordal graphs has only clique roots. In particular, this class has always a clique root −1. As a consequence of the above theorem, he also gave an algebraic proof of Turán’s graph theorem for K4 - free graphs. It is not hard to show that the class of connected K5 - free chordal graphs has not always only clique roots. Therefore, characterizing those subclasses of connected K5 - free chordal graphs which have only clique roots is an interesting and challenging problem. In this paper, we continue the above line of research by proving that the class of 2-connected K5-free chordal graphs has only clique roots. Our main motivation for introducing a new class of graphs with only clique roots is to move forward in the direction of finding a new algebraic proof of Turán’s graph theorem. It seems that this idea can be more generalized to prove Turán-type extremal results. The paper is organized, as follows. In section two, we quickely review the basics of clique polynomials. In particular, we introduce the graph-theoretical interpretations of the first and the second derivatives of clique polynomials. We also review the basic theory of chordal graphs. In section three, we state and prove the main result of our paper which asserts that the class of 2-connected K5-free chordal graphs has only clique roots. Finally, we conclude the paper with several interesting open questions and conjectures. 2. Basic definitions and notations We assume that our graphs are simple, finite and undirected. We also assume that they are connected, unless otherwise stated. For a given graph G = (V,E) and an arbitrary finite set S ⊆ V (G), the subgraph induced by S denotes by G[S]. For a vertex v ∈ V (G), it’s open neighborhood N(v) is defined as the set of vertices adjacent to v. A new graph obtained by deleting the vertex v from G is called the vertex- deleted subgraph of G and is denoted by G−v. One can similarly define the edge-deleted subgraph G−e of G. We also recall that the collection of all vertex-deleted subgraphs {G − v}v∈V (G) of G is called a vertex-deck of G. The collection of edge-deleted subgraphs {G−e}e∈E(G) of G is called the edge-deck of G. 2.1. Clique polynomials For a given graph G, the clique polynomial of G denoted by C(G,x) is defined as C(G,x) = 1 +∑ω(G) i=1 ci(G)x i, where ci(G) denotes the number of i-cliques of G and ω(G) is the size of the largest clique in G. Using a simple counting argument, one can obtain the following vertex-recurrence relation for clique polynomials. Lemma 2.1 (see [4]). Let G be a graph and v ∈ V (G) be a vertex of G. Then, we have C(G,x) = C(G−v,x) + xC(G[N(v)],x). (1) We also have the following vertex-deck identity for the number of cliques. The proof is a straight forward double-counting argument. Lemma 2.2. Let G = (V,E) be a graph on n vertices. Then, we have (n− i)ci(G) = ∑ v∈V (G) ci(G−v), (i ≥ 1). (2) 24 H. T. Faal / J. Algebra Comb. Discrete Appl. 8(1) (2020) 23–29 In a similar way, one can also get the following edge-recurrence relation for clique polynomials. We will use the notation N(e) = N(u) ∩N(v), for an edge e = {u,v}∈ E(G). Lemma 2.3 (see [4]). Let G = (V,E) be a graph and e ∈ E(G) be an edge of G. Then, we have C(G,x) = C(G−e,x) + x2C(G[N(e)],x). (3) One can also similarly obtain the following edge-deck identity for the number of cliques. Lemma 2.4. Let G = (V,E) be a graph on n vertices and m edges. Then, we have( m− ( i 2 )) ci(G) = ∑ e∈E(G) ci(G−e), (i ≥ 2). (4) The first derivative of subgraph-counting polynomials has been already studied in the literature [6]. Here, we have a graph-theoretical interpretation for the case of clique polynomials. Proposition 2.5. Let G = (V,E) be simple graph, then we have d dx C(G,x) = ∑ v∈V (G) C(G[N(v)],x). We can generalize the above formula as the following interesting formula. To the best of our knowl- edge, the formula is new. Proposition 2.6. Let G = (V,E) be simple graph, then we have d2 dx2 C(G,x) = 2 ∑ e∈E(G) C(G[N(e)],x). Proof. We first multiplying both sides of Equation (4) by xi and then summing over all i (i ≥ 0), we get ∑ i≥0 ( m− ( i 2 )) ci(G)x i = ∑ i≥0 ∑ e∈E ci(G−e)xi, or equivalently, by interchanging the summation order, we obtain m ∑ i≥0 ci(G)x i −x2 ∑ i≥2 ( i 2 ) ci(G)x i−2 = ∑ e∈E  ∑ i≥0 ci(G−e)xi   . (5) Next, by the definition of a clique polynomial of a graph, it’s second derivative is equal to d2 dx2 C(G,x) = 2 ∑ i≥2 ( i 2 ) ci(G)x i−2. (6) Therefore, considering relation (6) and the definition of a clique polynomial, we can rewrite equation (5) as follows mC(G,x) −x2 ( 1 2 d2 dx2 C(G,x) ) = ∑ e∈E C(G−e,x). or equivalently, d2 dx2 C(G,x) = 2 ∑ e∈E C(G,x) −C(G−e,x) x2 . (7) Finally, Equations (7) and (3) imply the desired result. 25 H. T. Faal / J. Algebra Comb. Discrete Appl. 8(1) (2020) 23–29 2.2. Chordal graphs In this subsection, we briefly review the basics of the class of chordal graphs. For more information about chordal graphs, one can refer to [7]. We first recall that a graph G is called a chordal graph if any induced cycle of G of length greater than three has a chord. By a chord, we simply mean an edge connecting two non-adjacent vertices of a cycle. We also need the following important definition from the paper [8]. For given graphs G1 and G2, we say that a graph G arises from G1 and G2 by pasting along S if we have G1 ∪G2 = G and G1 ∩G2 = S. We also use the notation G1 ∪S G2 whenever G1 and G2 are pasted along S. It is worth to note that the above definition immediately implies that any chordal graph can be recursively constructed by successively pasting complete graphs along cliques. We also recal the following key result [8]. Theorem 2.7. Let G be a chordal graph defined as a pasting of the complete graphs {Gi}ri=1 of sizes ni’s, respectively. That is, G = G1 ∪Q1 G2 ∪Q2 · · · ∪Qr−1 Gr, where {Qj} r−1 j=1 are cliques of sizes lj’s, respectively. Then, we have C(G,x) = r∑ i=1 (x + 1)ni − r−1∑ j=1 (x + 1)lj. (8) The above theorem immediately implies the following interesting conclusion. Corollary 2.8. Every r-connected chordal graph G has always a clique root −1 . The multiplicity of this root is equal to r. 3. Main results In this section, we give a generalization of the result of the paper [8], as follows. We also recall that a real root α of a polynomial Pn(x) of degree n is called of multiplicity 2, if Pn(x) can be written as (x−α)2Qn(x), where Qn−2(x) is another polynomial of degree n− 2. Theorem 3.1. The class of 2-connected K5-free chordal graphs has only clique roots. Moreover, it has r = −1 as a clique root of multiplicity 2. Here is the idea of the proof. We first prove that the quartic clique polynomial C(G,x) has a real root r = −1 of multiplicity 2. Therefore, we get C(G,x) = (1 + x)2Q(G,x) in which Q(G,x) is a quadratic polynomial. Thus, we only need to prove that Q(G,x) has at least one real root. It is not hard to show that this is equivalent to prove that d 2 dx2 C(G,x) has at least a real root. Proof. First of all we note that the last part of the result follows form Corollary 2.8, for r = 2. Next we note that since G is a K5-free chordal graph the induced graph G[N(e)], for each e ∈ E(G), is a collection of some trees or even isolated vertices. Hence, we get 1 2 d2 dx2 C(G,x) = ∑ e∈E C(G[NG(e)],x), = k1∑ i=1 C(G[NG(ei)],x) + k2∑ j=1 C(G[NG(ej)],x) − (k1 + k2 −m), = k1∑ i=1 (1 + x)(1 + lix) + k2∑ j=1 (1 + kjx) − (k1 + k2 −m), 26 H. T. Faal / J. Algebra Comb. Discrete Appl. 8(1) (2020) 23–29 where k1 and k2 denotes the number of trees (on li > 1 vertices) and isolated vertices, respectively. Here, m denotes the number of edges. Thus, considering the fact that kj ≥ 1 and k1 + k2 ≥ m, we finally obtain d2 dx2 C(G,−1) ≤ 0. This completes the proof, considering the fact that d 2 dx2 C(G, 0) = 1 > 0 and intermediate value theorem. Recall that a sequence {ai}i≥0 of real numbers is called log-concave [2] if for every i ≥ 1, we have ai−1ai+1 ≤ a2i . We recall the well-known Netwon’s theorem about the real-rootedness of polynomials. Lemma 3.2. If Pn(x) = a0 + a1x + · · · + anxn ∈ R[x] is a real-rooted polynomial, then the sequence {ai}i≥0 is log-concave. Moreover, the following sequence a0( n 0 ), a1(n 1 ), · · · , an(n n ), is also log-concave. A generalization of Turán’s theorem is the following which is due to Zaykov [9]. Theorem 3.3 (see [9]). For all integers k ≥ l ≥ 0, the maximum number of l-cliques in a graph on n vertices and no k + 1-cliques is ( k l ) (n k )l. The following result is an immediate consequence of Theorem 3.1 which is a Zykov theorem for the class of 2-connected K5-free graphs. Corollary 3.4. For 0 ≤ l ≤ 4, the number of l-cliques of the class of 2-connected K5-free chordal graphs is ( 4 l ) (n 4 )l . Proof. Let C(G,x) = 1 + c1x + c2x2 + c3x3 + c4x4 be the clique polynomial of a 2-connected K5-free graphs. Then by Theorem 3.1, the clique polynomial C(G,x) is real-rooted. Now, by Lemma 3.2, we immediately conclude the following inequalities 1 1 ≤ c1 4 ≤ c2 6 ≤ c3 4 ≤ c4 1 . (9) Now, the proof for the cases l = 0, 1 are obvious. For l = 2, from inequalities 1 1 ≤ c1 4 ≤ c2 6 , using log-concavity we immediately conclude that c2 ≤ 3n 2 8 . This is indeed the Turan’s graph theorem for K5-free graphs. For l = 3, again inequalities c14 ≤ c2 6 ≤ c3 4 (using log-concavity) imply c3 ≤ n 3 16 . The case l = 4 is a little tricky. First of all, from inequalities c2 6 ≤ c3 4 ≤ c4 1 by log-concavity, we obtain that c4 c2 6 ≤ c 2 3 16 . Now, by multiplying both sides to c1 4 and consdering the inequality c1 4 c3 4 ≤ c 2 2 36 , we get c1c4 ≤ c2c36 . Finally, considering the two previous cases l = 2, 3 we obtain c2c3 6 ≤ n 5 162 . Thus, the two last inequalities immediately imply c4 ≤ n 4 162 . 4. Open questions and conjectures In this section, we present some interesting open questions and problems. The following question naturally arises. Question 1. Is it true that the class of 2-connected K6-free chordal graphs has only clique roots? 27 H. T. Faal / J. Algebra Comb. Discrete Appl. 8(1) (2020) 23–29 4 3 1 2 5 6 G1 : Figure 1. The clique polynomial of G1 is C(G1, x) = 1 + 6x + 12x2 + 11x3 + 5x4 + x5 Here is a counter-example. Let G1 be the graph depicted in Figure 1. It is not hard to see that d3 dx3 C(G1,x) = (5)(4)(3)(1 + x) 2 + (3)(2) > 0, which immediately implies that not all roots of C(G1,x) are real. In this direction, we made the following conjecture. Conjecture 1. The class of 3-connected K6-free chordal graphs has only clique roots. The following question is also of our special interest. Question 2. Which classes of 2-connected K5-free non-chordal graphs have only clique roots. A graph G is called an r-triangulated graph if each edge of G belongs to at most r + 1 triangles of G. We come up with the following seemingly interesting conjecture. Conjecture 2. The class of 2-connected 2-triangulated graphs has only clique roots. It seems that one obvious way to extend the result of our paper is to think about some generalizations of the edge-deck counting formula (4). Thus the question that we encounter is as follows. Question 3. Is there any anlogue of edge-deck identity for the case of triangles? More specifically, does the following formula ( t− ( i 3 )) ci(G) = ∑ δ∈∆(G) ci(G− δ) (i ≥ 3), (10) hold in general? Note that here t shows the number of triangles of G and ∆(G) denotes the set of all triangles of G. We will call the above identity the triangle-deck formula. Here, we have a counter-example for triangle-deck identity in general. Let G2 be a graph which is shown in Figure 2. Hence, for i = 2, we obtain t = 3, c2(G2) = 8, c2(G2 −δ1) = c2(G2 −δ2) = c2(G2 − δ3) = 5. Thus, we get (3 − 0)8 6= 15, as required. We define a triangle graph of a given graph G which is denoted by T(G) as a graph with the vertex set ∆(G). Two triangles δ1 and δ2 are connected in T(G) if their share an edge in G. We believe that the following conjecture is true. Conjecture 3. Let G be a graph such that it’s triangle graph T(G) is an empty graph (a collection of isolated vertices), then the triangle-deck identity is true. 28 H. T. Faal / J. Algebra Comb. Discrete Appl. 8(1) (2020) 23–29 3 4 1 2 5 6 G2 : Figure 2. The triangle-deck identity is not true for G2 For more on triangle graphs see the reference [5]. Finallly, we are interested to answer to the following question. The reason is clear, becuase it will give us a proof of the well-known Zykov theorem [9] for K5-free graphs. Question 4. Can we relax the condition of being biconnected with connected in Corollary 3.4? References [1] J. A. Bondy, U. S. R. Murty, Graph theory, Springer GTM 244 (2008). [2] P. Branden, Unimodality, log-concavity, real-rootedness and beyond, Handbook of Enumerative Com- binatorics, CRC Perss (2018). [3] L. Comet, Advanced combinatorics, 200. Reidel, Dordrecht-Boston (1974). [4] H. Hajiabolhassan, M. L. Mehrabadi, On clique polynomials, Australasian Journal of Combinatorics 18 (1998) 313–316. [5] P. Haxell, A. Kostochka, S. Thomasse, Packing and covering triangles in K4-free planar graphs, Discrete Applied Mathematics 28 (2012) 653–662. [6] X. Li, I. Gutman, A unified approach to the first derivatives of graph polynomials, Discrete Applied Mathematics 587 (1995) 293–297. [7] T. A. McKee, F. R. McMorris, Topics in intersection graph theory (Monographs on Discrete Mathe- matics and Applications), Society for Industrial and Applied Mathematics (1987). [8] H. Teimoori, Clique roots of K4-free chordal graphs, Electronic Journal of Graph Theory and Appli- cations 7(1) (2010) 105–111. [9] A. A. Zykov, On some properties of linear complexes, Mat. Sbornik N.S. 24(66) (1949) 163–188. 29 https://www.springer.com/gp/book/9781846289699 https://www.taylorfrancis.com/books/handbook-enumerative-combinatorics-miklos-bona/e/10.1201/b18255 https://www.taylorfrancis.com/books/handbook-enumerative-combinatorics-miklos-bona/e/10.1201/b18255 https://www.springer.com/gp/book/9789401021982 https://ajc.maths.uq.edu.au/pdf/18/ajc-v18-p313.pdf https://ajc.maths.uq.edu.au/pdf/18/ajc-v18-p313.pdf https://doi.org/10.1007/s00373-011-1071-9 https://doi.org/10.1007/s00373-011-1071-9 https://doi.org/10.1016/0166-218X(95)00121-7 https://doi.org/10.1016/0166-218X(95)00121-7 https://dx.doi.org/10.5614/ejgta.2019.7.1.8 https://dx.doi.org/10.5614/ejgta.2019.7.1.8 http://mi.mathnet.ru/eng/msb5974 Introduction Basic definitions and notations Main results Open questions and conjectures References