Back to Search
Start Over
Extremal problems on components and loops in graphs
- Publication Year :
- 2019
- Publisher :
- Springer, 2019.
-
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.
- Subjects :
- Social connectedness
General Mathematics
0102 computer and information sciences
Acyclic graph
01 natural sciences
Omega
Connectedness
Combinatorics
symbols.namesake
Euler characteristic
Realizability
0101 mathematics
Graph property
Connectivity
Mathematics, applied
Mathematics
Cyclic graph
Degree Sequence
Split Graph
Graph
Applied Mathematics
010102 general mathematics
Graph theory
Graph characteristic
Degree sequence
010201 computation theory & mathematics
symbols
05C30
05C35
05C10
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....161fbccc59055c7f46b65e3739be4ff8