Skip to search boxSkip to navigationSkip to main content

Maximum nullity of outerplanar graphs and the path cover number

Output:
Contribution to journal
Article
Academic
Peer-review

Information

Output type

Output:
Contribution to journal
Article
Academic
Peer-review

Original language

English

Pages from-to (Number of pages)

Pages 2052-2060

Journal (Volume, Issue Number)

Linear Algebra and Its Applications (Volume 432, Issue 8)

Publication milestones

  • Published - 2010

Publication status

Published - 2010

ISSN

0024-3795

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=[aij] with aij¿0,i¿j if and only if ijeE. By M(G) we denote the largest possible nullity of any matrix AeS(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).

Metrics

Metrics

SciVal
FWCI
2.23
SciVal
Author count
1
SciVal
Paper percentile
88
SciVal
citations
13
Scopus
citations
13

PlumX, opens in new tab

Captures
5
Citation count
13