19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
k-restricted edge-connectivity in triangle-free graphs
Presented by Mr. Andreas HOLTKAMP
Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs
Content
Let $G$ be a $\lambda_k$-connected graph. $G$ is called
$\lambda_k$-optimal, if its $k$-restricted edge-connectivity
$\lambda_k(G)$ equals its minimum $k$-edge degree. $G$ is called super-$\lambda_k$ if every $\lambda_k$-cut isolates a connected subgraph of order $k$.
Firstly, we will introduce a lower bound on the order of $2$-fragments in triangle-free graphs that are not $\lambda_2$-optimal. Secondly, we present an Ore-type condition for triangle-free graphs to be $\lambda_3$-optimal. Thirdly, we prove a lower bound on the order of $k$-fragments in triangle-free $\lambda_k$-connected graphs, and use it to show that triangle-free graphs with high minimum degree are $\lambda_k$-optimal and super-$\lambda_k$.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
Co-authors
- Dr. Dirk MEIERLING RWTH Aachen University, Germany
- Mr. Luis Pedro MONTEJANO Universitat Politecnica de Catalunya, Spain