×

Unified extremal results for \(k\)-apex unicyclic graphs (trees). (English) Zbl 1451.05123

Summary: A \(k\)-cone \(c\)-cyclic graph is the join of the complete graph \(K_k\) and a \(c\)-cyclic graph (if \(k = 0\), we get the usual connected graph). A \(k\)-apex tree (resp., \(k\)-apex unicyclic graph) is defined as a connected graph \(G\) with a \(k\)-subset \(V_k \subseteq V ( G )\) such that \(G - V_k\) is a tree (resp., unicylic graph), but \(G - X\) is not a tree (resp., unicylic graph) for any \(X \subseteq V (G)\) with \(|X| < k\). In this paper, we extend those extremal results and majorization theorems concerning connected graphs of M. Liu et al. [ibid. 255, 267–277 (2019; Zbl 1405.05090)] to \(k\)-cone \(c\)-cyclic graphs. We also use a unified method to characterize the extremal maximum and minimum results of many topological indices in the class of \(k\)-apex trees and \(k\)-apex unicyclic graphs, respectively. The later results extend the main results of F. Javaid et al. [ibid. 270, 153–158 (2019; Zbl 1426.05012)], M. Liu et al. [ibid. 284, 616–621 (2020; Zbl 1443.05042)] and partially answer the open problem of Javaid et al. [loc. cit.]. Except for the new majorization theorem, some new techniques are also established to deal with the minimum extremal results of this paper.

MSC:

05C35 Extremal problems in graph theory
05C05 Trees
05C38 Paths and cycles
05C09 Graphical indices (Wiener index, Zagreb index, Randić index, etc.)
05C07 Vertex degrees

Software:

