MHB Bipartite Graphs: Does $\alpha(G) =|U|$?

  • Thread starter Thread starter Julio1
  • Start date Start date
  • Tags Tags
    Graphs
Click For Summary
In a bipartite graph G with bipartition U and W, where |U| ≥ |W|, the claim that the independence number α(G) equals |U| is false. A simple example demonstrating this is a bipartite graph with no edges, where α(G) exceeds |U|. Furthermore, it is possible to construct examples with connectedness that also show α(G) can be greater than |U|. The discussion emphasizes the need for justification of these claims. Understanding the relationship between the independence number and the sizes of the bipartite sets is crucial in graph theory.
Julio1
Messages
66
Reaction score
0
Let $G$ be a bipartite graph with bipartition $U$ and $W$ such that $|U|\ge |W|$. Is it true that $\alpha(G) =|U|$?The answer is false, but I don't know how to justify it. I would appreciate any help.
 
Physics news on Phys.org
If you do not assume connectedness then the simplest example where $\alpha(G)$ is more than $|U|$ is when there are no edges. But one can constrcut such exampels even with connectedness.
 
The standard _A " operator" maps a Null Hypothesis Ho into a decision set { Do not reject:=1 and reject :=0}. In this sense ( HA)_A , makes no sense. Since H0, HA aren't exhaustive, can we find an alternative operator, _A' , so that ( H_A)_A' makes sense? Isn't Pearson Neyman related to this? Hope I'm making sense. Edit: I was motivated by a superficial similarity of the idea with double transposition of matrices M, with ## (M^{T})^{T}=M##, and just wanted to see if it made sense to talk...

Similar threads

  • · Replies 2 ·
Replies
2
Views
2K
Replies
11
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
1K