4
$\begingroup$

Let $G=(V,E)$ be a graph with $n$ vertices. We call an edge $(i,j)\in E$ is imbalanced if $d_i\neq d_j$. What is the maximum number of imbalanced edge of $G$?

A candidate type of graph that attain the maximum value is the complete $k$-partite graph $K_{d_1,d_2,\dots,d_k}$ such that $d_1+d_2+\dots+d_k=n$ and all of the $d_i$ are pairwise different, so that all of the edges of $K_{d_1,d_2,\dots,d_k}$ are imbalanced.

$\endgroup$
6
  • 4
    $\begingroup$ If I understand correctly, in a star graph with $n+1$ vertices all $n$ edges are imbalanced. $\endgroup$ Commented Sep 8 at 14:45
  • 1
    $\begingroup$ Maybe the right question to ask is, for a given value of $n$, what's the maximum number of unbalanced edges, over all graphs with $n$ vertices? E.g., with $n=6$, the star graph has only five edges, while the $K_{1,2,3}$ has $11$. I agree that a complete $k$-partite graph may always be the winner. $\endgroup$ Commented Sep 9 at 2:39
  • $\begingroup$ But for $n=4$, a $K_4$ missing one edge beats a $K_{1,3}$, four unbalanced edges to three. $\endgroup$ Commented Sep 9 at 2:54
  • 1
    $\begingroup$ The more interesting question to me is, for a fixed $n$, what is the graph on $n$ vertices that has the most edges, ALL of which are unbalanced? For $n=6$, there is a graph with 11 edges, all of which are unbalanced. $\endgroup$ Commented Sep 9 at 10:37
  • 3
    $\begingroup$ @Erich, interest is in the eye of the beholder. For $n=4$, $K_{1,3}$ answers your question: three edges, all unbalanced. $K_{1,1,2}$ answers my question: four unbalanced edges, out of five edges total. For $n=7$, I know a graph with $17$ edges, of which $16$ are unbalanced. $\endgroup$ Commented Sep 11 at 12:43

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.