Incidence bounds on Edge Partitions of K_n

2020/09/05 by Andean E. Medjedovic, Medjedovic, Andean E.
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #math.CO

paper · pdf · doi:10.48550/arxiv.2009.02453

9 pages

openalex publication_date 2020/09/05 · arxiv created 2020/10/04 · arxiv updated 2020/10/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We solve a problem conjectured by Cheriyan, giving sharp bounds for incidence of certain edge partitions of the connected graph on n-vertices. We briefly discuss the history of the problem and relation to node connectivity of strongly regular graphs. We show that the bound cannot be made sharper.

Citations

• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs

Related

• Incidence bounds via extremal graph theory
• On a specific problem of partition of graph
• Counting Connected Partitions of Graphs
• On the extremal number of incidence graphs
• Incidence-free sets and edge domination in incidence graphs