GRAFFITI
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bıyıkoğlu, T.; Leydold, J., Graphs with given degree sequence and maximal spectral radius, Electron. J. Combin., 15, R119 (2008) · Zbl 1165.05340
[2] Bollobás, B.; Erdös, P., Graphs of extremal weights, Ars Combin., 50, 225-233 (1998) · Zbl 0963.05068
[3] Deng, H., A unified approach to the extremal Zagreb indices for trees, unicyclic graphs and bicyclic graphs, MATCH Commun. Math. Comput. Chem., 57, 597-616 (2007) · Zbl 1199.05052
[4] Estrada, E.; Torres, L.; Rodríguez, L.; Gutman, I., An atom-bond connectivity index: Modeling the enthalpy of formation of alkanes, Indian J. Chem., 37A, 849-855 (1998)
[5] Fajtlowicz, S., On conjectures of Graffiti-II, Congr. Numer., 60, 187-197 (1987) · Zbl 0713.05054
[6] Gutman, I., Degree-based topological indices, Croat. Chem. Acta, 86, 351-361 (2013)
[7] Huang, Y.; Liu, M.; Belardo, F., The general spectral radii of multicone graphs with given degree sequences (2020), submitted for publication
[8] Huang, Y.; Liu, B.; Liu, Y., The signless Laplacian spectral radius of bicyclic graphs with prescribed degree sequences, Discrete Math., 311, 504-511 (2011) · Zbl 1222.05130
[9] Javaid, F.; Jamil, M. K.; Tomescu, I., Extremal \(k\)-generalized quasi unicyclic graphs with respect to first and second Zagreb indices, Discrete Appl. Math., 270, 153-158 (2019) · Zbl 1426.05012
[10] Jiang, X.; Liu, Y.; Liu, B., A further result on majorization theorem, Linear Multilinear Algebra, 59, 957-967 (2011) · Zbl 1222.05115
[11] Li, X.; Zheng, J., A unified approach to the extremal trees for different indices, MATCH Commun. Math. Comput. Chem., 54, 195-208 (2005) · Zbl 1085.05037
[12] Liu, M., A simple approach to order the first Zagreb indices of connected graphs, MATCH Commun. Math. Comput. Chem., 63, 425-432 (2010) · Zbl 1265.05124
[13] Liu, M., The (signless Laplacian) spectral radii of connected graphs with prescribed degree sequences, Electron. J. Combin., 19, #R35 (2012) · Zbl 1266.05075
[14] Liu, M.; Cheng, K.; Tomescu, I., Some notes on the extremal \(k\)-generalized quasi-unicyclic graphs with respect to Zagreb indices, Discrete Appl. Math., 284, 616-621 (2020) · Zbl 1443.05042
[15] Liu, M.; Li, F.; Das, K. C., Ordering the Zagreb coindices of connected graphs, MATCH Commun. Math. Comput. Chem., 70, 939-948 (2013) · Zbl 1299.05058
[16] Liu, M.; Liu, B., Some results on the majorization theorem of connected graphs, Acta Math. Sin. Engl. Ser., 28, 371-378 (2012) · Zbl 1334.05066
[17] Liu, M.; Liu, B.; Das, K. C., Recent results on the majorization theory of graph spectrum and topological index theory-a survey, Electron. J. Linear Algebra, 30, 402-421 (2015) · Zbl 1323.05075
[18] Liu, M.; Xu, K.; Zhang, X.-D., Extremal graphs for vertex-degree-based invariants with given degree sequences, Discrete Appl. Math., 255, 267-277 (2019) · Zbl 1405.05090
[19] Marshall, A. W.; Olkin, I., Inequalities: Theory of Majorization and Its Applications (1979), Academic Press: Academic Press New York · Zbl 0437.26007
[20] Miličević, A.; Nikolić, S.; Trinajstić, N., On reformulated Zagreb indices, Mol. Divers., 8, 393-399 (2004)
[21] Nikolić, S.; Kovačević, G.; Miličević, A.; Trinajstić, N., The Zagreb indices 30 years after, Croat. Chem. Acta, 76, 113-124 (2003)
[22] Randić, M., On characterization of molecular branching, J. Amer. Chem. Soc., 97, 6609-6615 (1975)
[23] Shirdel, G. H.; Rezapour, H.; Sayadi, A. M., The hyper-Zagreb index of graph operations, Iran. J. Math. Chem., 4, 213-220 (2013) · Zbl 1367.05180
[24] Wagner, S.; Wang, H.; Zhang, X.-D., Distance-based graph invariants of trees and the Harary index, Filomat, 27, 41-50 (2013)
[25] Wang, H., Functions on adjacent vertex degrees of trees with given degree sequence, Cent. Eur. J. Math., 12, 1656-1663 (2014) · Zbl 1295.05080
[26] Xu, K.; Wang, J.; Das, K. C.; Klavžar, S., Weighted Harary indices of apex trees and \(k\)-apex trees, Discrete Appl. Math., 189, 30-40 (2015) · Zbl 1316.05030
[27] Xu, K.; Wang, J.; Liu, H., The Harary index of ordinary and generalized quasi-tree graph, J. Appl. Math. Comput., 45, 365-374 (2014) · Zbl 1296.05063
[28] Yao, Y.; Liu, M.; Belardo, F.; Yang, C., Unified extremal results of topological indices and spectral invariants of graphs, Discrete Appl. Math., 271, 218-232 (2019) · Zbl 1428.05158
[29] Yuan, W.-G.; Zhang, X.-D., The second Zagreb indices of graphs with given degree sequences, Discrete Appl. Math., 185, 230-238 (2015) · Zbl 1311.05037
[30] Zhang, X.-D., The Laplacian spectral radii of trees with degree sequences, Discrete Math., 308, 3143-3150 (2008) · Zbl 1156.05038
[31] Zhang, X.-D., The signless Laplacian spectral radius of graphs with given degree sequences, Discrete Appl. Math., 157, 2928-2937 (2009) · Zbl 1213.05153
[32] Zhang, X.-D., Extremal graph theory for degree sequences, (Proceedings of the Sixth International Congress of Chinese Mathematicians. Vol. I. Proceedings of the Sixth International Congress of Chinese Mathematicians. Vol. I, Adv. Lect. Math. (ALM), vol. 36 (2017), Int. Press: Int. Press Somerville, MA), 407-424 · Zbl 1379.05075
[33] Zhang, X.-D.; Xiang, Q.-Y., The wiener index of trees with given degree sequences, MATCH Commun. Math. Comput. Chem., 60, 623-644 (2008) · Zbl 1195.05022
[34] Zhang, X.-M.; Zhang, X.-D.; Bass, R.; Wang, H., Extremal trees with respect to functions on adjacent vertex degrees, MATCH Commun. Math. Comput. Chem., 78, 307-322 (2017) · Zbl 1471.92472
[35] Zhang, X.-M.; Zhang, X.-D.; Gray, D.; Wang, H., The number of subtrees of trees with given degree sequence, J. Graph Theory, 73, 280-295 (2013) · Zbl 1269.05022
[36] Zhou, B.; Trinajstić, N., On a novel connectivity index, J. Math. Chem., 46, 1252-1270 (2009) · Zbl 1197.92060
[37] Zhou, B.; Trinajstić, N., On general sum-connectivity index, J. Math. Chem., 47, 210-218 (2010) · Zbl 1195.92083
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.