首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Maximum nullity of outerplanar graphs and the path cover number
Authors:John Sinkovic
Institution:Department of Mathematics, Brigham Young University, Provo, UT 84602, United States
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,ij if and only if ijE. By M(G) we denote the largest possible nullity of any matrix AS(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).
Keywords:05C50  05C10  15A18  15A03  15B57
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号