论文标题
Nordhaus-gaddum的不平等现象，用于图中连接的诱导子图的数量
Nordhaus-Gaddum inequalities for the number of connected induced subgraphs in graphs
论文作者
论文摘要
令$η（g）$为图$ g $中连接的感应子图的数量，$ \ overline {g} $的补充$ g $。我们证明$η（g）+η（\ overline {g}）$在所有$ n $ vertex图中均为最低，并且仅当$ g $在四个顶点上没有诱导的路径。由于$ n $ vertex star $ s_n $具有最高度$ n-1 $是直径$ 2 $的独特树，$η（s_n）+η（\ overline {s_n}）$在所有$ n $ n $ vertex中是最低的，而最大的序列才能通过其序列来实现，而该序列是$（\ lce lce lce n lceil lceil lceil lceil l r r r r r r。 n/2 \ rfloor，1，\ dots，1）$。此外，我们证明，订单$ n \ geq 5 $的每个图$ g $，以及最大$η（g）+η（\ overline {g}）$最多必须具有直径为$ 3 $，也没有切割的顶点和$ \+++++++++++edline {g} $的属性。在两个具有相同顺序的树和图的情况下，我们发现，如果$η（g）$是最大的，则$η（g）+η（\ edimelline {g}）$是最低的。 作为我们结果的推论，我们表征了给定订单的唯一连接图$ g $ $ 1 $ $ 1 $的顶点，而独特的unicyclic（连接且只有一个周期）图$ g $的给定订单的$ g $，以最小化$η（g）+η（\ edline {g}）$。
Let $η(G)$ be the number of connected induced subgraphs in a graph $G$, and $\overline{G}$ the complement of $G$. We prove that $η(G)+η(\overline{G})$ is minimum, among all $n$-vertex graphs, if and only 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$, $η(S_n)+η(\overline{S_n})$ is minimum among all $n$-vertex trees, while the 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 that every graph $G$ of order $n\geq 5$ and with maximum $η(G)+η(\overline{G})$ must have diameter at most $3$, no cut vertex and the property that $\overline{G}$ is also connected. In both cases of trees and graphs that have the same order, we find that if $η(G)$ is maximum then $η(G)+η(\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 $η(G)+η(\overline{G})$.
