9
$\begingroup$

What is the largest transitively reduced acyclic connected graph on $n$ vertices, for every $n$?

How many edges $e$ does it have? How does $e$ grow as a function of $n$? Faster than $n^2/4$?

  • 0
    Does large mean "many edges"?2010-09-30
  • 0
    Yes, I mean, with the most edges. It just occurred to me that you can always split the vertices into two equal parts and connect each vertex in one part with each vertex in the other (creating a bipartite graph). I've edited the questions accordingly.2010-09-30
  • 0
    At the moment I don't see a larger graph either.2010-09-30
  • 0
    What exactly do you mean by a transitively reduced graph?2010-09-30
  • 0
    http://en.wikipedia.org/wiki/Transitive_reduction#Example2010-09-30

2 Answers 2

6

Since the transitively reduced graph $G$ is acyclic, there is a corresponding undirected simple graph $G'$, which can be formed by ignoring the direction of the edge. The number of edges in $G$ is the same as the number of edges in $G'$.

For $G$ to be transitively reduced, a necessary condition is that $G'$ must not contain any triangles.

It is well known (Turan's/Mantel's theorem) that any simple undirected graph on $n$ vertices and more than $n^2/4$ edges has a triangle.

It is also known that the undirected graph on $n$ vertices with maximum edges and no triangles is the complete bipartite graph $K_{[n/2],[n/2]}$ (for instance check out: http://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA28, exercise 4)

From your comments, it looks like you found a $G$ whose corresponding $G'$ is $K_{[n/2],[n/2]}$ and so that proves it.

3

Bipartite graph is the largest.

Proof: Suppose G is a graph, v is it's vertex. Let $L(v)$ is equal to the maximal length of a directed path, which starts in $v$. Let $L(G)=max_{v\in G} L(v)$. If $L(G)=1$, the graph is bipartite. In order to prove, that bipartite graph is the largest, I will prove, that for any graph $G$ such that $L(G)>1$ there exists graph $H$ with the same number of vertices and edges, such that $L(G)>L(H)$.

Note, that any vertex with $L(v)=0$ has only inbound connections. This connections are from vertices w with $L(w)=1$. We will do graph $H$ in two steps.
Step 1. Remove all vertices with $L(v)=0$, and edges to them. Note that $L(G)$ has been decreased. Step 2. Add all the vertices, removed on step 1. Add edges, removed on step 1, but reverse their direction. Call the new graph $H$. Note, that it has the same number of vertices and edges and $L(H) < L(G)$.

  • 0
    Very insightful, thank you! This proves that bipartite graphs are the largest (which is what I wanted to know) but not that there aren't any other largest graphs.2010-10-01