Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

A New Graph Invariant

Sadik Delen, Ismail Naci Cangul*

Faculty of Arts and Science, Department of Mathematics, Uludag University, 16059 Bursa, Turkey

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.

Keywords: graph characteristic, connectedness, cyclic graph, acyclic graph, degree sequence

Received November 20, 2017; Revised January 08, 2018; Accepted February 19, 2018

Citation: Sadik Delen, Ismail Naci Cangul, A New Graph Invariant. Turkish Journal of Analysis and Number Theory, 6 (1). 30-33. January 2018. doi:10.12691/tjant-6-1-4

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

Figure 1. Graphs with the same DS

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

[picture] | (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

[picture] | (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.

Figure 2. A graph G with Ω(G) = 10

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 Pn, Cn, Sn, Kn, Tr,s and Kr,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 em 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.

Figure 3. Counting the closed regions is difficult

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.

Figure 4. Counting the closed regions in Figure 3 is now easy

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

Figure 5. A connected graph

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, em multiple edges. Let nc 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

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