English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $\eta(G)$ be the number of connected induced subgraphs in a graph $G$,and $\overline{G}$ the complement of $G$. We prove that$\eta(G)+\eta(\overline{G})$ is minimum, among all $n$-vertex graphs, if andonly if $G$ has no induced path on four vertices. Since the $n$-vertex star$S_n$ with maximum degree $n-1$ is the unique tree of diameter $2$,$\eta(S_n)+\eta(\overline{S_n})$ is minimum among all $n$-vertex trees, whilethe maximum is shown to be achieved only by the tree whose degree sequence is$(\lceil n/2\rceil,\lfloor n/2\rfloor,1,\dots,1)$. Furthermore, we prove thatevery graph $G$ of order $n\geq 5$ and with maximum$\eta(G)+\eta(\overline{G})$ must have diameter at most $3$, no cut vertex andthe property that $\overline{G}$ is also connected. In both cases of trees andgraphs that have the same order, we find that if $\eta(G)$ is maximum then$\eta(G)+\eta(\overline{G})$ is minimum.  As corollaries to our results, we characterise the unique connected graph $G$of given order and number of vertices of degree $1$, and the unique unicyclic(connected and has only one cycle) graphs $G$ of a given order that minimises$\eta(G)+\eta(\overline{G})$.

Nordhaus-Gaddum inequalities for the number of connected induced subgraphs in graphs