Existence of connected regular and nearly regular graphs

2018/01/25 by Ghurumuruhan Ganesan, Ganesan, Ghurumuruhan · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Finite Group Theory Research #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1801.08345

arxiv created 2018/01/25 · openalex publication_date 2018/01/25 · arxiv updated 2018/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For integers k ≥ 2 and n ≥ k+1, we prove the following: If n⋅ k is even, there is a connected k-regular graph on n vertices. If n⋅ k is odd, there is a connected nearly k-regular graph on n vertices.

Cited by

• Locally Differentially Private Analysis of Graph Statistics

Related

• Even and Odd Cycles Passing a Given Edge or a Vertex
• Characterization of Equimatchable Even-Regular Graphs
• There is no (95,40,12,20) strongly regular graph
• Gaps Between Almost-Primes and a Construction of Almost-Ramanujan Graphs
• Independent sets in certain classes of (almost) regular graphs