Abstract

The well-known Euler characteristic is an invariant of graphs defined by means of the vertex, edge and face numbers of a graph, to determine the genus of the underlying surface of the graph. By means of it, it is possible to determine the vertex, edge and face numbers of all possible graphs which can be drawn in a given orientable/non-orientable surface. In this paper, by means of a given degree sequence, a new number denoted by which is related to Euler characteristic and has several applications in Graph Theory is defined. This formula gives direct information compared with the Euler characteristic on the realizability, number of realizations, connectedness, being acyclic or cyclic, number of components, chords, loops, pendant edges, faces, bridges etc.

1. Introduction

As usual, let be a graph with vertices and edges. and are called the order and the size of the graph G. For a vertex , the degree of v is denoted by . A vertex with degree one which is one of the fundamental concepts of these paper is called a pendant vertex. With slight abuse of language, we shall use the term "pendant edge" for an edge having a pendant vertex. The smallest and biggest vertex degrees in a graph will be denoted by and , respectively. If and are adjacent vertices of G, and if the edge connects them, this situation will be denoted by . In such a case, the vertices and are called adjacent vertices and the edge e is said to be incident with and . Adjacency and incidency play a very important role in the spectral graph theory, the sub-area of graph theory dealing with linear algebraic study of graphs.

Written with multiplicities, a degree sequence in general is written as

Let D be a set of some non-decreasing non-negative integers. We say that a graph G is a realization of the set D if the degree sequence of G is equal to D. It is clear from the definition that for a realizable degree sequence, there is at least one graph having this degree sequence. For example, the completely different two graphs in Figure 1 have the same degree sequence.

There are many results and algorithms to determine whether a given set of non-negative integers is realizable or not, the most famous one being Havel-Hakimi’s, see ^{1, 2}. Of course, the most obvious criteria that arises from the handshaking lemma says that the sum of all vertex degrees, being equal to twice the number of edges, must be even.

We shall classify our graphs according to whether they have at least one cycle or not. Those graphs having no cycle will be called acyclic. For example, all trees are acyclic. The remaining graphs are called cyclic graphs.

2. How the Invariant Arose?

It is well-known that the number a₁ of leaves (pendant vertices) of any given tree T is given by

(1)

where is the largest vertex degree in T and denotes the number of vertices of degree i. Note that the equation (1) can be rearranged as

(2)

Motivated by this fact, the authors studied a large number of graph realizations of given realizable degree sequences and observed that the left hand side of this equation is a graph invariant. We denote this number by Ω. This invariant has a big potential to give structural and combinatorial information about a graph just by means of its degree sequence:

Definition 2.1. Let be a realizable degree sequence and its realization be the graph The of G is defined in terms of the degree sequence as

With slight abuse of language, we shall sometimes use the expression for the of a given degree sequence. To understand , let us take the graph G in Figure 2.

It has the degree sequence . The of G is

has the following important computational property:

Theorem 2.1. For any graph G,

Proof. By the Handshaking lemma, we have

impliying the result as

It follows that

Theorem 2.2. For any graph is even.

This has the following obvious test for the realizability of a given degree sequence:

Corollary 2.1. Let D be a set of non-negative integers. If Ω(D) is odd, then D is not realizable.

As usual, let P_n, C_n, S_n, K_n, T_r,s and K_r,s, where n = r + s denote the path, cycle, star, complete, tadpole and complete bipartite graphs with n vertices, respectively. Let T denote a tree. For these well-known graph classes, the is as follows.

Example 2.1. The of some well-known graph classes are

One must note that the of a path, star or tree is equal to −2. This is in fact true for all connected acyclic graphs as we shall see.

3. Properties of Ω

We now deal with some properties of . We first study the number r of the closed regions (faces) which are bounded by the edges of the graph G. That is, the region outside the graph does not count. Note that a closed region could be bounded by any n-cycle (n-gon) where n ≥ 3, a loop (1-gon) or multiple edges (2-gon).

Theorem 3.1. Let If D is realizable as a connected planar graph G, then the number r of closed regions is given by

Proof. Recall that n − m + r = 1 by the Euler formula. Putting the values of n and m in terms of vertex degrees gives

As we shall often deal with disconnected graphs, the following useful result that shows that of a graph G is additive over the set of the components of G will be needed:

