FORMULATING EDGE COVERAGE CONSTRAINTS AND ANALYZING CONNECTIVITY CONDITIONS ON BUTTERFLY GRAPHS
Megha Chandraprakash Gaikwad
Assistant Professor, Shri Sheth Muralidharji Mansingaka Arts, science and commerce College, Pachora , Dist. Jalgaon, Maharashtra
Abstract
The Weighted Connected Vertex Cover (W-CVC) problem is a significant combinatorial optimization problem that integrates vertex coverage, connectivity, and weight minimization. This paper focuses on the formulation of edge coverage constraints and the analysis of connectivity conditions specifically on butterfly graphs, a structured class of graphs widely used in parallel computing and communication networks. By exploiting the inherent structural properties of butterfly graphs, particularly the presence of an articulation vertex, the study presents a simplified and efficient framework for solving the W-CVC problem. The work highlights how structural decomposition reduces computational complexity and enables the derivation of a closed-form solution.
Keywords: Vertex Cover, Connected Vertex Cover, Butterfly Graph, Edge Coverage, Connectivity Constraints, Graph Optimization
Journal Name :
VIEW PDF
EPRA International Journal of Multidisciplinary Research (IJMR)
VIEW PDF
Published on : 2026-04-19
| Vol | : | 12 |
| Issue | : | 4 |
| Month | : | April |
| Year | : | 2026 |