ISSN 2590-9770 The Art of Discrete and Applied Mathematics 1 (2018) #P1.09 https://doi.org/10.26493/2590-9770.1257.dda (Also available at http://adam-journal.eu) On a conjecture about the ratio of Wiener index in iterated line graphs* Katar´ina Hri¡akov´Martin Knor n´a, Facultyof Civil Engineering, Slovak UniversityofTechnology, Radlinsk´ eho 11, 810 05, Bratislava, Slovakia Riste ¡ Skrekovski FMF, University of Ljubljana, 1000 Ljubljana and Faculty of Information Studies, 8000 Novo Mestoand FAMNIT, Universityof Primorska, 6000Koper, Slovenia Received9January 2017, accepted30May 2018, published online23July 2018 Abstract Let G be a graph. Denote by W (G) its Wiener index and denote by Li(G) its i-iterated line graph. Dobrynin and Mel’nikov proposed to estimate the extremal values for the ratio Rk(G)= W (Lk(G))/W (G) for k . 1. Motivated by this we study the ratio for higher k’s. We prove that among all trees on n vertices the path Pn has the smallest value of this ratio for k . 3. We conjecture that this holds also for k =2, and even more, for the class of all connected graphs on n vertices. Moreover, we conjecture that the maximum value of the ratio is obtained for the complete graph. Keywords:Wiener index, linegraph,tree, iterated linegraph. Math. Subj. Class.: 05C12, 05C05, 05C76 Introduction Let G be a graph. We denote its vertex set and edge set by V (G) and E(G), respectively. For anytwo verticesu, v let d(u, v) be the distance from u to v. The Wiener indexof G, W (G), is defned as X W (G)= d(u, v), u6 =v *The frst and second author acknowledge partial supportby Slovak research grants VEGA 1/0007/14, VEGA 1/0026/16, VEGA 1/0142/17, APVV-0136-12 and APVV-15-0220. The research was partially supported by Slovenian research agencyARRS, program no. P1-0383. E-mail address: hrinakova@math.sk (Katar´ina Hri¡n´akov´a), knor@math.sk (Martin Knor), skrekovski@gmail.com (Riste ¡ Skrekovski) cb This work is licensed under http://creativecommons.org/licenses/by/3.0/ where the sum is taken over all unordered pairs of vertices of G. Wiener index was intro-ducedbyWienerin[17]. Sinceitis relatedtoseveral propertiesof molecules(see[7]), it is widely studied by chemists. The interest of mathematicians was attracted in 1970’s, when it was reintroduced as the transmission and the distance of a graph, see[16]and[5], respectively.For surveysand some up-to-date papers relatedtotheWienerindexof trees and line graphs see[15,18]and[2,8,13], respectively. By defnition, if G has a unique vertex, then W (G)=0. In this case, we say that the graph G is trivial. The line graph of G, L(G), has vertex set identical with the set of edges of G and two vertices of L(G) are adjacent if and only if the corresponding edges are incident in G. Iterated line graphs are defned inductively as follows: ( G if i =0, Li(G)= L(Li-1(G)) if i> 0. . n+1 Observe that W (Pn) = ((n-1) + ··· + 1)+((n-2) + ··· + 1)+ ··· +1 = . In 3 the case when a tree contains a small number of branching vertices (i.e., vertices of degree at least three), then it is suitable to use the theorem of Doyle and Graver[4]for computing itsWiener index: Theorem 1.1. Let T beatree on n vertices. Then  XX n +1 W (T )= - n(Ti) n(Tj) n(Tk) , 3 v.V (T )1.iW (T ) otherwise. The above result gives an immediate support to Conjecture 1.5: Corollary 1.7. Let k . 4. In the class of trees on n vertices, Rk attains the minimum value for Pn. In this paper we extend the above corollary to the case k =3. Let H be a tree on six vertices, two of which have degree 3 and the other four have degree 1. Recall that two graphs G1 and G2 are homeomorphic if and only if there is a third graph F , such that both G1 and G2 can be obtained from F by means of edge subdivision. In the proof we will use the following result[9, Corollary 1.6]: Theorem 1.8. Let T beatreewhichisnot homeomorphictoapath,claw K1,3 or H, and let k . 3. Then W (Lk(T )) >W (T ). By Theorem 1.8, to solve the case k =3, it is suffcient to consider the ratios for paths and trees homeomorphic to the claw K1,3 and H. Note that L3(Pn)= Pn-3 if n . 4, and we have . n-2 (n - 2)(n - 3)(n - 4) 3 R3(Pn)= . = . n+1 (n + 1)n(n - 1) 3 In Section 2we prove the following two results: Theorem 1.9. Let T beatree on n vertices homeomorphic to K1,3. Then R3(T ) >R3(Pn). Theorem 1.10. Let T beatree on n vertices homeomorphic to H. Then R3(T ) >R3(Pn). These two results together with Theorem 1.8 and Corollary 1.7 give us the following: Corollary 1.11. Let k . 3. Then the path Pn attains the minimum value of Rk in the class of trees on n vertices. 2 Proofs of Theorems 1.9 and 1.10 Proof of Theorem 1.9. Let Ca,b,c be a tree homeomorphic to the claw K1,3, such that the paths connecting the vertices of degree 1 with the vertex of degree 3 have lengths a, b and c,wherea . b . c . 1. The tree Ca,b,c hasexactly n = a+b+c+1 vertices, see Figure 1 for C4,3,2. Figure 1: The graph C4,3,2. Further, for i .{1, 2, 3} let Vi be the set of vertices of V (L(Ca,b,c)) of degree i. This naturally splits the problem into four cases according to the size of V1. Denote .= W (L3(Ca,b,c)) - W (Ca,b,c). (2.1) In[8], thevalueof . for each of these four cases is evaluated. For the sake of simplicity, let W0 = W (Ca,b,c) and W3 = W (L3(Ca,b,c)). Then .= W3 - W0 and W3 W0 +. . R3(Ca,b,c)= = =1+ . W0 W0 W0 By Theorem 1.1 we have W0 =(a + b + c + 2)(a + b + c + 1)(a + b + c)/6 - abc. (2.2) We prove that when |V (Ca,b,c)| = |V (Pn)|, that is when n = a + b + c +1, then R3(Ca,b,c) >R3(Pn). This inequality is equivalent to .(n - 2)(n - 3)(n - 4) 1+ > W0 (n + 1)n(n - 1) and after multiplying by denominators also to . .(n + 1)n(n - 1) + W0 (n + 1)n(n - 1) - (n - 2)(n - 3)(n - 4) > 0. (2.3) Since 3 .|Vi|. 0, there are four cases to consider. Case 1: a, b, c . 2. That is, |V1| =3.In[8]wehave .=(a+b+c)2 - 5(ab+ac+bc)+(a+b+c) + 21. (2.4) After substituing(2.4)and(2.2)into(2.3), we get that the left-hand side of(2.3)is equal to K.Hrin¡akov´aetal.:Ona ´conjectureabouttheratioofWienerindexiniteratedlinegraphs the following expression . 5 1.5abc (a - b)2 +(a - c)2 +(b - c)2+ 44a + 65a 2 + 25.5a 3 +7a 4 +2.5a + 3b2 44b + 130ab + 66.5a 2b + 13a 3b +7.5a 4b + 65b2 + 66.5ab2 + 12a 2b2 + 10a + 2 25.5b3 + 13ab3 + 10a 2b3 +7b4 +7.5ab4 +2.5b5 + 44c + 130ac + 66.5ac + 34 13ac +7.5ac + 130bc + 117abc + 18a 2bc +3a 3bc + 66.5b2 c + 18ab2 c + 23 13b3 c +3ab3 c +7.5b4 c + 65c 2 + 66.5ac 2 + 12ac 2 + 10ac 2 + 66.5bc2 + 18abc2 + 24 12b2 c 2 + 10b3 c 2 + 25.5c 3 + 13ac 3 + 10ac 3 + 13bc3 +3abc3 + 10b2 c 3 +7c + 5 7.5ac 4 +7.5bc4 +2.5c. . Since a, b, c . 2, the expression 1.5abc (a - b)2 +(a - c)2 +(b - c)2 and all the isolated terms are nonnegative. Moreover some of the terms, such as 44a for example, are strictly positive. Hence,(2.3)is satisfed, which means thatR3(Ca,b,c) >R3(Pa+b+c+1). Observe that the above longexpressionwas obtained from the left-hand sideof(2.3) . by subtracting 1.5abc (a - b)2 +(a - c)2 +(b - c)2 , which is nonnegative, and then by expanding the difference. Since all the parameters a, b, c are nonnegative, all the co­effcients in the expanded expression are positive and at least one of the terms is strictly positive,(2.3)is satisfed. We will use this way of reasoning especially in the proof of Theorem 1.10, where the expanded expressions are extremely long. Case 2: a, b . 2, c =1. That is, |V1| =2.In[8]wehave 2. = (a+b)2 - 8ab - 5(a+b) + 30. (2.5) After substituing(2.5)and(2.2)into(2.3)andexpanding theexpression, we get that the left-hand sideof(2.3)is equalto 96 + 170a + 97a 2 + 32a 3 + 11a 4 +2a 5 + 170b + 164ab + 43a 2b + 11a 3b +6a 4b + 97b2 + 43ab2 +8a 3b2 + 32b3 + 11ab3 +8a 2b3 + 11b4 +6ab4 +2b5 . Hence(2.3)is satisfed and soR3(Ca,b,1) >R3(Pa+b+2). Case 3: a . 2, b = c =1. That is, |V1| =1. In[8]we have .= -6a +6. After substituing this value of . and(2.2)into(2.3)andexpanding theexpression, we get that the left-hand sideof(2.3)is equalto 1.5a 5 + 12a 4 + 26.5a 3 + 60a 2 + 300a + 240. Hence(2.3)is satisfed and soR3(Ca,1,1) >R3(Pa+3). Case 4: a = b = c =1. That is, |V1| =0. In this case Ca,b,c = K1,3 has 4 vertices and L3(K1,3) is a cycle of length 3. Since W (L3(P4)) = 0, we have R3(C1,1,1) > 0= R3(P4), which establishes this small case, and also the proof of the theorem. Proof of Theorem 1.10. Denoteby Ha,b,c,d,e atree homeomorphic toH defned as follows: In Ha,b,c,d,e, the two vertices of degree 3 are joined by a path of length e +1, e . 0. Hence, this path has e vertices of degree 2. Further, at one vertex of degree 3 there start two pendant paths of lengths a and b, where a, b . 1, and at the other vertex of degree 3 there start another two pendant paths of lengths c and d, where c, d . 1. Thus Ha,b,c,d,e has n = a + b + c + d + e +2 vertices, out of which two have degree 3, four have degree 1 and the remaining vertices have degree 2, see Figure 2 for H3,3,4,2,2. By symmetry, we may assume that a . b, c . d, and b . d. That is, we assume that the shortest pendant path in Ha,b,c,d,e has length d. Figure 2: The graph H3,3,4,2,2. We proceed analogously as in the proof of Theorem1.9. Denote .= W (L3(Ha,b,c,d,e)) - W (Ha,b,c,d,e). (2.6) For the sake of simplicity, letW0 = W (Ha,b,c,d,e) and W3 = W (L3(Ha,b,c,d,e)). Then .= W3 - W0 and again . R3(Ha,b,c,d,e)=1+ . W0 By Theorem 1.1 we have  a + b + c + d + e +3 W0 = - ab(c + d + e + 1) - cd(a + b + e + 1). (2.7) 3 If e =0, then we have one vertex of degree 4 in L(Ha,b,c,d,e), while if e . 1, then the greatest degree of a vertex in L(Ha,b,c,d,e) is 3. Analogously asin[8],by symmetry we distinguish eleven cases. Five cases with at least one of a, b, c, d greater than or equal to 2 have e . 1, fve cases with at least one of a, b, c, d greater than or equal to 2 have e =0, and the last case has all a, b, c, d equal to 1. First we consider the cases with . > 0. Claim 1. If . > 0, then R3(Ha,b,c,d,e) >R3(Pa+b+c+d+e+2). Proof. Observe that |V (Ha,b,c,d,e)| = |V (Pa+b+c+d+e+2)|. If . > 0, then . R3(Ha,b,c,d,e)=1+ W0 > 1. However, R3(Pn) is always smaller than 1. By[8], there are 8 cases (out of the 11)for whichin[8]itwasprovedthat. > 0 (we remark that P is used instead of . in[8]). These are the cases: 1. (case3in[8]) a, c . 2, b = d =1, e . 1; 2. (case4in[8]) a, b . 2, c = d =1, e . 1; K.Hrin¡akov´aetal.:Ona ´conjectureabouttheratioofWienerindexiniteratedlinegraphs 3. (case5in[8]) a . 2, b = c = d =1, e . 1; 4. (case7in[8]) a, b, c . 2, d =1, e =0; 5. (case8in[8]) a, c . 2, b = d =1, e =0; 6. (case9in[8]) a, b . 2, c = d =1, e =0; 7. (case10in[8]) a . 2, b = c = d =1, e =0; 8. (case11in[8]) a = b = c = d =1, e . 0. By Claim1itsuffcesto considerthe remaining three cases. We proceed analogously as in the proof of Theorem1.9. Hence, we prove that when |V (Ha,b,c,d,e)| = |V (Pn)|, that is when n = a + b + c + d + e +2, then R3(Ha,b,c,d,e) > R3(Pn). This inequality is equivalent to .(n - 2)(n - 3)(n - 4) 1+ > W0 (n + 1)n(n - 1) and after multiplyingby denominators also to . .(n + 1)n(n - 1) + W0 (n + 1)n(n - 1) - (n - 2)(n - 3)(n - 4) > 0. (2.8) Now we consider the remaining three cases. Case 1: a, b, c, d . 2, e . 1. In[8]wehave 2. = 7(a+b+c+d+e)2 - 20(ab+ac+ad+bc+bd+cd) - 10(ae+be+ce+de) + 5(a+b+c+d) + 65e + 234. (2.9) Denote D = 11 cd(a - b)2(a + b)+ bd(a - c)2(a + c)+ ad(b - c)2(b + c)  + bc(a - d)2(a + d)+ ac(b - d)2(b + d)+ ab(c - d)2(c + d) . Observe that D . 0. Now substitute(2.9)and(2.7)into the left-hand side of(2.8)and delete D. When we expand the resulting expression, all the coeffcients will be posi­tive. Since the constant term is 708, which is strictly positive,(2.8)is satisfed and so R3(Ha,b,c,d,e) >R3(Pa+b+c+d+e+2). Case 2: a, b, c . 2, d =1, e . 1. From[8]wehave 22 . = 3(a +b2+c +e 2) - 3(ab+ac+bc)+(ae+be)+2ce - 2(a + b) - c + 28e + 97. In[8]itwas shown thatife . 2 then . > 0. By Claim 1, R3(Ha,b,c,1,e) >R3(Pa+b+c+e+3) in this subcase, so it suffces to restrict ourselves to e =1.For e =1 we obtain 2 . = 3(a +b2+c 2) - 3(ab+ac+bc) - a - b + c + 128. (2.10) Nowsubstitute(2.10)and(2.7)withe =1 intothe left-handsideof(2.8). Whenweexpand the resulting expression, all the coeffcients will be positive. Since the constant term is 8280, whichis strictly positive,(2.8)is satisfed and soR3(Ha,b,c,1,1) >R3(Pa+b+c+4). Case 3: a, b, c, d . 2, e =0. In[8]we have . = 4(a+b+c+d)2 - 11(ab+ac+ad+bc+bd+cd) + 3(a+b+c+d) + 137. (2.11) Denote D = 10 cd(a - b)2(a + b)+ bd(a - c)2(a + c)+ ad(b - c)2(b + c)  + bc(a - d)2(a + d)+ ac(b - d)2(b + d)+ ab(c - d)2(c + d) . Observe that D . 0. Now substitute(2.11)and(2.7)into the left-hand side of(2.8) and delete D. When we expand the resulting expression, all the coeffcients will be pos­itive. Since the constant term is 828, which is strictly positive,(2.8)is satisfed and so R3(Ha,b,c,d,0) >R3(Pa+b+c+d+2). This completes the proof. References [1] F. Buckley, Mean distance in line graphs, in: F. Hoffman, K. B. Reid, R. C. Mullin and R. G. Stanton (eds.), Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing,VolumeI,Utilitas Mathematica Publishing,Winnipeg, Manitoba, 1981 pp. 153–162,heldat LouisianaStateUniversity,BatonRouge, Louisiana,March2 –5,1981. [2] N. Cohen, D. Dimitrov, R. Krakovski, R. Skrekovski and V. ¡Vuka¡sinovi´c, On Wiener index of graphs and their line graphs, MATCH Commun. Math. Comput. Chem. 64 (2010), 683–698, http://match.pmf.kg.ac.rs/electronic_versions/ Match64/n3/match64n3_683-698.pdf. [3]A.A.DobryninandL.S. Mel’nikov,Wienerindexoflinegraphs,in:I.GutmanandB. Furtula (eds.), Distance in Molecular Graphs – Theory, University of Kragujevac, Kragujevac, vol­ume 12 of Mathematical Chemistry Monographs, pp. 85–121, 2012, http://match.pmf. kg.ac.rs/mcm12.html. [4] J. K. Doyle and J. E. Graver, Mean distance in a graph, Discrete Math. 7 (1977), 147–154, doi:10.1016/0012-365x(77)90144-3. [5] R. C. Entringer, D. E. Jackson and D. A. Snyder, Distance in graphs, Czechoslovak Math.J. 26 (1976), 283–296, https://dml.cz/handle/10338.dmlcz/101401. [6] I. Gutman, Distance of line graphs, Graph Theory NotesN.Y. 31 (1996), 49–52. [7] I. Gutman and I. G. Zenkevich, Wiener index and vibrational energy, Z. Naturforsch. A 57 (2002), 824–828, http://www.znaturforsch.com/aa/v57a/s57a0824.pdf. ¡ [8] M. Knor, M. Ma¡caj, P. Poto¡cnik and R. Skrekovski, Complete solution of equation W (L3(T )) = W (T ) for the Wiener index of iterated line graphs of trees, Discrete Appl. Math. 171 (2014), 90–103, doi:10.1016/j.dam.2014.02.007. [9] M. Knor,P. Poto¡cnikandR. ¡ Skrekovski, On a conjecture about Wiener index in iterated line graphs of trees, Discrete Math. 312 (2012), 1094–1105, doi:10.1016/j.disc.2011.11.023. [10] M. Knor, P. Poto¡cnik and R. ¡ Skrekovski, The Wiener index in iterated line graphs, Discrete Appl. Math. 160 (2012), 2234–2245, doi:10.1016/j.dam.2012.04.021. [11] M. Knor,P. Poto¡Skrekovski,Wiener indexof iterated line graphsof trees homeo­ cnik and R. ¡morphic to H, Discrete Math. 313 (2013), 1104–1111, doi:10.1016/j.disc.2013.02.005. K.Hrin¡´aetal.:Ona conjectureabouttheratioofWienerindexiniteratedlinegraphs akov´ ¡ homeomorphic to the claw K1,3, Ars Math. Contemp. 6 (2013), 211–219, https:// amc-journal.eu/index.php/amc/article/view/250. [12] M. Knor, P. Poto¡cnik and R. Skrekovski, Wiener index of iterated line graphs of trees [13] M.KnorandR. ¡Skrekovski,Wienerindexofline graphs,in:M. DehmerandF. Emmert-Streib (eds.), Quantitative Graph Theory: Mathematical Foundations and Applications, CRC Press, Boca Raton, FL, Discrete Mathematics and its Applications (Boca Raton), pp. 279–301, 2015. [14] M. Knor, R. ¡Skrekovski and A.Tepeh, An inequality between the edge-Wiener index and the Wiener index of a graph, Appl. Math. Comput. 269 (2015), 714–721, doi:10.1016/j.amc.2015. 07.050. [15] M. Knor, R. ¡Skrekovski andA.Tepeh, Mathematical aspectsof Wiener index, Ars Math. Con-temp. 11 (2016), 327–352, https://amc-journal.eu/index.php/amc/article/ view/795. [16] J. Plesn´ik, On the sum of all distances in a graph or digraph, J. Graph Theory8 (1984), 1–21, doi:10.1002/jgt.3190080102. [17] H.Wiener, Structural determination of paraffn boiling points, J. Am. Chem. Soc. 69 (1947), 17–20, doi:10.1021/ja01193a005. [18] K. Xu, M. Liu, K. Ch. Das, I. Gutman and B. Furtula, A survey on graphs ex­tremal with respect to distance-based topological indices, MATCH Commun. Math. Com-put. Chem. 71 (2014), 461–508, http://match.pmf.kg.ac.rs/electronic_ versions/Match71/n3/match71n3_461-508.pdf.