Affordable Access

Publisher Website

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
  • Minimum Rank
  • Graph
  • Path Cover Number
  • Outerplanar
  • Partial 2-Path
  • Symmetric

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.