图的染色数和Estrada指数
|
摘要
谱图理论主要是研究图的结构性质和图的谱性质之间的联系,期望通过图的谱性质来描述图的结构性质.谱图理论在结构化学中的一个重要应用是：通过对化学物质结构建立图模型,应用图的特征值来刻画分析该化学物质的物理性质或化学性质.在这种背景下,许多研究者提出了一些基于图谱的分子拓扑指数.
2000年,由E.Estrada引入衡量化学分子长链折叠情况的一个指标,这个指标后来被研究者称为Estrada指数.该指标提出以后引起了广泛地关注,成为国内外学者的研究热点.本文从两个方面综述了近年来Estrada指数的研究成果,研究了Estrada指数与一个重要图参数—染色数之间的关系,刻画了给定染色数的图类中Estrada指数取到极大的图,部分刻画了在该图类中Estrada(?)指数取到极小的图.
本文的组织结构如下.第一章主要介绍了Estrada指数的研究背景和意义,以及本文所用到的一些基本概念和记号.第二章从两个方面综述了谱图理论领域Estrada指数最新研究成果.第三章首先介绍了一些基本引理,其次给出了给定染色数的Estrada(?)指数的极大图,最后探讨了顶点数与染色数相差1的Estrada(?)指数的极小图.
Spectral graph theory mainly discuss relations between the structural property and the spectral property of graphs by using the spectra of graphs. An important application of spectral graph theory in structural chemistry is that one can characterize the chemical or physical properties of chemical molecule structure by using the spectra of graphs corre-sponding to chemical molecule structure. So, researchers propose some molecular topological index based on spectrum of graphs.
In2000, an index was introduced by E.Estrada to measure the degree of folding of a protein, which was called the Estrada index by other researchers. In recent years, the Estrada index have became a hot topic of spectral graph theory, have received much attention. In this dissertation, we survey the recent development of Estrada index from two aspects, discuss the relationship between the Estrada index and the chromatic number which is an important graph parameter, characterize the graph whose Estrada index attains maximum among all graphs with fixed order and given chromatic number, and partially characterize the minimizing graph in this graph set.
The dissertation is organized as follows. In Charter one, we briefly introduce the back-ground of the Estrada index and some concepts and notations which will be used in following Charter. In Charter two, the recent development of the Estrada index is surveyed from two aspects. In final Charter, we characterize the maximizing graph among all graphs with fixed order and given chromatic number, and characterize the minimizing graph among all graphs whose chromatic number is one less than its order.
2000年,由E.Estrada引入衡量化学分子长链折叠情况的一个指标,这个指标后来被研究者称为Estrada指数.该指标提出以后引起了广泛地关注,成为国内外学者的研究热点.本文从两个方面综述了近年来Estrada指数的研究成果,研究了Estrada指数与一个重要图参数—染色数之间的关系,刻画了给定染色数的图类中Estrada指数取到极大的图,部分刻画了在该图类中Estrada(?)指数取到极小的图.
本文的组织结构如下.第一章主要介绍了Estrada指数的研究背景和意义,以及本文所用到的一些基本概念和记号.第二章从两个方面综述了谱图理论领域Estrada指数最新研究成果.第三章首先介绍了一些基本引理,其次给出了给定染色数的Estrada(?)指数的极大图,最后探讨了顶点数与染色数相差1的Estrada(?)指数的极小图.
Spectral graph theory mainly discuss relations between the structural property and the spectral property of graphs by using the spectra of graphs. An important application of spectral graph theory in structural chemistry is that one can characterize the chemical or physical properties of chemical molecule structure by using the spectra of graphs corre-sponding to chemical molecule structure. So, researchers propose some molecular topological index based on spectrum of graphs.
In2000, an index was introduced by E.Estrada to measure the degree of folding of a protein, which was called the Estrada index by other researchers. In recent years, the Estrada index have became a hot topic of spectral graph theory, have received much attention. In this dissertation, we survey the recent development of Estrada index from two aspects, discuss the relationship between the Estrada index and the chromatic number which is an important graph parameter, characterize the graph whose Estrada index attains maximum among all graphs with fixed order and given chromatic number, and partially characterize the minimizing graph in this graph set.
The dissertation is organized as follows. In Charter one, we briefly introduce the back-ground of the Estrada index and some concepts and notations which will be used in following Charter. In Charter two, the recent development of the Estrada index is surveyed from two aspects. In final Charter, we characterize the maximizing graph among all graphs with fixed order and given chromatic number, and characterize the minimizing graph among all graphs whose chromatic number is one less than its order.
引文
[1]T. Aleksic, I. Gutman, M. Petrovi6, Estrada index of iterated line graphs, Bull. Acad. Serbe Sci. Arts(Cl. Math. Natur.).,134(2007),33-41.
[2]F. Buckley, Iterated line graphs, Congr. Numer.,33(1981),390-394.
[3]F. Buckley, The size of iterated line graphs, Graph Theory Notes New York.,25(1993),33-36.
[4]D. Cvetkovic, M. Doob, and II. Sachs. Spectra of Graphs-Theory and Application, Academic Press, Inc., New York.,1980.
[5]R. Carbo-Dorca, Smooth function topological structure descriptors based on graph-spectra, J. Math. Chem.,44(2008),373-378.
[6]K. Das, S. Lee, On the Estrada index conjecture, Linear Algebra Appl,431(2009),1351-1359.
[7]J. A. de la Pena, I. Gutman, and J. Rada. Estimating the Estrada index, Linear Alegbra and its Applications.,427(2007),70-76.
[8]H. Deng, A proof of a conjecture on the Estrada index, Match communications in mathematical and in computer chemistry.,62(2009),599-606.
[9]H. Deng, A note on the Estrada index of trees, Match communications in mathematical and in computer chemistry.,62(2009),607-610.
[10]H. Deng, S. Radenkovic and I. Gutman, The Estrada index, in:D. Cvetkovic, I. Gutman (Eds.), Applications of Graph Spectra (Math. Inst., Belgrade.)., (2009),123-140.
[11]Z. B. Du, B. Zhou, The Estrada index of trees, Linear Algebra Appl.,435(2011),2462-2467.
[12]Z. B. Du, B. Zhou, On the Estrada index of graphs with given number of cut edges, Electron. J. Linear Algebra.,22(2011),586-592.
[13]Z. B. Du, Z. Z. Liu, On the Estrada and Laplacian Estrada indices of graphs, Linear Algebre Appl.,435(2011),2065-2076.
[14]Z. B. Du, B. Zhou, The Estrada index of unicyclic graphs, Linear Algebra Appl.,436(2012), 3149-3159.
[15]Z. B. Du, B. Zhou, R. D. Xing, On maximum Estrada indices graphs with given parameters, Linear Algebra and its Applications.,436(2012),3767-3772.
[16]E. Estrada, Characterization of 3D molecular structure, Chem. Phys. Lett.,319(2000),713-718.
17] E. Estrada, Characterization of the folding degree of proteins, Bioinformatics.,18(2002),697-704.
[18]E. Estrada, Characterization of the amino acid contribution to the folding degree of proteins, Proteins.,54(2004),727-737.
[19]E. Estrada, J. A. Rodriguez-Velazquez, Spectral measures of bipartivity in complex networks, Phys. Rev. E.,72(2005),046105-1-046105-6.
[20]E. Estrada, J. A. Rodriguez-Velazquez, Subgraph centrality in complex networks, Phys. E., 71(2005),056103-1-056103-9.
[21]E. Estrada, J. A. Rodriguez-Velazquez, M. Randic, Atomic branching in molecules, Int. J. Quantum Chem.,106(2006),823-832.
[22]E. Estrada, Topological structural classes of complex networks, Phys. Rev. E.,75(2007), 016103-1-016103-12.
[23]E. Estrada, N. Hatano, Statistical-mechanical approach to subgraph centrality in complex networks, Chem. Phys. Lett.,439(2007),247-251.
[24]E. Estrada, Atom-bond connectivity and the energetic of branches alkanes, Chem. Phys. Lett., 463(2008),422-425.
[25]G. H. Fath-Tabar, A. R. Ashrafi, New upper bounds for Estrada index of bipartite graphs, Linear Algebra and its Applications.,435(2011),2607-2611.
[26]L. H. Feng, Q. Li, X. D. Zhang, Spectral radii of graphs with given chromatic number, Applied Mathematics Letters.,20(2007),158-162.
[27]D. Gomez, E. Gonzalez-Aranguena, C. Manuel. Centrality and power in social network a game theoretic approach, Mathematical Social Sciences.,2003(46)(1),27-54.
[28]A. Gursoy, O. Keskin, R. Nussinov, Topological properties of protein interaction networks from a structural perspective, Biochem. Soc.Trans.,36(2008),1398-1403.
[29]I. Gutman, The energy of a graph:Old and new results, in:A. Betten, A. Kohnert, R. Laue, A. Wassermann(Eds.), Algebraic Combinatorics and Applications, Springer-Verlag, Berlin., 2001, pp.196-211.
[30]I. Gutman, S. Radenkovic, Estrada index of benzenoid hydrocarbons, Z. Naturforschung., 62a(2007),254-258.
[31]I. Gutman, S; Radenkovic, A. Graovac, D. Plavsic, Monte Carlo approach to Estrada index, Chem. Phys. Lett.,446(2007),233-236.
[32]I. Gutman, S. Radenkovic, A lower bound for the Estrada index of bipartite molecular graphs, Kragujevac J. Sci.,29(2007),67-72.
[33]I. Gutman, E. Estrada, J. A. Rodriguez-Velazquez, On a graph spectrum based structure descriptor, Croat. Chem. Acta.,80(2007),151-154.
[34]I. Gutman, A. Graovac, Estrada index of cycles and paths, Chem. Phys. Lett.,436(2007), 294-296.
[35]I. Gutman, Lower bounds for Estrada index, Publ. Inst. Math. (Beograd)(N.S.).,83(2008), 1-7.
[36]H. Hosoya, Topologiesl index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons. Bull. Chem. Soc. Jpn.,44(1971),2332-2339.
[37]A. liic, D. Stevanovic, The Estrada index of chemical trees, J. Math. Chem.,47(2010),305-314.
[38]J. Li, W. C. Shiu, A. Chang, On the laplacian Estrada index of a graph, Appl. Anal. Discrete Math.,3(2009),147-156.
[39]J. Li, X. L. L, L. Sh. Wang, The minimal Estrada index of trees with two maximum degree vertices, Match Commum. Math. Comput. Chem.,64(2010),799-810.
[40]J. Li, A note on the maximal Estrada index of trees with a given bipartition, Match Commum. Math. Comput. Chem.,66(2011),765-768.
[41]C. Y. Lin, C. H. Chin, H. H. Wu, S. H. Chen, C. W. Ho, M. T. Ko, Hubs objects analyzer-a framework of interactome hubs identification for network biology, Nucleic Acids Res.,36(2008), 438-443.
[42]J. P. Liu, B. L. Liu, Bounds of the Estrada index of graphs, Appl. Math. J. Chinese Univ., 25(2010),325-330.
[43]A. Platzer, P. Perco, A. Lukas, B. Mayer, Characterization of protein-interaction networks in tumors, BMC Bioinformatics.,8(2007),224-229.
[44]H. Prodinger, R. F. Tichy, Fibonacci numbers of graphs, Fibonacci Quart.,20(1982),16-21.
[45]H. Wiener. Structural determination of paraffin boiling points, J. Amer. Chem. Soc.,69(1947), 17-20.
[46]叶德泳.计算机辅助药物设计导论[M].北京：化学工业出版社,2004.
[47]J. B. Zhang, B. Zhou, J. P. Li, On Estrada index of trees, Linear Algebra Appl.,434(2011), 215-223.
[48]H. Zhao, Y. jia, On the Estrada index of bipartite graph, Match.,61(2009),495-501.
[49]B. Zhou, On Estrada index, MATCH Commum. Math. Comput. Chem.,60(2008),485-492.
[50]B. Zhou, N. Trinajstic, Estrada index of bipartite graphs, Int. J. Chem. Model.,1(2008), 387-394.
[51]B. Zhou, I. Gutman, More on the Laplacian Estrada index, Appl. Anal. Discrete Math., 3(2009),371-378.
[52]B. Zhou, On sum of powers of Laplacian eigenvalues and Laplacian Estrada index of graphs, Match.,62(2009),611-619.
[2]F. Buckley, Iterated line graphs, Congr. Numer.,33(1981),390-394.
[3]F. Buckley, The size of iterated line graphs, Graph Theory Notes New York.,25(1993),33-36.
[4]D. Cvetkovic, M. Doob, and II. Sachs. Spectra of Graphs-Theory and Application, Academic Press, Inc., New York.,1980.
[5]R. Carbo-Dorca, Smooth function topological structure descriptors based on graph-spectra, J. Math. Chem.,44(2008),373-378.
[6]K. Das, S. Lee, On the Estrada index conjecture, Linear Algebra Appl,431(2009),1351-1359.
[7]J. A. de la Pena, I. Gutman, and J. Rada. Estimating the Estrada index, Linear Alegbra and its Applications.,427(2007),70-76.
[8]H. Deng, A proof of a conjecture on the Estrada index, Match communications in mathematical and in computer chemistry.,62(2009),599-606.
[9]H. Deng, A note on the Estrada index of trees, Match communications in mathematical and in computer chemistry.,62(2009),607-610.
[10]H. Deng, S. Radenkovic and I. Gutman, The Estrada index, in:D. Cvetkovic, I. Gutman (Eds.), Applications of Graph Spectra (Math. Inst., Belgrade.)., (2009),123-140.
[11]Z. B. Du, B. Zhou, The Estrada index of trees, Linear Algebra Appl.,435(2011),2462-2467.
[12]Z. B. Du, B. Zhou, On the Estrada index of graphs with given number of cut edges, Electron. J. Linear Algebra.,22(2011),586-592.
[13]Z. B. Du, Z. Z. Liu, On the Estrada and Laplacian Estrada indices of graphs, Linear Algebre Appl.,435(2011),2065-2076.
[14]Z. B. Du, B. Zhou, The Estrada index of unicyclic graphs, Linear Algebra Appl.,436(2012), 3149-3159.
[15]Z. B. Du, B. Zhou, R. D. Xing, On maximum Estrada indices graphs with given parameters, Linear Algebra and its Applications.,436(2012),3767-3772.
[16]E. Estrada, Characterization of 3D molecular structure, Chem. Phys. Lett.,319(2000),713-718.
17] E. Estrada, Characterization of the folding degree of proteins, Bioinformatics.,18(2002),697-704.
[18]E. Estrada, Characterization of the amino acid contribution to the folding degree of proteins, Proteins.,54(2004),727-737.
[19]E. Estrada, J. A. Rodriguez-Velazquez, Spectral measures of bipartivity in complex networks, Phys. Rev. E.,72(2005),046105-1-046105-6.
[20]E. Estrada, J. A. Rodriguez-Velazquez, Subgraph centrality in complex networks, Phys. E., 71(2005),056103-1-056103-9.
[21]E. Estrada, J. A. Rodriguez-Velazquez, M. Randic, Atomic branching in molecules, Int. J. Quantum Chem.,106(2006),823-832.
[22]E. Estrada, Topological structural classes of complex networks, Phys. Rev. E.,75(2007), 016103-1-016103-12.
[23]E. Estrada, N. Hatano, Statistical-mechanical approach to subgraph centrality in complex networks, Chem. Phys. Lett.,439(2007),247-251.
[24]E. Estrada, Atom-bond connectivity and the energetic of branches alkanes, Chem. Phys. Lett., 463(2008),422-425.
[25]G. H. Fath-Tabar, A. R. Ashrafi, New upper bounds for Estrada index of bipartite graphs, Linear Algebra and its Applications.,435(2011),2607-2611.
[26]L. H. Feng, Q. Li, X. D. Zhang, Spectral radii of graphs with given chromatic number, Applied Mathematics Letters.,20(2007),158-162.
[27]D. Gomez, E. Gonzalez-Aranguena, C. Manuel. Centrality and power in social network a game theoretic approach, Mathematical Social Sciences.,2003(46)(1),27-54.
[28]A. Gursoy, O. Keskin, R. Nussinov, Topological properties of protein interaction networks from a structural perspective, Biochem. Soc.Trans.,36(2008),1398-1403.
[29]I. Gutman, The energy of a graph:Old and new results, in:A. Betten, A. Kohnert, R. Laue, A. Wassermann(Eds.), Algebraic Combinatorics and Applications, Springer-Verlag, Berlin., 2001, pp.196-211.
[30]I. Gutman, S. Radenkovic, Estrada index of benzenoid hydrocarbons, Z. Naturforschung., 62a(2007),254-258.
[31]I. Gutman, S; Radenkovic, A. Graovac, D. Plavsic, Monte Carlo approach to Estrada index, Chem. Phys. Lett.,446(2007),233-236.
[32]I. Gutman, S. Radenkovic, A lower bound for the Estrada index of bipartite molecular graphs, Kragujevac J. Sci.,29(2007),67-72.
[33]I. Gutman, E. Estrada, J. A. Rodriguez-Velazquez, On a graph spectrum based structure descriptor, Croat. Chem. Acta.,80(2007),151-154.
[34]I. Gutman, A. Graovac, Estrada index of cycles and paths, Chem. Phys. Lett.,436(2007), 294-296.
[35]I. Gutman, Lower bounds for Estrada index, Publ. Inst. Math. (Beograd)(N.S.).,83(2008), 1-7.
[36]H. Hosoya, Topologiesl index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons. Bull. Chem. Soc. Jpn.,44(1971),2332-2339.
[37]A. liic, D. Stevanovic, The Estrada index of chemical trees, J. Math. Chem.,47(2010),305-314.
[38]J. Li, W. C. Shiu, A. Chang, On the laplacian Estrada index of a graph, Appl. Anal. Discrete Math.,3(2009),147-156.
[39]J. Li, X. L. L, L. Sh. Wang, The minimal Estrada index of trees with two maximum degree vertices, Match Commum. Math. Comput. Chem.,64(2010),799-810.
[40]J. Li, A note on the maximal Estrada index of trees with a given bipartition, Match Commum. Math. Comput. Chem.,66(2011),765-768.
[41]C. Y. Lin, C. H. Chin, H. H. Wu, S. H. Chen, C. W. Ho, M. T. Ko, Hubs objects analyzer-a framework of interactome hubs identification for network biology, Nucleic Acids Res.,36(2008), 438-443.
[42]J. P. Liu, B. L. Liu, Bounds of the Estrada index of graphs, Appl. Math. J. Chinese Univ., 25(2010),325-330.
[43]A. Platzer, P. Perco, A. Lukas, B. Mayer, Characterization of protein-interaction networks in tumors, BMC Bioinformatics.,8(2007),224-229.
[44]H. Prodinger, R. F. Tichy, Fibonacci numbers of graphs, Fibonacci Quart.,20(1982),16-21.
[45]H. Wiener. Structural determination of paraffin boiling points, J. Amer. Chem. Soc.,69(1947), 17-20.
[46]叶德泳.计算机辅助药物设计导论[M].北京：化学工业出版社,2004.
[47]J. B. Zhang, B. Zhou, J. P. Li, On Estrada index of trees, Linear Algebra Appl.,434(2011), 215-223.
[48]H. Zhao, Y. jia, On the Estrada index of bipartite graph, Match.,61(2009),495-501.
[49]B. Zhou, On Estrada index, MATCH Commum. Math. Comput. Chem.,60(2008),485-492.
[50]B. Zhou, N. Trinajstic, Estrada index of bipartite graphs, Int. J. Chem. Model.,1(2008), 387-394.
[51]B. Zhou, I. Gutman, More on the Laplacian Estrada index, Appl. Anal. Discrete Math., 3(2009),371-378.
[52]B. Zhou, On sum of powers of Laplacian eigenvalues and Laplacian Estrada index of graphs, Match.,62(2009),611-619.