On The Graphs and Their Complements with Prescribed Circumference

  • TA Kusmayadi
  • L Caccetta

Abstract

Let Gt(n) be the class of connected graphs on n vertices having the longest cycle of length t and let G āˆˆ Gt(n). Woodall (1976) determined the maximum number of edges of G. An alternative proof and characterization of the extremal (edge-maximal) graphs given by Caccetta & Vijayan (1991). The edge-maximal graphs have the property that their complements are either disconnected or have a cycle going through each vertex (i.e. they are hamiltonian). This motivates us to investigate connected graphs with prescribed circumference (length of the longest cycle) having connected complements with cycles . More specifically, we focus our investigations on the class G (n, c, c) denoting the class of connected graphs on n vertices having circumference c and whose connected complements have circumference c. The problem of interest is that of determining the bounds of the number of edges of a graph Gāˆˆ G(n, c, c) and characterize the extremal graphs of G(n, c, c). We discuss the class G (n, c, c) and present some results for small c. In particular for c=4 and c =n-2, we provide a complete solution.

Published
2012-01-01
How to Cite
KUSMAYADI, TA; CACCETTA, L. On The Graphs and Their Complements with Prescribed Circumference. Jurnal ILMU DASAR, [S.l.], v. 12, n. 1, p. 30-36, jan. 2012. ISSN 2442-5613. Available at: <https://jurnal.unej.ac.id/index.php/JID/article/view/351>. Date accessed: 29 mar. 2024.
Section
General

Keywords

Extremal graph; circumference