1
$\begingroup$

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:

Drawing of the digraph

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

$\endgroup$
1
  • $\begingroup$ Isn't $H$ just a $4$-cycle? $\endgroup$
    – azimut
    Aug 12, 2013 at 12:24

2 Answers 2

Reset to default
1
$\begingroup$

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.

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

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.

$\endgroup$
1
  • $\begingroup$ hmm, looks more like a comment... $\endgroup$
    – draks ...
    Sep 2, 2013 at 12:24

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.