Connectedness Criteria for Graphs by Means of Omega Invariant

Abstract

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. \\

In this paper, another important topological property of graphs which is connectedness is studied by means of $\Omega$. It is shown that all graphs with $\Omega(G) \leq -4$ are disconnected, and if $\Omega(G) \geq -2$, then the graph could be connected or disconnected. It is also shown that if the realization is a connected graph and $\Omega(G) = -2$, then certainly the graph should be acyclic. Similarly, it is shown that if the realization is a connected graph $G$ and $\Omega(G) \geq 0$, then certainly the graph should be cyclic. Also, the fact that when $\Omega(G) \leq -4$, the components of the disconnected graph could not all be cyclic, and that if all the components of a graph $G$ are cyclic, then $\Omega(G) \geq 0$ are proven.