13
$\begingroup$

If $G=(V,E)$ is a finite, simple, undirected graph, and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in E\}$, and $\text{deg}(v)= |N(v)|$. We say a vertex $v\in V$ is a king if $\text{deg}(v) > \text{deg}(w)$ for all $w\in N(v)$.

In the graph $G=(\{0,1,2\}, \big\{\{0,1\}, \{1,2\}\big\})$, one of the $3$ vertices is a king. Let $\text{King}(G)$ be the set of king vertices.

Question. Is it true that for any finite connected graph $G=(V,E)$ with $|V|>1$ we have $|\text{King}(G)|/|V|\leq 1/3$? If not, how large can this value get?

$\endgroup$
2
  • 24
    $\begingroup$ A complete bipartite graph $G = U \cup V$ with $|U| = n$ and $|V| = n-1$ has $n - 1$ kings out of $2n - 1$ total vertices. $\endgroup$
    – Nik Weaver
    Feb 28 at 14:16
  • $\begingroup$ maybe related: mathoverflow.net/questions/343607/… $\endgroup$ Mar 1 at 15:14
36
$\begingroup$

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".)

$\endgroup$
2
  • 1
    $\begingroup$ There is already the gender-neutral "celebrity" which appears to be motivated by interpreting the vertex degree as the number of people by which a person is known. $\endgroup$ Mar 1 at 15:20
  • $\begingroup$ Furthermore the terminology "king" is used with a different meaning in oriented tournaments (these are vertices with maximum out-degree). $\endgroup$ Mar 2 at 4:14
13
$\begingroup$

The fact that the number of kings is less than the number of non-kings is essentially equivalent to the following problem, proposed by Alexander Razborov to Tournament of Towns in 1990:

Given an $m\times n$ matrix, $m<n$. Some entries are starred, and each column contains a starred entry. Then there exists a star whose row contains more stars than its column.

(Here columns correspond to kings, rows to non-kings, stars to edges, and the strictness of inequalities is different.)

$\endgroup$
5
$\begingroup$

I wanted to find a proof that uses Hall's marriage theorem [1] instead of double-counting.

Given a graph $G=(V,E)$, let $K$ be the set of kings in $V$, and $R:=V \setminus K$ the rest.

Claim: $|K| < |R|$.

Proof Let $G=(V,E)$ be a counterexample that minimizes the sum $|V|+|E|$, so $|K| \ge |R|$. Then $G$ is bipartite, since any edge between nodes in $R$ can be removed. If $|K|>|R|$ then removing one king would yield a smaller counterexample, so $|K|=|R|$. If there was a subset $S$ of $K$ where its neighborhood satisfies $|N(S)|< |S|$, then the induced graph on $S \cup N(S)$ would be a smaller counterexample. Thus the Hall condition is met in $G$. Removing from $G$ a perfect matching of $K$ to $R$ yields a smaller counterexample.

[1] https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem

$\endgroup$
1
  • 1
    $\begingroup$ Beautiful additional answer, thanks Yuval! $\endgroup$ Mar 9 at 18:48
2
$\begingroup$

If we consider the complete bipartite graph $K_{n,m},$ where $n,m$ are natural numbers with $n < m,$ then the maximum degree of a vertex in this graph is $=m$ and there are at least $n$ many vertices having degree $m$, and so the number of "kings" (as per the definition above) in this graph is $ = n,$ and the total number of vertices $=n+m.$

Now, since $n,m$ can be anything (with $n \le m$), so one can take $n,m$ to be such that $n/(n+m) > \frac{1}{3},$ and thus in this case we see that the number of kings in this graph is $> \frac{1}{3} \cdot$ the number of vertices in the graph.

For such graphs you can just set $n=m-1$ to see that you cannot get an "asymptotic" bound of $< 1/2.$

$\endgroup$
2
  • $\begingroup$ If $n=m$ then there are no kings. The best this bipartite construction can do is $\lceil n/2\rceil$ many kings, as Nik Weaver has also pointed out. $\endgroup$ Feb 28 at 15:58
  • $\begingroup$ Ahh sorry, I misread the definition of kings. I will adjust my answer accordingly. $\endgroup$ Feb 28 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.