“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 8861
School of Mathematics
  Title:   On eigensharp and almost eigensharp graphs
  Author(s): 
1.  E. Ghorbani
2.  H. R. Maimani
  Status:   Published
  Journal: Linear Algebra Appl.
  Vol.:  429
  Year:  2008
  Pages:   2746-2753
  Supported by:  IPM
  Abstract:
The minimum number of complete bipartite subgraphs needed to partition the edges of a graph G is denoted by b(G). A known lower bound on b(G) states that b(G) ≥ max {p(G), q(G)}, where p(G) and q(G) are the numbers of positive and negative eigenvalues of the adjacency matrix of G, respectively. When equality is attained, G is said to be eigensharp and when b(G)=max{p(G), q(G)} + 1, G is called an almost eigensharp graph. In this paper we investigate the eigensharpness of graphs with at most one cycle and products of some families of graphs. Among the other results, we show that PmPn, CmPn for m ≡ 2,3 (mod 4) and Qn when n is odd are eigensharp. We obtain some results on almost eigensharp graphs as well.

Download TeX format
back to top
scroll left or right