کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4602124 1336916 2010 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Maximum nullity of outerplanar graphs and the path cover number
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
Maximum nullity of outerplanar graphs and the path cover number
چکیده انگلیسی

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 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).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 432, Issue 8, 1 April 2010, Pages 2052-2060