ISSN(Print): 2333-1100
ISSN(Online): 2333-1232

Article Versions

Export Article

Cite this article

- Normal Style
- MLA Style
- APA Style
- Chicago Style

Research Article

Open Access Peer-reviewed

Sadik Delen, Ismail Naci Cangul^{ }

Received November 20, 2017; Revised February 08, 2018; Accepted March 02, 2018

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.

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.

It is well-known that the number *a*_{1} 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.

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*_{1} 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*.

[1] | S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a graph, J. SIAM Appl. Math., 10 (1962), 496-506. | ||

In article | View Article | ||

[2] | V. Havel, A remark on the existence of finite graphs (Czech), Časopic Pěst. Mat., 80 (1955), 477-480. | ||

In article | |||

Published with license by Science and Education Publishing, Copyright © 2018 Sadik Delen and Ismail Naci Cangul

This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Sadik Delen, Ismail Naci Cangul. A New Graph Invariant. *Turkish Journal of Analysis and Number Theory*. Vol. 6, No. 1, 2018, pp 30-33. http://pubs.sciepub.com/tjant/6/1/4

Delen, Sadik, and Ismail Naci Cangul. "A New Graph Invariant." *Turkish Journal of Analysis and Number Theory* 6.1 (2018): 30-33.

Delen, S. , & Cangul, I. N. (2018). A New Graph Invariant. *Turkish Journal of Analysis and Number Theory*, *6*(1), 30-33.

Delen, Sadik, and Ismail Naci Cangul. "A New Graph Invariant." *Turkish Journal of Analysis and Number Theory* 6, no. 1 (2018): 30-33.

Share

[1] | S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a graph, J. SIAM Appl. Math., 10 (1962), 496-506. | ||

In article | View Article | ||

[2] | V. Havel, A remark on the existence of finite graphs (Czech), Časopic Pěst. Mat., 80 (1955), 477-480. | ||

In article | |||