Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let be $G=(U,V,E)$ a bipartite graph where $U$ has $K$ possible vertices and $V$ has $N$ possible vertices.

We focus on closed walks of length $2L$. Such walks can be described by the sequence of vertices $(u_1,v_1,u_2,v_2,\ldots,u_L,v_L,u_1)$. The $(2k-1)$th edge is given by $\{ u_k,v_k \}$ and the $2k$th edge is given by $\{v_k,u_{k+1}\}$, for $1\leq k\leq L-1$, the last two edges are $\{u_L,v_L\}$, $\{v_L,u_1\}$. The following two properties have to be satisfied:

(P1) $u_k\neq u_{k+1}$ for $1\leq k\leq L-1$ and $u_L\neq u_1$;

(P2) each edge is traversed an even number of times.

The question is: how many closed walks satisfying (P1) and (P2) have $\ell$ distinct edges?

Example: $U = \{1,2,3\}$, $V=\{4,5\}$. The walk $(1,4,2,5,2,4,1)$ does not satisfy (P1) since it comes back to $2$ after $5$, while for instance $(1,4,2,4,1)$ is ok.

I can solve the problem when $N=1$, since in that case (P2) is automatically satisfied (the graph is bipartite but in this very particular case $V$ has only one vertex so...) while I do not know how to start when $N>1$. Do you have some hint?

P.S. I have an algorithm that compute (brute force) the answer given $K$, $N$, $L$. I report here four cases with random choices of $K$, $N$, $L$ for some check, I hope they can be useful: when $K=7$, $N=3$, $L=3$, then $(1134,630)$ are the number of closed walks with $\ell=2,3$ distinct edges; when $K=7$, $N=1$, $L=4$, then $(294,1260,840)$ with $\ell=2,3,4$ distinct edges; when $K=7$, $N=2$, $L=4$, then $(2100,4200,2772)$ with $\ell=2,3,4$ distinct edges; when $K=7$, $N=3$, $L=4$, then $(6930,8820,5796)$ with $\ell=2,3,4$ distinct edges.

Update (combinatorial form): I think that I can rephrase the problem in the following combinatorial form. Let a closed walk be represented by the set of his edges: \begin{equation}\mathcal{G}=\{ \{u_1,v_1\},\{v_1,u_2\},\{u_2,v_2\},\ldots,\{u_L,v_L\},\{v_L,u_1\} \}.\end{equation} This is a set properly specified by fixing $(u_1,\ldots,u_L)$ and $(v_1,\ldots,v_L)$, where $1 \leq u_k \leq K$ and $1 \leq v_k \leq N$. Elements are actually sets of the form $\{u_i,v_j\}$. Suppose there are $\ell$ distinct elements in this set. For (P2), one has: \begin{equation} 2L = 2n_1 + \cdots + 2n_\ell,\end{equation} where $2n_i$ is the number of times that the $i$th set appears. This number is necessarily even, and $L=n_1+\cdots+n_\ell$. There is a number of ways to obtain this sum and this is given by a standard formula in combinatorics. How many $\mathcal{G}$ satisfying (P1) are there? In other words, how many times $\mathcal{G}$ has $\ell$ distinct elements, each appearing an even number of times, satisfying (P1)?

share|improve this question
    
Ok, I updated the question calling more properly them closed walks. I also added a combinatorial form of the problem (I hope this equivalence actually holds) that may help (I hope so). –  Gweedo Apr 23 '13 at 18:57
1  
Surely {{1,3},{3,1},{1,3},{3,1},{1,3},{3,1},{1,3},{3,1}} doesn't satisfy P1. P1 appears to forbid $\ell=1$. –  David Bevan Apr 24 '13 at 8:22
    
Both your two remark are right! The case $\ell=1$ is not possible. Version improved! :) [sorry I deleted the previous comment, but yes, that graph I wrote down was incorrect] –  Gweedo Apr 24 '13 at 8:22
    
In your examples, you seem to be ignoring $E$ completely. Are you also assuming the bipartite graph is complete (i.e. all possible edges between $U$ and $V$ exist)? –  Aryabhata Apr 24 '13 at 8:46
    
No, I am not assuming that the bipartite graph is complete. There are vertices that are not touched by closed walks that I consider. –  Gweedo Apr 24 '13 at 15:58

1 Answer 1

I haven't been able to make any real progress on this (none of my ideas so far have worked out), but here's my own table of numerical results for small values of $K$, $N$, $L$ and $\ell$:

$\quad$ table of values

The columns in the inner tables are indexed by values of $\ell$. Where the entry has a "$\cdot$", there are no walks with the corresponding values of the parameters.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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