Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419439 | Discrete Applied Mathematics | 2012 | 11 Pages |
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
Andreas Holtkamp, Dirk Meierling, Luis Pedro Montejano,