Return to Answer

For this discussion I am assuming we do not consider isolated vertices to be "Kings", even though technically your definition considers them to be so in a vacuous sense (I guess this convention goes back to Shakespeare). Otherwise of course one can make every vertex a king by having no edges whatseover.

For the matching lower bound, observe that no two kings can be adjacent, and if there is at least one king, the set $E'$ of ordered pair edges $(v,w)$ in $E$ with $v \in \mathrm{King}(G)$ and $w \not \in \mathrm{King}(G)$ is non-empty. Now we do weighted double counting: \begin{align*} \# \mathrm{King}(G) &= \sum_{v \in \mathrm{King}(G)} 1 \\ &= \sum_{(v,w) \in E'} \frac{1}{d(v)}\\ &< \sum_{(v,w) \in E'} \frac{1}{d(w)} \\ &\leq \sum_{w \in V \backslash \mathrm{King}(G)} 1 \\ &= \#V - \# \mathrm{King}(G) \end{align*} hence $$ \# \mathrm{King}(G) < \frac{1}{2} \# V.$$ Of course the same claim holds when there are no kings as long as the graph is not the empty graph. So this shows that the lower bound provided by the complete bipartite graph examples (adding an isolated vertex in the case when one wants an even number of edges) are completely optimal.

This bound can also be viewed as quantifying a variant of the "friendship paradox". (Based on this connection, I propose "influencer" as a more modern and gender-neutral terminology alternative to "king".)

For this discussion I am assuming we do not consider isolated vertices to be "Kings", even though technically your definition considers them to be so in a vacuous sense (I guess this convention goes back to Shakespeare). Otherwise of course one can make every vertex a king by having no edges whatseover.

For the matching lower bound, observe that no two kings can be adjacent, and if there is at least one king, the set $E'$ of ordered pair edges $(v,w)$ in $E$ with $v \in \mathrm{King}(G)$ and $w \not \in \mathrm{King}(G)$ is non-empty. Now we do weighted double counting: \begin{align*} \# \mathrm{King}(G) &= \sum_{v \in \mathrm{King}(G)} 1 \\ &= \sum_{(v,w) \in E'} \frac{1}{d(v)}\\ &< \sum_{(v,w) \in E'} \frac{1}{d(w)} \\ &\leq \sum_{w \in V \backslash \mathrm{King}(G)} 1 \\ &= \#V - \# \mathrm{King}(G) \end{align*} hence $$ \# \mathrm{King}(G) < \frac{1}{2} \# V.$$ Of course the same claim holds when there are no kings as long as the graph is not the empty graph. So this shows that the lower bound provided by the complete bipartite graph examples (adding an isolated vertex in the case when one wants an even number of vertices) are completely optimal: the maximal number of kings in a graph on $n$ vertices is $\max( \lfloor \frac{n-1}{2} \rfloor, 0)$.

This bound can also be viewed as quantifying a variant of the "friendship paradox". (Based on this connection, I propose "influencer" as a more modern and gender-neutral terminology alternative to "king".)

For this discussion I am assuming we do not consider isolated vertices to be "Kings", even though technically your definition claims them to be so in a vacuous sense (I guess this convention goes back to Shakespeare). Otherwise of course one can make every vertex a king by having no edges whatseover.

For the matching lower bound, observe that no two kings can be adjacent, and if there is at least one king, the set $E'$ of ordered pair edges $(v,w)$ in $E$ with $v \in \mathrm{King}(G)$ and $w \not \in \mathrm{King}(G)$ is non-empty. Now we do weighted double counting: \begin{align*} \# \mathrm{King}(G) &= \sum_{(v,w) \in E'} \frac{1}{d(v)}\\ &< \sum_{(v,w) \in E'} \frac{1}{d(w)} \\ &\leq \sum_{w \in V \backslash \mathrm{King(G)}} 1 \\ &= \#V - \# \mathrm{King(G)} \end{align*} hence $$ \# \mathrm{King(G)} < \frac{1}{2} \# V.$$ Of course the same claim holds when there are no kings as long as the graph is not the empty graph. So this shows that the lower bound provided by the complete bipartite graph examples (adding an isolated vertex in the case when one wants an even number of edges) are completely optimal.

This bound can also be viewed as quantifying a variant of the "friendship paradox". (Based on this connection, I propose "influencer" as a more modern and gender-neutral terminology alternative to "king".)

For this discussion I am assuming we do not consider isolated vertices to be "Kings", even though technically your definition considers them to be so in a vacuous sense (I guess this convention goes back to Shakespeare). Otherwise of course one can make every vertex a king by having no edges whatseover.

For the matching lower bound, observe that no two kings can be adjacent, and if there is at least one king, the set $E'$ of ordered pair edges $(v,w)$ in $E$ with $v \in \mathrm{King}(G)$ and $w \not \in \mathrm{King}(G)$ is non-empty. Now we do weighted double counting: \begin{align*} \# \mathrm{King}(G) &= \sum_{v \in \mathrm{King}(G)} 1 \\ &= \sum_{(v,w) \in E'} \frac{1}{d(v)}\\ &< \sum_{(v,w) \in E'} \frac{1}{d(w)} \\ &\leq \sum_{w \in V \backslash \mathrm{King}(G)} 1 \\ &= \#V - \# \mathrm{King}(G) \end{align*} hence $$ \# \mathrm{King}(G) < \frac{1}{2} \# V.$$ Of course the same claim holds when there are no kings as long as the graph is not the empty graph. So this shows that the lower bound provided by the complete bipartite graph examples (adding an isolated vertex in the case when one wants an even number of edges) are completely optimal.

This bound can also be viewed as quantifying a variant of the "friendship paradox". (Based on this connection, I propose "influencer" as a more modern and gender-neutral terminology alternative to "king".)

For this discussion I am assuming we do not consider isolated vertices to be "Kings" (Shakespeare notwithstanding), even though technically your definition claims them to be so in a vacuous sense. Otherwise of course one can make every vertex a king by having no edges whatseover.

For the matching lower bound, observe that no two kings can be adjacent, and if there is at least one king, the set $E'$ of ordered pair edges $(v,w)$ in $E$ with $v \in \mathrm{King}(G)$ and $w \not \in \mathrm{King}(G)$ is non-empty. Now we do weighted double counting: \begin{align*} \# \mathrm{King}(G) &= \sum_{(v,w) \in E'} \frac{1}{d(v)}\\ &< \sum_{(v,w) \in E'} \frac{1}{d(w)} \\ &\leq \sum_{w \in V \backslash \mathrm{King(G)}} 1 \\ &= \#V - \# \mathrm{King(G)} \end{align*} hence $$ \# \mathrm{King(G)} < \frac{1}{2} \# V.$$ Of course the same claim holds when there are no kings as long as the graph is not the empty graph. So this shows that the lower bound provided by the complete bipartite graph examples (adding an isolated vertex in the case when one wants an even number of edges) are completely optimal.

This bound can also be viewed as quantifying a variant of the "friendship paradox". (Based on this connection, I propose "influencer" as a more modern and gender-neutral terminology alternative to "king".)

For this discussion I am assuming we do not consider isolated vertices to be "Kings", even though technically your definition claims them to be so in a vacuous sense (I guess this convention goes back to Shakespeare). Otherwise of course one can make every vertex a king by having no edges whatseover.

For the matching lower bound, observe that no two kings can be adjacent, and if there is at least one king, the set $E'$ of ordered pair edges $(v,w)$ in $E$ with $v \in \mathrm{King}(G)$ and $w \not \in \mathrm{King}(G)$ is non-empty. Now we do weighted double counting: \begin{align*} \# \mathrm{King}(G) &= \sum_{(v,w) \in E'} \frac{1}{d(v)}\\ &< \sum_{(v,w) \in E'} \frac{1}{d(w)} \\ &\leq \sum_{w \in V \backslash \mathrm{King(G)}} 1 \\ &= \#V - \# \mathrm{King(G)} \end{align*} hence $$ \# \mathrm{King(G)} < \frac{1}{2} \# V.$$ Of course the same claim holds when there are no kings as long as the graph is not the empty graph. So this shows that the lower bound provided by the complete bipartite graph examples (adding an isolated vertex in the case when one wants an even number of edges) are completely optimal.

This bound can also be viewed as quantifying a variant of the "friendship paradox". (Based on this connection, I propose "influencer" as a more modern and gender-neutral terminology alternative to "king".)