×

On the mean order of connected induced subgraphs of block graphs. (English) Zbl 1439.05123

Summary: The average order of the connected induced subgraphs of a graph \(G\) is called the mean connected induced subgraph (CIS) order of \(G\). This is an extension of the mean subtree order of a tree, first studied by R. E. Jamison-Waldner [J. Comb. Theory, Ser. B 35, 207–223 (1983; Zbl 0509.05034)]. In this article, we demonstrate that among all connected block graphs of order \(n\), the path \(P_n\) has minimum mean CIS order. This extends a result of Jamison from trees to connected block graphs, and supports the conjecture of M. E. Kroeker et al. [Australas. J. Comb. 71, 161–183 (2018; Zbl 1404.05103)] that \(P_n\) has minimum mean CIS order among all connected graphs of order \(n\).

MSC:

05C40 Connectivity
05C51 Graph designs and isomorphic decomposition
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] E. O. D. Andriantiana, V. R. Misanantenaina and S. Wagner, The average size of independent sets of graphs,European J. Math. (to appear). Available at https://doi.org/10.1007/s40879-019-00333-8. · Zbl 1439.05173
[2] A. J. Chin, G. Gordon, K. J. MacPhee and C. Vincent, Subtrees of graphs,J. Graph Theory(2018), 1-26. · Zbl 1440.05076
[3] R. E. Jamison, On the average number of nodes in a subtree of a tree,J. Combin. Theory Ser. B35(1983), 207-223. · Zbl 0509.05034
[4] M. E. Kroeker, L. Mol and O. R. Oellermann, On the mean connected induced subgraph order of cographs,Australasian J. Combin.71(1) (2018), 161-183. · Zbl 1404.05103
[5] L. Mol and O. R. Oellermann, Maximizing the mean subtree order,J. Graph Theory91(4) (2019), 326-352. · Zbl 1417.05031
[6] A. M. Stephens and O. R. Oellermann, The mean order of sub-k-trees ofk-trees, J. Graph Theory88(1) (2018), 61-79. · Zbl 1391.05082
[7] A. Vince and H. Wang, The average order of a subtree of a tree,J. Combin. Theory Ser. B.100(2) (2010), 161-170. · Zbl 1216.05011
[8] S. Wagner and H. Wang, Indistinguishable trees and graphs,Graphs Combin. 30(6) (2014), 1593-1605. · Zbl 1306.05165
[9] S.
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.