×

On the mean connected induced subgraph order of cographs. (English) Zbl 1404.05103

Summary: In this article, the extremal structures for the mean order of connected induced subgraphs of cographs are determined. It is shown that among all connected cographs of order \(n\geq 7\), the star \(K_{1,n-1}\) has maximum mean connected induced subgraph order, and for \(n\geq 3\), the \(n\)-skillet, \(K_1+(K_1\cup K_{n-2})\), has minimum mean connected induced subgraph order. It is deduced that the density for connected cographs (i.e. the ratio of the mean to the order of the graph) is asymptotically 1/2. The mean order of all connected induced subgraphs containing a given vertex \(v\) of a cograph \(G\), called the local mean of \(G\) at \(v\), is shown to be at least as large as the mean order of all connected induced subgraphs of \(G\), called the global mean of \(G\).

MSC:

05C40 Connectivity
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] J. I. Brown and L. Mol, On the roots of the node reliability polynomial, Networks 68(3) (2016), 238-246. · Zbl 1387.05116
[2] J. I. Brown and L. Mol, The shape of node reliability, Discrete Appl. Math. 238 (2018), 41-55. · Zbl 1383.05165
[3] C. J. Colbourn, A. Satyanarayana, C. Suffel and K. Sutner, Computing residual connectedness reliability for restricted networks, Discrete Appl. Math. 44 (1993), 221-232. · Zbl 0780.90047
[4] D. G. Corneil, H. Lerchs and L. Stewart Burlingham, Complement reducible graphs, Discrete Appl. Math. 3 (1981), 163-174. · Zbl 0463.05057
[5] O. Goldschmidt, P. Jaillet and R. LaSota, On reliability of graphs with node failures, Networks 24 (1994), 251-259. · Zbl 0824.90067
[6] R. E. Jamison, On the average number of nodes in a subtree of a tree, J. Combin. Theory Ser. B 35 (1983), 207-223. · Zbl 0509.05034
[7] R. E. Jamison, Monotonicity of the mean order of subtrees, J. Combin. Theory Ser. B 37 (1984), 70-78. · Zbl 0544.05054
[8] S. Liu, K.-H. Cheng and X. Liu, Network reliability with node failures, Networks 35(2) (2000), 109-117. · Zbl 0957.90017
[9] L. Mol and O. R. Oellermann, Maximizing the mean subtree order, preprint, arXiv:1707.01874[math.CO], 2017. · Zbl 1417.05031
[10] K. Sutner, A. Satyanarayana and C. Suffel, The complexity of the residual node connectedness reliability problem, SIAM J. Comput. 20(1) (1991), 149-155. · Zbl 0716.68049
[11] A. Vince and H. Wang, The average order of a subtree of a tree, J. Combin. Theory Ser. B 100 (2010), 161-170. · Zbl 1216.05011
[12] S. Wagner and H. Wang, Indistinguishable trees and graphs, Graphs Combin. 30 (2014), 1593-1605. · Zbl 1306.05165
[13] S. Wagner and H. Wang, On the local and global means of subtree orders, J. Graph Theory 81(2) (2016), 154-166. · Zbl 1330.05043
[14] S. Yu, F.-M. Shao and H. Meng, Uniformly optimal graphs in some classes of graphs with node failures, Discrete Math. 310(1) (2010), 159-166. · Zbl 1189.05167
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.