Counting edge numbers in bipartite graphs

In summary, the conversation discusses the creation of a bipartite graph G through the combination of various levels L, with each level containing a different number of vertices. The number of edges in a bipartite graph is determined by the product of the number of vertices in each level. The total number of bipartite graphs created by combining all levels is the sum of all possible combinations. The speaker also inquires about any research publications related to this topic in various fields such as networking optimization, genetic networks, and graph theories. They clarify that they have not worked with graphs for a long time and may not remember all the basics.
  • #1
Medicol
223
54
Let L be the level number of a bipartite graph G, and so
L1 be the first level of n1 vertices,
L2 be the second level of n2 vertices,
...
Lk be the kth level of nk vertices.
Then a bipartite graph G12 is created by a combination of L1 and L2, G23 is of L2 and L3,...,Gij is of Li and Lj.

The number of edges in a bipartite graph is [itex]m[/itex]x[itex]n[/itex]. And the total number of the above network of bipartite graphs is [tex]\sum=n_1n_2+n_1n_3+...+n_1n_k+n_2n_3+...+n_2n_k+...+n_{k-1}n_k[/tex]
  • Is my sum above correct ?
  • Are there any research publication concerning this bipartite graph node combination in networking optimization, genetic network, numerical research or graph theories that you know about ?
All the definitions are self-made, I have not been working with graphs for years, many basics are thus forgotten. Thank you. :D
 
Mathematics news on Phys.org
  • #2
Thanks for the post! Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?
 

1. What is a bipartite graph?

A bipartite graph is a type of graph in which the vertices can be divided into two sets, such that there are no edges between vertices within the same set. In other words, all edges in a bipartite graph connect vertices from different sets.

2. How do you count edge numbers in a bipartite graph?

To count edge numbers in a bipartite graph, you can use the formula E = V1 * V2, where E is the number of edges, V1 is the number of vertices in one set, and V2 is the number of vertices in the other set. This assumes that there are no multiple edges between the same pair of vertices.

3. Can a bipartite graph have an odd number of vertices?

Yes, a bipartite graph can have an odd number of vertices. As long as the vertices can be divided into two sets with no edges between them, the graph is considered bipartite.

4. What is the maximum number of edges in a bipartite graph?

The maximum number of edges in a bipartite graph is V1 * V2, where V1 and V2 are the sizes of the two vertex sets. This occurs when every vertex in one set is connected to every vertex in the other set.

5. How is counting edge numbers in a bipartite graph useful?

Counting edge numbers in a bipartite graph can be useful for analyzing the structure and relationships within the graph. It can also help with determining the complexity and efficiency of algorithms that use bipartite graphs.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
7K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
Replies
4
Views
863
  • Calculus and Beyond Homework Help
Replies
5
Views
12K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
Replies
1
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Beyond the Standard Models
Replies
24
Views
7K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
2K
Back
Top