On the maximum number of diagonals of a circuit in a graph |
| |
Authors: | Ram Prakash Gupta Jeff Kahn Neil Robertson |
| |
Affiliation: | Department of Mathematics, Ohio State University, 231 West 18th Avenue, Columbus, OH 43210, USA |
| |
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 valency.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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|