Extremal Problems on Components and Loops in Graphs |
| |
Authors: | Sadik Delen Ismail Naci Cangul |
| |
Institution: | Uludag University, Mathematics Department, Gorukle 16059 Bursa, TURKEY |
| |
Abstract: | The authors recently defined a new graph invariant denoted by Ω(G) only in terms of a given degree sequence which is also related to the Euler characteristic. It has many important combinatorial applications in graph theory and gives direct information compared to the better known Euler characteristic on the realizability, connectedness, cyclicness, components, chords, loops etc. Many similar classification problems can be solved by means of Ω. All graphs G so that
$$\Omega(G)\leq-4$$
are shown to be disconnected, and if
$$\Omega(G)\geq-2$$
, then the graph is potentially connected. It is also shown that if the realization is a connected graph and
$$\Omega(G)\geq-2$$
, then certainly the graph should be a tree. Similarly, it is shown that if the realization is a connected graph G and
$$\Omega(G)\geq0$$
, then certainly the graph should be cyclic. Also, when
$$\Omega(G)\geq-4$$
, the components of the disconnected graph could not all be cyclic and if all the components of G are cyclic, then
$$\Omega(G)\geq0$$
. In this paper, we study an extremal problem regarding graphs. We find the maximum number of loops for three possible classes of graphs. We also state a result giving the maximum number of components amongst all possible realizations of a given degree sequence. |
| |
Keywords: | Graph characteristic connectedness cyclic graph acyclic graph degree sequence |
本文献已被 CNKI 维普 SpringerLink 等数据库收录! |
| 点击此处可从《数学学报(英文版)》浏览原始摘要信息 |
| 点击此处可从《数学学报(英文版)》下载免费的PDF全文 |
|