2011/11/23 by Asen Bojilov, A. I. Bojilov, Bojilov, A. I. +3 · 1 citation
Computer Science · Mathematics · #05C35 (Primary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C35
paper · pdf · doi:10.48550/arxiv.1111.5598
5 pages
arxiv created 2011/11/23 · openalex publication_date 2011/11/23 · arxiv updated 2011/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a simple n-vertex graph with degree sequence d1,d2,...,dn and vertex set \V(G). The degree of v∈\V(G) is denoted by \D(v). The smallest integer r for which \V(G) has an r-partition \V(G)=V1∪ V2∪...∪ Vr, Vi∩ Vj=∅, ,i≠ j such that \D(v)≤ n-\absVi, ∀ v∈ Vi, i=1,2,...,r is denoted by \f(G). In this note we prove the inequality \f(G)≥\frac nn-d, where d=√\dfracd12+d22+...+dn2n.