Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Electronic Journal of Graph Theory and Applications (EJGTA)
Filipovski, Slobodan
Faculty of Mathematics, Natural Sciences and Information Technologies University of Primorska, Glagoljaška 8 6000 Koper, Slovenia
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
A refined Tur'an theorem Filipovski, Slobodan
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 12, No 1 (2024): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2024.12.1.2

Abstract

Let G = (V, E) be a finite undirected graph with vertex set V(G) of order |V(G)| = n and edge set E(G) of size |E(G)| = m. Let Δ = d1 ≥ d2 ≥ ⋯ ≥ dn = δ be the degree sequence of the graph G. A clique in a graph G is a complete subgraph of G. The clique number of a graph G, denoted by ω(G), is the order of a maximum clique of G. In 1907 Mantel proved that a triangle-free graph with n vertices can contain at most ⌊n2/4⌋ edges. In 1941 Tur'an generalized Mantel’s result to graphs not containing cliques of size r by proving that graphs of order n that contain no induced Kr have at most (1 − 1/r − 1)n2/2 edges. In this paper, we give new bounds for the maximum number of edges in a Kr-free graph G of order n, minimum degree δ, and maximum degree Δ. We show that, for the families of graphs having the above properties, our bounds are slightly better than the more general bounds of Tur'an.
Co-Authors