Counting Connected Partitions of Graphs

2022/10/20 by Yair Caro, Balázs Patkós, Caro, Yair +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2210.11032

openalex publication_date 2022/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Motivated by the theorem of Gy\H ori and Lovász, we consider the following problem. For a connected graph G on n vertices and m edges determine the number P(G,k) of unordered solutions of positive integers ∑_i=1^k m_i = m such that every m_i is realized by a connected subgraph H_i of G with m_i edges such that ∪_i=1^kE(H_i)=E(G). We also consider the vertex-partition analogue. We prove various lower bounds on P(G,k) as a function of the number n of vertices in G, as a function of the average degree d of G, and also as the size CMC_r(G) of r-partite connected maximum cuts of G. Those three lower bounds are tight up to a multiplicative constant. We also prove that the number π(G,k) of unordered k-tuples with ∑_i=1^kn_i=n, that are realizable by vertex partitions into k connected parts of respective sizes n₁,n₂,…,n_k, is Ω(d^k-1).

Related

• Incidence bounds on Edge Partitions of K_n
• A note on vertex partitions
• Connected Partitions via Connected Dominating Sets
• On a specific problem of partition of graph
• Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs