Connectedness Criteria for Graphs by Means of Omega Invariant

Creative Commons License

Sanli U., Celik F., Delen S., CANGÜL İ. N.

FILOMAT, vol.34, no.2, pp.647-652, 2020 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 34 Issue: 2
  • Publication Date: 2020
  • Doi Number: 10.2298/fil2002647s
  • Journal Name: FILOMAT
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, zbMATH
  • Page Numbers: pp.647-652
  • Keywords: omega invariant, degree sequence, graph characteristic, connectedness, cyclic graph, acyclic graph
  • Bursa Uludag University Affiliated: Yes


A realizable degree sequence can be realized in many ways as a graph. There are several tests for determining realizability of a degree sequence. Up to now, not much was known about the common properties of these realizations. Euler characteristic is a well-known characteristic of graphs and their underlying surfaces. It is used to determine several combinatorial properties of a surface and of all graphs embedded onto it. Recently, last two authors defined a number Omega which is invariant for all realizations of a given degree sequence. Omega is shown to be related to Euler characteristic and cyclomatic number. Several properties of Omega are obtained and some applications in extremal graph theory are done by authors. As already shown, the number Omega gives direct information compared with the Euler characteristic on the realizability, number of realizations, being acyclic or cyclic, number of components, chords, loops, pendant edges, faces, bridges etc.