Affordable Access

Publisher Website

On eigensharp and almost eigensharp graphs

Authors
Journal
Linear Algebra and its Applications
0024-3795
Publisher
Elsevier
Publication Date
Volume
429
Identifiers
DOI: 10.1016/j.laa.2008.05.005
Keywords
  • Eigensharp Graphs
  • Almost Eigensharp Graphs
  • Products Of Graphs

Abstract

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 P m ∨ P n , C m ∨ P n for m ≡ 2 , 3 ( mod 4 ) and Q n when n is odd are eigensharp. We obtain some results on almost eigensharp graphs as well.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

On almost distance-regular graphs

on Journal of Combinatorial Theor... Jan 01, 2011

Almost rank three graphs

on Discrete Mathematics Jan 01, 1992
More articles like this..