On the connectivity of diamond-free graphs

Peter Dankelmann, Angelika Hellwig, Lutz Volkmann

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


Let G be a graph of order n (G), minimum degree δ (G) and connectivity κ (G). Chartrand and Harary [Graphs with prescribed connectivities, in: P. Erdös, G. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 61-63] gave the following lower bound on the connectivityκ (G) ≥ 2 δ (G) + 2 - n (G) .Topp and Volkmann [Sufficient conditions for equality of connectivity and minimum degree of a graph, J. Graph Theory 17 (1993) 695-700] improved this bound to κ (G) ≥ 4 δ (G) - n (G), if G is bipartite and κ (G) < δ (G). In this paper, we show that this result remains valid for diamond-free graphs with δ (G) ≥ 3. A diamond is a graph obtained from a complete graph with 4 vertices by removing an arbitrary edge. Furthermore, we show that the above bounds can be improved significantly for graphs with δ (G) ≥ 3 and no 4-cycle, namely, if κ (G) < δ (G), thenκ (G) ≥ 2 δ (G)2 + 2 - 2 δ (G) - n (G) .For graphs that, in addition, contain no 3-cycle, we improve this bound even further.

Original languageEnglish
Pages (from-to)2111-2117
Number of pages7
JournalDiscrete Applied Mathematics
Issue number16
Publication statusPublished - 1 Oct 2007
Externally publishedYes


  • C-free graph
  • Connectivity
  • Diamond-free graph
  • Minimum degree

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'On the connectivity of diamond-free graphs'. Together they form a unique fingerprint.

Cite this