Andriantiana, Eric O. D.; Razanajatovo Misanantenaina, Valisoa; Wagner, Stephan The average size of independent sets of graphs. (English) Zbl 1439.05173 Eur. J. Math. 6, No. 2, 561-576 (2020). Summary: We study the average size of independent (vertex) sets of a graph. This invariant can be regarded as the logarithmic derivative of the independence polynomial evaluated at 1. We are specifically concerned with extremal questions. The maximum and minimum for general graphs are attained by the empty and complete graph respectively, while for trees we prove that the path minimises the average size of independent sets and the star maximises it. Although removing a vertex does not always decrease the average size of independent sets, we prove that there always exists a vertex for which this is the case. Cited in 5 Documents MSC: 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C35 Extremal problems in graph theory 05C05 Trees 05C07 Vertex degrees Keywords:independent sets; average size; trees; extremal problems PDFBibTeX XMLCite \textit{E. O. D. Andriantiana} et al., Eur. J. Math. 6, No. 2, 561--576 (2020; Zbl 1439.05173) Full Text: DOI arXiv References: [1] Brightwell, G.R., Winkler, P.: Hard constraints and the Bethe lattice: adventures at the interface of combinatorics and statistical physics. In: Tatsien, L.I. (ed.) Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), pp. 605-624. Higher Education Press, Beijing (2002) · Zbl 1001.82035 [2] Davies, E.; Jenssen, M.; Perkins, W.; Roberts, B., Independent sets, matchings, and occupancy fractions, J. London Math. Soc., 96, 1, 47-66 (2017) · Zbl 1370.05160 [3] Davies, E.; Jenssen, M.; Perkins, W.; Roberts, B., On the average size of independent sets in triangle-free graphs, Proc. Amer. Math. Soc., 146, 1, 111-124 (2018) · Zbl 1375.05194 [4] Haslegrave, J., Extremal results on average subtree density of series-reduced trees, J. Combin. Theory Ser. B, 107, 26-41 (2014) · Zbl 1298.05066 [5] Jamison, RE, On the average number of nodes in a subtree of a tree, J. Combin. Theory Ser. B, 35, 3, 207-223 (1983) · Zbl 0509.05034 [6] Jamison, RE, Monotonicity of the mean order of subtrees, J. Combin. Theory Ser. B, 37, 1, 70-78 (1984) · Zbl 0544.05054 [7] Levit, V.E., Mandrescu, E.: The independence polynomial of a graph—a survey. In: Bozapalidis, S., Kalampakas, A., Rahonis, G. (eds.) Proceedings of the 1st International Conference on Algebraic Informatics, pp. 233-254. Aristotle University of Thessaloniki, Thessaloniki (2005) [8] Merrifield, RE; Simmons, HE, Topological Methods in Chemistry (1989), New York: Wiley, New York [9] Mol, L., Oellermann, O.: Maximizing the mean subtree order. J. Graph Theory. 10.1002/jgt.22434 · Zbl 1417.05031 [10] Prodinger, H.; Tichy, RF, Fibonacci numbers of graphs, Fibonacci Quart., 20, 1, 16-21 (1982) · Zbl 0475.05046 [11] Razanajatovo Misanantenaina, V.: Properties of Graph Polynomials and Related Parameters. PhD thesis, Stellenbosch University (2017) [12] Stephens, AM; Oellermann, OR, The mean order of sub-\(k\)-trees of \(k\)-trees, J. Graph Theory, 88, 1, 61-79 (2018) · Zbl 1391.05082 [13] Vince, A.; Wang, H., The average order of a subtree of a tree, J. Combin. Theory Ser. B, 100, 2, 161-170 (2010) · Zbl 1216.05011 [14] Wagner, S.; Gutman, I.; Furtula, B.; Das, KC; Milovanović, E.; Milovanović, I., Upper and lower bounds for Merrifield-Simmons index and Hosoya index, Bounds in Chemical Graph Theory—Basics, 155-187 (2017), Kragujevac: University of Kragujevac, Kragujevac [15] Wagner, S.; Wang, H., On the local and global means of subtree orders, J. Graph Theory, 81, 2, 154-166 (2016) · Zbl 1330.05043 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.