On the edge connectivity of direct products with dense graphs

Details On the edge connectivity of direct products with dense graphs On the edge connectivity of direct products with dense graphs

2011-02-25

arxiv.org/abs/1102.5181v1

Mathematics

Combinatorics

8 pages, submited to discrete math

Scientific paper

Let $\kappa'(G)$ be the edge connectivity of $G$ and $G\times H$ the direct product of $G$ and $H$. Let $H$ be an arbitrary dense graph with minimal degree $\delta(H)>|H|/2$. We prove that for any graph $G$, $\kappa'(G\times H)=\textup{min}\{2\kappa'(G)e(H),\delta(G)\delta(H)\}$, where $e(H)$ denotes the number of edges in $H$. In addition, the structure of minimum edge cuts is described. As an application, we present a necessary and sufficient condition for $G\times K_n(n\ge3)$ to be super edge connected.

Affiliated with

Also associated with

No associations

Rating

On the edge connectivity of direct products with dense graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the edge connectivity of direct products with dense graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the edge connectivity of direct products with dense graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-709478