Theorem 3.2. Let G be a disconnected graph with c components Then

The following is a direct generalization of Theorem 3.1 to disconnected graphs:

Corollary 3.1. Let be realizable as a graph G with c components. The number r of faces of G is given by

As r ≥ 0, we have the following very important property:

Corollary 3.2. For each graph G, we have

Equivalently,

The following result gives the relation between χ and Ω:

Lemma 3.1. For any graph, we have

Proof. Let G have n vertices, m edges and r regions. Recall that by Corollary 3.1 and by Theorem 2.1. Hence the result follows.

Theorem 3.3. Let and let If D is realizable as a connected graph G, then

where l is the number of loops, ch is the number of chords and e_m is the number of multiple edges in G.

Proof. When , G has no loops or chords and the theorem is satisfied. Let therefore . Let us try to draw a realization of D. If we draw an and as above start adding pendant edges such that one pendant edge to of the vertices, two to of the vertices, three to of the vertices, · · · , to of the vertices, we are not able to draw all of these pendant edges as we only have a₁ times 1’s in D and by assumption That is, of the planned pendant edges can not be realized as we do not have enough 1’s. After adding the existing 1’s, some vertices have degrees less than they should have. Note that drawing a pendant edge at a vertex u adds a 1 and also increase the degree of u by 1. Therefore, not to add new 1’s, we do, instead of drawing two pendant edges at two different vertices u, v on draw a chord. In that way we increase the degrees of u and v by 1 without needing any 1’s. Similarly, the effect of adding two pendant edges is the same with adding a loop. So therefore, the realization of D must have loops and chords and their number would be

If u and v are two vertices on the largest cycle in G having a chord in between, and if w is one of the neighbours of v on the largest cycle, interchanging v and w transforms the chord to a pair of multiple edges. So the total number of loops, chords and multiple edges in all realizations of a given degree sequence is fixed. The result then follows.

A direct result of this Theorem is as follows:

Corollary 3.3. If , then the Euler characteristic of a connected realization G of D is given by

Sometimes, it may not be very easy to count the closed regions one by one. For example, in the graph in Figure 3, it is not an easy task to count the closed regions as most of them are overlapping.

Note that in Figure 3, there are no loops nor multiple edges. So we only need to count the chords. There are seven of them which implies that there are eight closed regions. Figure 4 shows another drawing of the same graph and here it is obvious that there are indeed eight non-overlapping closed regions.

As another example, look at the graph in Figure 5.

There are five chords and three cut vertices each connecting two closed regions. So one added to 5+3=8 gives 9 which is the number of closed regions. By Theorem 2.3, as we obtain the number of closed regions as as .

The following is an interesting relation between Ω, m and n:

Corollary 3.4. Let G be a connected graph. If for an integer then

Proof. By Theorem 2.1, we have giving the result.

We shall often come up with unicyclic graphs which are graphs with only one closed region, that is a cycle with at least three edges, a pair of multiple edges or a loop. By Theorem 3.1, we have = 0 for all unicyclic graphs. The following result then directly follows:

Corollary 3.5. Let G be a connected graph. If then

Similarly, we can say that for bicyclic and three-cyclic connected graphs, we have the relations m = n + 1 and m = n + 2, respectively.

We also have

Lemma 3.3. Let G be a graph with m > n = 3. Then G has at least one multiple edge or loop.

Proof. If n = 3, then form a triangle using three of m > 3 edges and all three vertices. If we do not form a triangle, we have to have a loop or multiple edges. As there is no place for chords in a triangle, all the remaining edges must be loops or multiple edges.

Theorem 3.4. Let the degree sequence

be realizable as a graph G with c components, ch chords, l loops, e_m multiple edges. Let n_c denote the number of edges of the largest cycle in G. If then

Proof. It is known that by Theorem 3.3. To prove the second equality, we count the degrees of vertices on the unique cycle in two ways: Note that all the vertices are either on the largest cycle or are pendant. First recall that Excluding one ends of all pendant edges as these ends are pendant and therefore not on the cycle, we get the sum of the degrees of the vertices lying on the largest cycle as Also the edges incident to the vertices on the cycle are chords, loops, multiple edges or the edges of the cycle itself. That is

The result then follows.

The following is a direct and useful result when :

Corollary 3.6. If , then any realization of D has no chords, loops nor multiple edges.

References