# Counting the number of subgraphs isomorphic with the following digraph

Suppose $H$ is the following 4-vertex digraph : $$\langle V=\{a,b,c,d\}, E=\{ab,bd,ac,cd\}\rangle .$$ The digraph is drawn below:

Can one help me to prove upper bound $n^4/55$ on the number of $H$s in any n-vertex digraph G for G's that out-degree of every vertex is exactly $n/3$ and doesn't contain any directed triangle.

I would appreciate any help, thanks.

edit #1: In fact, I want an asymptotic bound (i.e. when n tends to infinity).

• Isn't $H$ just a $4$-cycle? Aug 12, 2013 at 12:24

If you don't specify any other structure of $G$ then you can have up to $4!{n \choose 4} = O(n^4)$ such subgraphs.

Edit. If you want to bound the number of such two paths you can argue as follows. Every such path is defined by a source vertex $v$, two of its neighbours $v',v''$ and a common neighbor of $v',v''.$ There are (being shallow with floorings/ceilings) up to ${n/3 \choose 2}$ ways to choose $v',v''$ and it can happen that $v',v''$ have $n/3$ common neighbours giving us a total of ${n/3 \choose 2}n/3$ such paths with start vertex $v$ and hence a total of ${n/3 \choose 2}n^2/3$ such subgraphs.

• I don't think so. Can you give me an example of such G?
– j.s.
Jul 15, 2013 at 9:18
• @behnam Take a complete digraph of order $4$ with arcs in both directions. Jul 15, 2013 at 9:19
• @Jenej, thanks. But I want asymptotic bound (i.e. when n tends to infinity). small graph doesn't matter.
– j.s.
Jul 15, 2013 at 9:20
• However, I want this ub for G's that out-degree of every vertex is $n/3$ and has no directed triangle.
– j.s.
Jul 15, 2013 at 9:24
• @Jenej, you count directed quadrilaterals. but my $H$ is not directed quadrilateral.
– j.s.
Jul 15, 2013 at 10:16

Just a quick clarification: is your digraph G simple? (no loops, no oriented cycles of length 2). Second, do you care about copies of H in G or induced copies of H in G? There is a paper by A.J.Bondy - Counting Subgraphs - which appeared in Discrete Mathematics in 1997 which I believe it could be useful.

• hmm, looks more like a comment... Sep 2, 2013 at 12:24