On the Mean Connected Induced Subgraph Order of Cographs

Abstract

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\ge 7$, the star $K_{1,n-1}$ has maximum mean connected induced subgraph order, and for $n\ge 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$.

24 pages