Skip to main content
Became Hot Network Question
added 59 characters in body; edited tags
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

I want to find a condition ofon $\delta(G)$  (ex. $\delta(G) \geq an$) that guarantees $\kappa(G)=\delta(G)$ where $\kappa(G)$ is a connectivitythe vertex-connectivity of a bipartite graph $G$, and $\delta(G)$ is the minimum degree of $G$.
In

In other words, I want to prove that the statement 'If $\delta(G) \geq an$, then $\kappa(G)=\delta(G)$

If $\delta(G) \geq an$, then $\kappa(G)=\delta(G)$

holds for bipartite graphs.'
I

I know that $\delta(G) \geq \frac{n+1}{4}$ implies $\kappa'(G)=\delta(G)$ where $\kappa'(G)$ is anthe edge-connectivity of $G$, and it is sharp.
Also, I proved that bipartite $G$ is connected if $\delta(G) \geq \frac{n+1}{4}$.
But I have no idea with the vertex-connectivity.
Here are my ideas to find such boundary $an$:

  1. (Contrapositive) Prove the statement 'If"If $\kappa(G)<\delta(G)$, then $\delta(G)<an$  ."
  2. Use the statement $\delta(G) \geq \frac{n+1}{4}\Rightarrow \kappa'(G)=\delta(G)$. Find the boundary of $\delta(G)$ that implies $\kappa(G)=\kappa'(G)$, and then show this boundary also satisfies $\delta(G) \geq \frac{n+1}{4}$.

Would you help me?

I want to find a condition of $\delta(G)$(ex. $\delta(G) \geq an$) that guarantees $\kappa(G)=\delta(G)$ where $\kappa(G)$ is a connectivity of bipartite graph $G$, and $\delta(G)$ is the minimum degree of $G$.
In other words, I want to prove the statement 'If $\delta(G) \geq an$, then $\kappa(G)=\delta(G)$.'
I know that $\delta(G) \geq \frac{n+1}{4}$ implies $\kappa'(G)=\delta(G)$ where $\kappa'(G)$ is an edge-connectivity of $G$, and it is sharp.
Also, I proved that bipartite $G$ is connected if $\delta(G) \geq \frac{n+1}{4}$.
But I have no idea with the connectivity.
Here are my ideas to find such boundary $an$:

  1. (Contrapositive) Prove the statement 'If $\kappa(G)<\delta(G)$, then $\delta(G)<an$  .
  2. Use the statement $\delta(G) \geq \frac{n+1}{4}\Rightarrow \kappa'(G)=\delta(G)$. Find the boundary of $\delta(G)$ that implies $\kappa(G)=\kappa'(G)$, and then show this boundary also satisfies $\delta(G) \geq \frac{n+1}{4}$.

Would you help me?

I want to find a condition on $\delta(G)$  (ex. $\delta(G) \geq an$) that guarantees $\kappa(G)=\delta(G)$ where $\kappa(G)$ is the vertex-connectivity of a bipartite graph $G$, and $\delta(G)$ is the minimum degree of $G$.

In other words, I want to prove that the statement

If $\delta(G) \geq an$, then $\kappa(G)=\delta(G)$

holds for bipartite graphs.

I know that $\delta(G) \geq \frac{n+1}{4}$ implies $\kappa'(G)=\delta(G)$ where $\kappa'(G)$ is the edge-connectivity of $G$, and it is sharp.
Also, I proved that bipartite $G$ is connected if $\delta(G) \geq \frac{n+1}{4}$.
But I have no idea with the vertex-connectivity.
Here are my ideas to find such boundary $an$:

  1. (Contrapositive) Prove the statement "If $\kappa(G)<\delta(G)$, then $\delta(G)<an$."
  2. Use the statement $\delta(G) \geq \frac{n+1}{4}\Rightarrow \kappa'(G)=\delta(G)$. Find the boundary of $\delta(G)$ that implies $\kappa(G)=\kappa'(G)$, and then show this boundary also satisfies $\delta(G) \geq \frac{n+1}{4}$.

Would you help me?

Source Link
okw1124
  • 341
  • 1
  • 9

Connectivity and the minimum degree of bipartite graph

I want to find a condition of $\delta(G)$(ex. $\delta(G) \geq an$) that guarantees $\kappa(G)=\delta(G)$ where $\kappa(G)$ is a connectivity of bipartite graph $G$, and $\delta(G)$ is the minimum degree of $G$.
In other words, I want to prove the statement 'If $\delta(G) \geq an$, then $\kappa(G)=\delta(G)$.'
I know that $\delta(G) \geq \frac{n+1}{4}$ implies $\kappa'(G)=\delta(G)$ where $\kappa'(G)$ is an edge-connectivity of $G$, and it is sharp.
Also, I proved that bipartite $G$ is connected if $\delta(G) \geq \frac{n+1}{4}$.
But I have no idea with the connectivity.
Here are my ideas to find such boundary $an$:

  1. (Contrapositive) Prove the statement 'If $\kappa(G)<\delta(G)$, then $\delta(G)<an$ .
  2. Use the statement $\delta(G) \geq \frac{n+1}{4}\Rightarrow \kappa'(G)=\delta(G)$. Find the boundary of $\delta(G)$ that implies $\kappa(G)=\kappa'(G)$, and then show this boundary also satisfies $\delta(G) \geq \frac{n+1}{4}$.

Would you help me?