19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details
PDF | XML

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

Primary authors

More

Co-authors

More