On the maximum number of diagonals of a circuit in a graph

Ram Prakash Gupta, Jeff Kahn, Neil Robertson

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

For a graph G, let ∂(G) denote the maximum number k such that G contains a circuit with k diagonals. Theorem. For any graph G with minimum valencyn≥ 3, ∂(G) ≥ 1 2 (n+1)(n-2). If the equality holds and G is connected, then either G is isomorphic to Kn+1 or G is separable and each of its terminal blocks is isomorphic to Kn+1, or Kn+1 with one edge subdivided.

Original languageEnglish (US)
Pages (from-to)37-43
Number of pages7
JournalDiscrete Mathematics
Volume32
Issue number1
DOIs
StatePublished - 1980

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On the maximum number of diagonals of a circuit in a graph'. Together they form a unique fingerprint.

Cite this