A note on triangle-free graphs

2011/01/17 by Vahan Mkrtchyan, Petros A. Petrosyan, Mkrtchyan, Vahan V. +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1101.3188

openalex publication_date 2011/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that if G is a simple triangle-free graph with n≥ 3 vertices, without a perfect matching, and having a minimum degree at least (n-1)/(2), then G is isomorphic either to C₅ or to K_{(n-1)/(2),(n+1)/(2)}.

Citations

• Note on Hamilton Circuits

Related

• Triangle-free Graphs with Large Minimum Common Degree
• Edge number critical triangle free graphs with low independence numbers
• The Generic Circular Triangle-Free Graph
• An invariant for minimum triangle-free graphs
• Forbidden pairs for equality of edge-connectivity and minimum degree