Some extremal graphs with respect to inverse degree. (English) Zbl 1332.05076
Summary: The inverse degree of graph \(G\) is defined as \(\operatorname{ID}(G) = \sum_{v \in V(G)} \frac{1}{d_G(v)}\) where \(d_G(v)\) is the degree of vertex \(v\) in \(G\). In this paper the authors determine some upper and lower bounds on the inverse degree \(\operatorname{ID}(G)\) for a connected graph \(G\) in terms of other graph parameters, such as chromatic number, clique number, connectivity, number of cut edges, matching number. Also the corresponding extremal graphs have been completely characterized.
MSC:
| 05C35 | Extremal problems in graph theory |
| 05C07 | Vertex degrees |
| 05C40 | Connectivity |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
Software:
GRAFFITIReferences:
| [1] | Berge, C., Sur le couplage maximum d’un graphe, C.R. Acad. Sci. Paris Sér. I Math., 247, 258-259 (1958) · Zbl 0086.16301 |
| [2] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan Press: Macmillan Press New York · Zbl 1226.05083 |
| [3] | Chen, X.; Fujita, S., On diameter and inverse degree of chemical graphs, Appl. Anal. Discrete Math., 7, 83-93 (2013) · Zbl 1299.05047 |
| [4] | Dankelmann, P.; Hellwig, A.; Volkmann, L., Inverse degree and edge-connectivity, Discrete Math., 309, 2943-2947 (2009) · Zbl 1203.05082 |
| [5] | Dankelmann, P.; Swart, H. C.; van den Berg, P., Diameter and inverse degree, Discrete Math., 308, 670-673 (2008) · Zbl 1142.05022 |
| [6] | Das, K. C.; Xu, K.; Gutman, I., On Zagreb and Harary indices, MATCH Commun. Math. Comput. Chem., 70, 301-314 (2013) · Zbl 1299.05035 |
| [7] | Das, K. C.; Xu, K.; Wang, J., On inverse degree and topological indices of graphs, Filomat (2016), in press · Zbl 1462.05074 |
| [8] | Erdös, P., On the graph theorem of Turán, Mat. Lapok, 21, 249-251 (1970) · Zbl 0231.05110 |
| [9] | Erdös, P.; Pach, J.; Spencer, J., On the mean distance between points of a graph, Congr. Numer., 64, 121-124 (1988) · Zbl 0677.05053 |
| [10] | Fajtlowicz, S., On conjectures of graffiti II, Congr. Numer., 60, 189-197 (1987) · Zbl 0713.05054 |
| [11] | Hu, Y.; Li, X.; Shi, Y.; Xu, T., Connected \((n, m)\)-graphs with minimum and maximum zeroth-order general Randić index, Discrete Appl. Math., 155, 1044-1054 (2007) · Zbl 1120.05046 |
| [12] | Li, X.; Gutman, I., (Mathematical Aspects of Randic-Type Molecular Structure Descriptors. Mathematical Aspects of Randic-Type Molecular Structure Descriptors, Mathematical Chemistry Monographs, vol. 1 (2006), Kragujevac) · Zbl 1294.92032 |
| [13] | Li, X.; Shi, Y., On the diameter and inverse degree, Ars Combin., 101, 481-487 (2011) · Zbl 1265.05192 |
| [14] | Li, X.; Zhao, H., Trees with the first three smallest and largest generalized topological indices, MATCH Commun. Math. Comput. Chem., 50, 57-62 (2004) · Zbl 1274.05080 |
| [15] | Mukwembi, S., On diameter and inverse degree of a graph, Discrete Math., 310, 940-946 (2010) · Zbl 1216.05023 |
| [16] | Tutte, W. T., The factorization of linear graphs, J. Lond. Math. Soc., 22, 107-111 (1947) · Zbl 0029.23301 |
| [17] | Zhang, S.; Zhang, H., Unicyclic graphs with the first three smallest and largest first general Zagreb index, MATCH Commun. Math. Comput. Chem., 55, 427-438 (2006) · Zbl 1106.05032 |
| [18] | Zhang, Z.; Zhang, J.; Lu, X., The relation of matching with inverse degree of a graph, Discrete Math., 301, 243-246 (2005) · Zbl 1079.05081 |
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.
