Article ID Journal Published Year Pages File Type
6416044 Linear Algebra and its Applications 2016 6 Pages PDF
Abstract

Let G be a graph of order n and size m, and let mck(G) be the maximum size of a k-cut of G. It is shown thatmck(G)≤k−1k(m−μmin(G)n2),where μmin(G) is the smallest eigenvalue of the adjacency matrix of G.An infinite class of graphs forcing equality in this bound is constructed.

Related Topics
Physical Sciences and Engineering Mathematics Algebra and Number Theory
Authors
,