On the mean connected induced subgraph order of cographs

MaRDI QIDQ4616101zbMATH OpenFDO

Authors Matthew E. Kroeker, Ortrud R. Oellermann, L. A. S. Mól

Publication date 30 January 2019

Full work available at URL https://arxiv.org/abs/1708.01916, http://ajc.maths.uq.edu.au/pdf/71/ajc_v71_p161.pdf

zbMATH Keywords

connected induced subgraphs of cographsglobal mean of a graph

Mathematics Subject Classification ID

Connectivity (05C40)

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

Recommendations

• On the mean order of connected induced subgraphs of block graphs
• The path minimises the average size of a connected induced subgraph
• A lower bound on the average size of a connected vertex set of a graph
• The average size of a connected vertex set of a graph—Explicit formulas and open problems
• scientific article; zbMATH DE number 7714103

Cites work

• Complement reducible graphs
• Computing residual connectedness reliability for restricted networks
• scientific article; zbMATH DE number 1444280 (Why is no real title available?)
• Indistinguishable trees and graphs
• Maximizing the mean subtree order
• Monotonicity of the mean order of subtrees
• On reliability of graphs with node failures
• On the average number of nodes in a subtree of a tree
• On the local and global means of subtree orders
• On the roots of the node reliability polynomial
• The average order of a subtree of a tree
• The Complexity of the Residual Node Connectedness Reliability Problem
• The shape of node reliability
• Uniformly optimal graphs in some classes of graphs with node failures

Cited in

(12)

• The average size of a connected vertex set of a \(k\)-connected graph
• The path minimises the average size of a connected induced subgraph
• A lower bound on the average size of a connected vertex set of a graph
• On the local and global mean orders of sub-k-trees of k-trees
• On the mean order of connected induced subgraphs of block graphs
• On the mean subtree order of graphs under edge addition
• The average size of a connected vertex set of a graph—Explicit formulas and open problems
• The number and average size of connected sets in graphs with degree constraints
• A tight upper bound on the average order of dominating sets of a graph
• The average order of a connected vertex set in generalized ladder graphs
• The average order of a connected induced subgraph of a graph and union-intersection systems
• The maximum number of connected sets in regular graphs

This page was built for publication: On the mean connected induced subgraph order of cographs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4616101)