Article ID Journal Published Year Pages File Type
419439 Discrete Applied Mathematics 2012 11 Pages PDF
Abstract

Let GG be a λkλk-connected graph. GG is called λkλk-optimal, if its kk-restricted edge-connectivity λk(G)λk(G) equals its minimum kk-edge degree. GG is called super  -λkλk if every λkλk-cut isolates a connected subgraph of order kk.Firstly, we give a lower bound on the order of 22-fragments in triangle-free graphs that are not  λ2λ2-optimal. Secondly, we present an Ore-type condition for triangle-free graphs to be λ3λ3-optimal. Thirdly, we prove a lower bound on the order of kk-fragments in triangle-free λkλk-connected graphs, and use it to show that triangle-free graphs with high minimum degree are λkλk-optimal and super  -λkλk.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,