Advanced Studies on Bipartite and Multipartite Graphs: Co-Complete Properties, Structural Transformations, Equitable Domination, and Graph-Valued Functions

Abstract

Bipartite graphs partition vertices into two independent sets with edges only between sets, forming foundational structures in network theory. This paper extends analysis to k-partite graphs and introduces co-complete variants where vertices within the same partition maintain distance exactly two via unique P3-paths, generalizing the friendship theorem. We characterize k(G), the minimal partition number for co-completeness, deriving explicit formulas for cycles C_n (n ≥ 7): k(C_n)=⌈n/2⌉ for odd n, n/2 if n ≡ 0 mod 4, and n/2+1 if n ≡ 2 mod 4. Transformations via edge deletions from complete k-partite graphs preserve co-completeness under matching constraints, yielding (n - β₁)-partite structures where β₁ is the matching number. Equitable domination, requiring balanced neighborhood degrees differing by at most 1, is bounded in bipartite graphs by γ_eq(G) ≤ (3/8)n for C4-free cases. Graph-valued functions over semirings map these to middle/total graphs, preserving regularity. Results unify coloring, distance properties, and optimization, with applications in fault-tolerant networks and social modeling. New theorems on spanning subgraphs and valued homomorphisms fill literature gaps. Future directions include algorithmic computation of k(G) and quantum extensions.