02139176

j

02139176 Will, Todd G. Hulett, Heather Parsimonious multigraphs. SIAM J. Discrete Math. 18, No. 2, 241-245 (2004). 2004 Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA EN degree sequence

doi:10.1137/S0895480103432477

Summary: We view a loopless multigraph as a complete graph with nonnegative integer edge weights indicating the multiplicity of each edge. A multigraph realization of a given degree sequence is parsimonious if it has the least number of positive weight edges. We characterize the graphs that can appear as components in a parsimonious multigraph and show that minimizing the number of positive weight edges is equivalent to maximizing the number of cycle-free components.