摘要
图的能量定义为图连接矩阵的所有特征根的绝对值之和.在化学图论中,研究具有极值能量的图具有十分重要的理论意义和应用价值.图的能量越大(小),相应化合物的热力学稳定性越强(弱).
共轭分子图根据其是否具有Kekuléan结构,可分为Kekuléan分子图和非Kekuléan分子图.在图论中,Kekuléan结构称为完美匹配.具有完美匹配的图具有许多化学的性质.例如,是否具有完美匹配对于芳香族系统的稳定性是及其重要的.
基于具有完美匹配的图在化学上的重要性,本文研究此类图的极值能量图问题.记此类图的顶点个数为2n.主要工作和结果有以下五部分.
(1).考虑了最大度不超过3,并且具有完美匹配的树依能量从小到大的排序问题.我们采用了比文献(Li H.J.Math.Chem.25(1999)145-169)更加简捷的方法,当n+1≥14时,得到了2n-2r-5个具有较小能量的树并加以排序,其中r由n+1≡r(mod 4)确定.这个结果比文献(Li 1999)中得到的具有较小能量树的个数多了n-r-6个.当6≤n+1≤13时,我们也分别得到了许多具有较小能量的树并加以排序.
(2).考虑了直径为d,并且具有完美匹配的树的极值能量图问题.当4≤d≤10时,分别得到了极小能量图.对于d=5,当n=2h和n=2h+1时,还分别得到了(1+(?))/2和(?)+1个具有较大能量的树并进行了排序,其中h是不小于2的正整数.
(3).考虑了具有完美匹配的树依能量从小到大的排序问题.我们运用了比文献(ZhangF.J.&Li H.Discrete Appl.Math.92(1999)71-84)更加简单的证明方法,得到了此类图的极小,次二小和次三小能量图.
(4).考虑了最大度不超过3,并且具有完美匹配的单圈图依Hosoya指标的排序及其极小能量图问题.首先,在四种特殊情况下,得到了这四类图依Hosoya指标从小到大的排序.接着,确定了所考虑图类中多个具有较小Hosoya指标的单圈图并加以排序.进一步地,得到了此类图的极小能量图.
(5).考虑了具有完美匹配的单圈图,得到了此类图的极小能量图.
The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. The investigation on the graphs with extremal energies is of theoretical interest and practical importance in the subject of chemical graph theory. The larger the value of enery, the greater the thermodynamic stability of the corresponding compund.
Conjugated molecules in chemistry may be classified into two groups: Kekulean and non-Kekulean molecules, depending on whether or not they possess Kekulean structures, i.e., the perfect matchings in graph theory. The graphs with perfect matchings possess many chemical properties. For example, the existence of perfect matchings is closely connected to the stability of aromatic systems.
In view of the significance of the graphs with perfect mathings in chemical graph theory, this kind of the graphs with extremal energies is investigated in this thesis. The vertex number of the graphs considered is denoted by In. The main results can be divided into five parts as follows.
Firstly, the ordering of the minimal energies of the trees with a perfect matching having degrees no greater than three is considered. By means of a simpler method than that of Li (J. Math. Chem. 25 (1999) 145-169), we obtain the first 2n - 2r - 5 trees in the increasing order of their energies within the class under consideration for n + 1≥14, where r is determined by n + 1≡r (mod 4). The number of the trees obtained here exceeds the reported result (Li 1999) by n - r - 6. We also get a lot of preceding trees in the increasing order of their energies within the class for 6≤n + 1≤13.
Secondly, the extremal energies of the trees with a perfect matching having a given diameter d are obtained. The graphs with minimal energies are given for 4≤d≤10. As d = 5, we obtain the last (1 +(?))/2 and y(?)+1 trees in the increasing order of their energies within the class under consideration for n = 2h and n = 2h + 1, respectively, where h≥2.
Thirdly, the ordering of the minimal energies of the trees with a perfect matching is studied. We employ a simpler method than that of Zhang & Li (Discrete Appl. Math. 92 (1999) 71-84) to find the trees having the minimal, the second-minimal, and the third-minimal energies.
Next, the ordering of unicyclic graphs with perfect matchings having degrees no greater than three by their Hosoya indexes is considered. Four special cases in the increasing order of their Hosoya indexes are studied. The preceding graphs in the increasing order of their Hosoya indexes are determined. Furthermore, the corresponding graphs with minimal energies are provided.
Finally, unicyclic graphs with perfect matchings having minimal energy are considered . The corresponding graph with minimal energy is mathematically verified.
引文
[1]张福基.图依能量的排序.厦门大学学报40(2001)157-162.
[2] Gutman I. & Polansky O.E. Mathematical Concepts in Organic Chemistry. Berlin:Springer-Verlag (1986).
[3] Gutman I. The energy of a graph: old and new results, in: A. Betten, A. Kohnert,R. Laue, A. Wassermann (Eds.) Algebra Combinatorics and Applications, pp. 196-211.Berlin: Springer-Verlag (2001).
[4] Gutman I. Topology and stability of conjugated hydrocarbons. The dependence of total7r-electron energy on molecular topology. J. Serb. Chem. Soc. 70 (2005) 441-456.
[5]唐熬庆,江元声等.分子轨道图形理论.北京:科学出版社(1980).
[6] Bonchev D. & Rouvray D.H. Chemical Graph Theory: Introduction and Fundamentals.Gordon and Breach Science Pulishers (1990).
[7] Narumi H. & Hosoya H. Topological index and thermodynamic properties. III. Classification of various topological aspects of properties of acyclic saturated hydrocarbons. Bull. Chem. Soc. Japan 58 (1985) 1778-1786.
[8] Gutman I. & Zhang F. J. On the ordering of graphs with respect to their matching numbersDiscrete Appl. Math. 15 (1986) 25-33.
[9] Hosoya H. Introduction to Graph Theory. In: D. Bonchev and O. Mekenyan ed. Graph Theoretical Approaches to Chemical Reactivity, p. 30, Kluwer Academic Publishers (1994).
[10] Trinajstic N. Chemical Graph Theory, Vol. 2. CRC Press (1983).
[11] Gutman I. Total 7r-electron energy of benzenoid hydrocarbon, in: Topics In Curr. Chem. Vol. 162: Advance in the Theory of Benzenoid Hydrocarbons II. pp. 29-63, Berlin: Springer (1992).
[12] Gutman I. Note on the Coulson integral formula. J. Math. Chem. 39 (2005) 259-266.
[13] Cvetkovic D.M., Doob M. & Sachs H. Spectra of Graphs Theory and Application. New York: Academic Press (1980).
[14] Hall G.G. The bond orders of alternant hydrocarbon molecules. Proc. Roc. Soc. London A 229 (1955) 251-259.
[15] McClelland B.J. Properties of latent roots of a matrix-estimation of electron energies. J. Chem. Phys. 54 (1971) 640-643.
[16] England W. & Ruedenberg K. Why is delocalization energy negative and why is it proportional to number of electron. J. Amer. Chem. Soc. 95 (1973) 8769-8775.
[17] Gutman I., Nedeljkovic L.J. & Teodorovic A.V. Bull. Soc. Chim. Beograd 48 (1983) 495.
[18] Gutman I., Soldatovic T. k Vidovic D. The energy of a graph and its size dependence. AMonte Carlo approach. Chem. Phys. Lett. 297 (1998) 428-432.
[19] Gutman I. Bounds for total 7r-electron energy. Chem. Phys. Lett. 24 (1974) 283-285.
[20] Gutman I. Bounds for total 7r-electron energy of polymethines. Chem. Phys. Lett. 50(1977) 488-490.
[21] Gutman I. Bounds for total 7r-electron energy. Croat. Chem. Ada 51 (1978) 299-306.
[22] Gutman I. Acyclic Conjugated molecules, trees and their energies. J. Math. Chem. 1(1987) 123-143.
[23] Turker L. An upper bound for total 7r-electron energy of alternant hydrocarbons. Commun.Math. Chem. 6 (1984) 83-94.
[24] Caporossi G., Cvetkovic D., Gutman I., et al. Variable neighborhood search for extermalgraphs. 2. finding graphs with extremal energy. J. Chem. Inform. Computer. Sci. 39(1999) 984-996.
[25] Caporossi G. k Hansen P. Variable neighborhood search for extremal graphs. 1. Auto-Graphix system. Discrete Math. 212 (2000) 29-49.
[26] Koolen J.H., Moulton V. k Gutman I. Improving the McClelland inequality for totalπ-electron energy. Chem. Phys. Lett. 320 (2000) 213-216.
[27] Koolen J.H. k Moulton V. Maximal Energy Graphs. Adv. Appl. Math. 26 (2001) 47-52.
[28] Koolen J.H. k Moulton V. Maximal Energy bipartite Graphs. Graphs Combinatorics 19(2003) 131-135.
[29] Guo J.M. Sharp upper bounds for total 7r-electron energy of alternant hydrocarbons. J.Math. Chem. 43 (2008) 713-718.
[30] Zhou B. Energy of a graph. Match-Communications Math. Comput. Chem. 51 (2004)111-118.
[31] Yu A., Lu M. k Tian F. New upper bounds for the energy of graphs. Match-Communications Math. Comput. Chem. 53 (2005) 441-448.
[32] Liu H.Q., Lu M. k Tian F. Some upper bounds for the energy of graphs. J. Math. Chem.41 (2007) 45-87.
[33] Liu H. k Lu M. Sharp bounds on the spectral radius and the energy of graphs. Match-Communications Math. Comput. Chem. 59 (2008) 279-290.
[34] Gutman I. Acyclic systems with extremal Huckel π-electron energy. Theoret. Chim. Acta45 (1977) 79-87.
[35] Li Q. k Feng K. Some results about the spectral properties of graphs. J. Univ. Sci.Technol. China (1979) 53-56.
[36] Li N. & Li S. On the extremal energies of trees. Match-Communications Math. Comput.Chem. 59 (2008) 291-314.
[37] Gutman I., Raddenkovic S., Li N. et al. Extremal energy tress. Match-CommunicationsMath. Comput. Chem. 59 (2008) 315-320.
[38] Zhang F.J. & Li H. On acyclic conjugated molecules with minimal energies. Discrete Appl.Math. 92 (1999) 71-84.
[39] Li H. On minimal energy ordering of acyclic conjugated molecules. J. Math. Chem. 25(1999) 145-169.
[40] Zhang F.J. & Li H. On maximal energy ordering of acyclic conjugated molecules. DiscreteMathmatica Chem. 51 (2000) 385-392.
[41] Fujita S. Symmetry and Combinatorial Enumeration in Chemistry. Berlin: Springer(1991).
[42] Shao J.Y. & Hong Y. Bound on the smallest positive eigenvalue of a trees with perfectmatching. Chinese Sci. Bull. 37 (1992) 713-717.
[43] Zhang F.J. & Chang A. Acyclic molecules with greatest HOME-LUMO separation. Discrete Appl. Math. 98 (1999) 165-171.
[44]侯耀平.具有给定匹配大小的极小能量树. 系统科学与数学23(2003)491-494.
[45]王霄霞,郭晓峰.关于具有给定非悬挂边数的树的极小能量. 数学研究39(2006) 109-116.
[46] Yan W.G. & Ye L.Z. On the minimal energy of trees with a given diameter. Appl. Math.Lett. 18 (2005) 1046-1052.
[47] Zhou B. & Li F. On minimal energies of trees of a prescribed diameter. J. Math. Chem.39 (2006) 465-473.
[48] Ou J.P. On acyclic molecular graphs with maximal Hosoya index, energy, and short diameter . J. Math. Chem. 43 (2008) 328-337.
[49] Liu H.Q. The proof of a conjecture concerning acyclic molecular graphs with maximalHosoya index and diameter 4. J. Math. Chem. 43 (2008) 1199-1206.
[50] Ye L.Z. & Chen R.S. Ordering of trees with a given bipartition by their energies andHosoya indices. Match-Communications Math. Comput. Chem. 52 (2004) 193-208.
[51] Lin W.S., Guo X.F. & Li H.H. On the extremal energies of trees with a given maximumdegree. Match-Communications Math. Comput. Chem. 54 (2005) 363-378.
[52] Yan W.G. & Ye L.Z. On the maximal energy and the Hosoya index of a type of treeswith many pendant vertices. Match-Communications Math. Comput. Chem. 53 (2005)449-459.
[53] Yu A.M. & Lv X.Z. Minimum energy on trees with k pendent vertices. Linear Algebra and its Applications 418 (2006) 625-633.
[54] Gutman I. & Hou Y.P. Bipartite unicyclic graphs with greatest energy. Match-Communications Math. Comput. Chem. 43 (2001) 17-28.
[55] Hua H. Bipartite unicyclic graphs with large energy. Match-Communications Math. Comput . Chem. 58 (2007) 57-73.
[56] Gutman I., Furtula B. & Hua H. Bipartite unicyclic graphs with maximal, second-maximal and third-maximal energy. Match-Communications Math. Comput. Chem. 58 (2007) 75-82.
[57] Hou Y.P. Unicyclic graphs with minimal energy. J. Math. Chem. 29 (2001) 163-168.
[58] Hou Y.P., Gutman I. & Woo C.W. Unicyclic graphs with maximal energy. Linear Algebra and its Application 356 (2002) 27-36.
[59] Chen A.L., Chang A. & Shiu W.C. Energy ordering of unicycle graphs. Match-Communications Math. Comput. Chem. 55 (2006) 95-102.
[60]王文环.△(G)≤3的具有完美匹配的单圈图的能量下界. 福州大学学报30(2002) 475-478.
[61] Wang W.H., Chang A., Zhang L.Z., et al. Unicyclic Huckel molecular graphs with minimalenergy. J. Math. Chem. 39 (2006) 231-241.
[62] Li X.L., Zhang J.B. & Zhou B. On unicyclic conjugated molecules with minimal energies.J. Math. Chem. 42 (2007) 729-740.
[63] Zhou B. & Li F. Minimal energy of bipartite unicyclic graphs of a given repartition.Match-Communications Math. Comput. Chem. 54 (2005) 379-388.
[64] Hua H. On minimal energy of unicyclic graphs with prescribed girth and pendent vertices.Match-Communications Math. Comput. Chem. 57 (2007) 351-361.
[65] Hua H.B. & Wang M.L. Unicyclic graphs with given number of pendent vertices andminimal energy. Linear Algebra and its Applications 426 (2007) 478-489.
[66] Li F. & Zhou B. Minimal energy of unicyclic graphs of a given diameter. J. Math. Chem.43 (2008) 476-484.
[67] Wang M.L., Hua H.B. & Wang D.D. Minimal energy on a class of graphs. J. Math. Chem.(http://dx.doi.org/10.1007/sl0910-007-9259-l)
[68] Hou Y.P. Bicyclic graphs with minimum energy. Linear Multilinear Algebra 49 (2002)347-354.
[69] Zhang J.B. & Zhou B. On bicyclic graphs with minimal energies. J. Math. Chem. 37(2005) 423-431.
[70] Yang Y. k Zhou B. Minimal energy of bicyclic graphs of a given diameter. Match-Communications Math. Comput. Chem. 59 (2008) 321-342.
[71]张建斌,周波.恰含两个圈的二部图的能量. 高校应用数学学报A辑20(2005) 233-238.
[72] Liu Z. k Zhou B. Minimal energies of bipartite bicyclic graphs. Match-CommunicationsMath. Comput. Chem. 59 (2008) 381-396.
[73] Li S., Li X. & Zhu Z. On tricyclic graphs with minimal energy. Match-CommunicationsMath. Comput. Chem. 59 (2008) 397-419.
[74] Gutman I. k Cyvin S.J. Topics In Curr. Chem. Vol. 153: Advance in the Theory ofBenzenoid Hydrocarbons. Berlin: Springer (1990).
[75] Zhang F.J., Li Z.M. k Wang L. Hexagonal chains with minimal total π-energy. Chem.Phys. Lett. 337 (2001) 125-130.
[76] Zhang F.J., Li Z.M. & Wang L. Hexagonal chains with maximal total π-energy. Chem.Phys. Lett. 337 (2001) 131-137.
[77] Rada J. Energy ordering of catacondensed hexagonal systems. Discrete Appl. Math. 145(2005) 437-443.
[78] Rada J. & Tineo A. Polygonal chains with minimal energy. Linear Algebra and its Applications 372 (2003) 333-344.
[79]何梅芝,侯耀平,周后卿.具有极小能量的全角六角链.湖南师范大学自然科学学 报29(2006)27-31.
[80] Ren H.Z. k Zhang F.J. Double hexagonal chains with minimal total π-electron energy. J.Math. Chem. 42 (2007) 1041-1056.
[81] Zhang F.J. k Lai Z. The totally ordered ubset in a sort of Hasse graphs of trees. J.Xinjiang Univ. (1983) 12-20.
[82] Zhang F.J. k Lai Z. Three theorem of comparison of trees by their energy. Sci. Exploration3 (1983) 35-36.
[83] Gutman I. & Zhang F.J. On the quasiordering of bipartite graphs. Publications deL'institut Mathematique Nouvelle Serie, tome 40(54) (1986) 11-15.
[84] Bondy J.A. k Murty U.S.R. Graph Theory with Applications. New York: The MacmillanPress (1976).
[85] Wang X.X. k Guo X.F. On the ordering of a class of graphs with respect to their matchingnumbers. J. Math. Chem. 42 (2007) 473-480.
[86] Ren H.Z. k Zhang F.J. Double hexagonal chains with maximal Hosoya index and minimalMerrifield-Simmons index. J. Math. Chem. 42 (2007) 679-690.
[87] Hua H. Hosoya index of unicyclic graphs with prescribed pendent vertices. J. Math. Chem. 43 (2008) 831-844.
[88] Gutman I., Trinajstic N. & Zivkovic T. Theoretical studies on radialenes and related molecules. Croat. Chem. Ada 44 (1972) 501-505.
[89] Gutman I. On graph theoretical polynomials of annulenes and radialenes. Zeitschrift fur Naturforschung Sect A - J. Phys. Sci. 35 (1980) 453-457.
[90] Aihara J. Simple topological theory of aromaticity for annulenes and radialenes. Bull. Chem. Soc. Japan 53 (1980) 1751-1752.
[91] Dias J.R. Properties and relationships of conjugated polyenes having a reciprocal eigenvalue spetrum-dendralene and radialene hydrocarbons. Croat. Chem. Acta 77 (2004) 325-330.