Several Problems On Topological Invariants And Structure Properties Of Graphs

Historically, graph theory has a close relation with chemistry. A chemical structure canbe conveniently represented by a graph (chemical graph or molecular graph). Topologicalindices are graph invariants used in theoretical chemistry, which are real numbers related toa graph or molecular graph and they do not depend on the labeling or the pictorial represen-tation of a graph. In order to model properties of molecular graphs, many topological indiceshave been designed by mathematicians and theoretical chemists and many important and niceresults concerning on topological indices have been obtained.We put forward our investigation in terms of topological indices. In Chapter1, we intro-duce the background and the process of the investigation related to this thesis as well as ourmain results obtained. The proceeding five chapters are the main contributions of this thesis.Define κ(G):=κ, λ(G):=λ and δ(G):=δ. In1932, the authors proved a well-known theorem in [H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J.Math.54(1932)150-168]: Let G be any graph, then κ≤λ≤δ. Subsequently, the problemdetermining whether a given graph is maximally edge-connected (λ=δ) or not has attractedthe attention of many researchers [A. Hellwing, L. Volkmann, Maximally edge-connected andvertex-connected graphs and digraphs: A survey, Discrete Math.308(2008)3265-3296]. InChapter2, we proved: for any real number α≤1, if R01α(G)<2δα δα++(δ1)(δ+1)α+(δ1)(n δ1)α+(2n3δ2)(n δ2)α, then λ=δ (Theorem2.1.1); let G be atriangle-free graph, if R0α(G)<δα δα+1+(δ1)(δ+1)α+2α(δ1)(n2δ+2)α+2α(2n5δ+1)(n2δ)α, we have λ=δ (Theorem2.1.3). It can be seen that our results generalizethose given by P. Dankelmann et al. in [P. Dankelmann, A. Hellwig, L. Volkmann, Inversedegree and edge-connectivity, Discrete Math.309(2009)2943-2947]. Similar theorems havebeen established for0<α <1and the extremal graphs have completely characterized (seeTheorem2.2.1and Theorem2.2.2). We also derived a sufficient condition for a graph to besuper edge-connected (Theorem2.3.6) which generalizes a result given by Y. Tian et al. in[Y. Tian, L. Guo, J. Meng, C. Qian, Inverse degree and super edge-connectivity, InternationalJournal of Comput. Math.89:6(2012)752-759]. Problem2.3.8and problem2.3.9are themain task in our future research. In Chapter3, we proposed the concept of [Q, k]-decomposition problems, and main-ly studied the [Q, k]-decomposition problems for the H-index, W W-index, R0α-index,RDD+-index, RDD-index and χα-index, respectively. Several results such as7(n)2≤W W (3; K)(n)n)≤2(n+24+2+4(n1) have been presented and all of them are bestpossible. By comparing previous results derived by L. Zhang and B. Wu in [L. Zhang, B.Wu, The Nordhaus-Gaddum-type inequalities for some chemical indices, MATCH Commun.Math. Comput. Chem.54(2005)189-194], this suggests that Theorem3.3.3is a commongeneralization of Zhang’s results. We also leave several open problems (Conjecture3.2.17etc.) for our further research.In Chapter4, we derived an equivalent definition of Co-PI index and explored somemathematical properties. The spectral properties of the Co-PI matrix and Laplacian matrixfor Cartesian product graphs were presented: σ′kl(G1G2)=|V1|σ′l(G2)+|V2|σ′k(G1) andμ′kl(G1G2)=|V1|μ′l(G2)+|V2|μ′k(G1), where k=1,2,···,|V1|, l=1,2,···,|V2|. Wealso supplied the explicit formulae for the Co-PI index of Cartesian product graphs (see The-orem4.3.1and Theorem4.3.3for details).In Chapter5, we first proposed the definitions of Q-maximized and Q-minimizedproblems, and then investigated the extremal value of RDD-index with a given vertex-connectivity κ and proved: RDD (G)≤21n4217n3+21(κ3κ2+3κ+18)n2+21(κ311κ20)n+21(κ2+9κ+8), the bound is best possible. We also obtained a resultfor RDD+-maximized and RDD-maximized problem, respectively, with a given matchingnumber β (see Theorem5.1.3and Theorem5.2.9, respectively). A similar conclusion waspresented for RDD+-maximized problem with a given impendence number α, the extremalgraphs were also completely determined (Theorem5.3.4).In the last Chapter, we reported the line graph of the subdivision of Tadpole graph, Wheelgraph and Ladder graph, respectively. Some exact expressions of several topological indicesfor those graphs mentioned above were presented. This suggest a common generalization ofthe result derived by P. S. Ranjini in [P. S. Ranjini, V. Lokesha, I. N. Cangu¨e, On the Zagrebindices of the line graphs of the subdivision graphs, Appl. Math. Comput.218(2011)699-701], respectively.