TY - JOUR
T1 - On the maximum number of diagonals of a circuit in a graph
AU - Gupta, Ram Prakash
AU - Kahn, Jeff
AU - Robertson, Neil
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 1980
Y1 - 1980
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0042223596&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0042223596&partnerID=8YFLogxK
U2 - 10.1016/0012-365X(80)90097-7
DO - 10.1016/0012-365X(80)90097-7
M3 - Article
AN - SCOPUS:0042223596
VL - 32
SP - 37
EP - 43
JO - Discrete Mathematics
JF - Discrete Mathematics
SN - 0012-365X
IS - 1
ER -