# Maximum nullity of outerplanar graphs and the path cover number

- Authors
- Journal
- Linear Algebra and its Applications 0024-3795
- Publisher
- Elsevier
- Publication Date
- Volume
- 432
- Issue
- 8
- Identifiers
- DOI: 10.1016/j.laa.2009.08.033
- Keywords

## Abstract

Abstract Let G = ( V , E ) be a graph with V = { 1 , 2 , … , n } . Define S ( G ) as the set of all n × n real-valued symmetric matrices A = [ a ij ] with a ij ≠ 0 , i ≠ j if and only if ij ∈ E . By M ( G ) we denote the largest possible nullity of any matrix A ∈ S ( G ) . The path cover number of a graph G , denoted P ( G ) , is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G . There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T , M ( T ) = P ( T ) . Barioli et al. [2], show that for a unicyclic graph G , M ( G ) = P ( G ) or M ( G ) = P ( G ) - 1 . Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G , M ( G ) ⩽ P ( G ) . Further we show that for any partial 2-path G , M ( G ) = P ( G ) .

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