共查询到20条相似文献,搜索用时 15 毫秒
1.
The nullity of a graph is defined to be the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. In this paper, we obtain the nullity set of bipartite graphs of order n, and characterize the bipartite graphs with nullity n-4 and the regular bipartite graphs with nullity n-6. 相似文献
2.
Let G be a simple graph of order n and A(G) be its adjacency matrix. The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in the spectrum of A(G). Denote by Ck and Lk the set of all connected graphs with k induced cycles and the set of line graphs of all graphs in Ck, respectively. In 1998, Sciriha [I. Sciriha, On singular line graphs of trees, Congr. Numer. 135 (1998) 73-91] show that the order of every tree whose line graph is singular is even. Then Gutman and Sciriha [I. Gutman, I. Sciriha, On the nullity of line graphs of trees, Discrete Math. 232 (2001) 35-45] show that the nullity set of L0 is {0,1}. In this paper, we investigate the nullity of graphs with cut-points and deduce some concise formulas. Then we generalize Scirihas' result, showing that the order of every graph G is even if such a graph G satisfies that G∈Ck and η(L(G))=k+1, and the nullity set of Lk is {0,1,…,k,k+1} for any given k, where L(G) denotes the line graph of the graph G. 相似文献
3.
The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. In this paper, we obtain the nullity set of bicyclic graphs of order n, and determine the bicyclic graphs with maximum nullity. 相似文献
4.
Darren D. Row 《Linear algebra and its applications》2012,436(12):4423-4432
The zero forcing number of a graph is the minimum size of a zero forcing set. This parameter is useful in the minimum rank/maximum nullity problem, as it gives an upper bound to the maximum nullity. Results for determining graphs with extreme zero forcing numbers, for determining the zero forcing number of graphs with a cut-vertex, and for determining the zero forcing number of unicyclic graphs are presented. 相似文献
5.
6.
The nullity of a graph G is defined to be the multiplicity of the eigenvalue zero in its spectrum. In this paper we characterize the unicyclic graphs with nullity one in aspect of its graphical construction. 相似文献
7.
The maximum nullity over a collection of matrices associated with a graph has been attracting the attention of numerous researchers for at least three decades. Along these lines various zero forcing parameters have been devised and utilized for bounding the maximum nullity. The maximum nullity and zero forcing number, and their positive counterparts, for general families of line graphs associated with graphs possessing a variety of specific properties are analysed. Building upon earlier work, where connections to the minimum rank of line graphs were established, we verify analogous equations in the positive semidefinite cases and coincidences with the corresponding zero forcing numbers. Working beyond the case of trees, we study the zero forcing number of line graphs associated with certain families of unicyclic graphs. 相似文献
8.
A mixed graph means a graph containing both oriented edges and undirected edges. The nullity of the Hermitian-adjacency matrix of a mixed graph G, denoted by ηH(G),is referred to as the multiplicity of the eigenvalue zero. In this paper, for a mixed unicyclic graph G with given order and matching number, we give a formula on ηH(G), which combines the cases of undirected and oriented unicyclic graphs and also corrects an error in Theorem 4.2 of [Xueliang LI, Guihai YU. The skew-rank of oriented graphs. Sci. Sin. Math., 2015, 45:93-104(in Chinese)]. In addition, we characterize all the n-vertex mixed graphs with nullity n-3, which are determined by the spectrum of their Hermitian-adjacency matrices. 相似文献
9.
令$\eta(\Gamma)$和$c(\Gamma)$是符号图$\Gamma$的零度和基本圈数. 一个符号圈拼接图是指每个块都是圈的连通符号图. 本文证明了对任意符号拼接图$\eta(\Gamma)\le c(\Gamma)+1$成立, 并且刻画了等号成立的极图, 推广了王登银等人(2022)在简单圈拼接图上的结果. 此外, 我们证明了任意的符号拼接图$\eta(\Gamma)\neq c(\Gamma)$, 给出了满足$\eta(\Gamma)=c(\Gamma)-1$的符号拼接图的一些性质并刻画处$\eta(\Gamma)=c(\Gamma)-1$的二部符号拼接图. 相似文献
10.
Let Γ be a signed graph and A(Γ) be the adjacency matrix of Γ. The nullity ofΓ is the multiplicity of eigenvalue zero in the spectrum of A(Γ). In this paper, the connected bicyclic signed graphs(including simple bicyclic graphs) of order n with nullity n-7 are completely characterized. 相似文献
11.
林跃峰 《数学的实践与认识》2013,43(10)
研究次极大图(即链环分支数等于基圈数的连通平图)的唯一性.证明了无割点且包含子图K_4的连通平图G是次极大图当且仅当G同构于K_4,并刻画了包含子图K_4的次极大图的结构. 相似文献
12.
G. R. Omidi 《Graphs and Combinatorics》2009,25(1):111-114
The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. We obtain some lower bounds for the nullity
of graphs and we then find the nullity of bipartite graphs with no cycle of length a multiple of 4 as a subgraph. Among bipartite
graphs on n vertices, the star has the greatest nullity (equal to n − 2). We generalize this by showing that among bipartite graphs with n vertices, e edges and maximum degree Δ which do not have any cycle of length a multiple of 4 as a subgraph, the greatest nullity is .
G. R. Omidi: This research was in part supported by a grant from IPM (No.87050016). 相似文献
13.
Bo Cheng 《Linear algebra and its applications》2011,434(8):1799-1810
The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. It is known that η(G)?n-2 if G is a simple graph on n vertices and G is not isomorphic to nK1. The extremal graphs attaining the upper bound n-2 and the second upper bound n-3 have been obtained. In this paper, the graphs with nullity n-4 are characterized. Furthermore the tricyclic graphs with maximum nullity are discussed. 相似文献
14.
Didar A. Ali John Baptist Gauci Irene Sciriha Khidir R. Sharaf 《Czechoslovak Mathematical Journal》2016,66(3):971-985
The nullity of a graph G is the multiplicity of zero as an eigenvalue in the spectrum of its adjacency matrix. From the interlacing theorem, derived from Cauchy’s inequalities for matrices, a vertex of a graph can be a core vertex if, on deleting the vertex, the nullity decreases, or a Fiedler vertex, otherwise. We adopt a graph theoretical approach to determine conditions required for the identification of a pair of prescribed types of root vertices of two graphs to form a cut-vertex of unique type in the coalescence. Moreover, the nullity of subgraphs obtained by perturbations of the coalescence G is determined relative to the nullity of G. This has direct applications in spectral graph theory as well as in the construction of certain ipso-connected nano-molecular insulators. 相似文献
15.
For a graph G of order n, the maximum nullity of G is defined to be the largest possible nullity over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Maximum nullity and the related parameter minimum rank of the same set of matrices have been studied extensively. A new parameter, maximum generic nullity, is introduced. Maximum generic nullity provides insight into the structure of the null-space of a matrix realizing maximum nullity of a graph. It is shown that maximum generic nullity is bounded above by edge connectivity and below by vertex connectivity. Results on random graphs are used to show that as n goes to infinity almost all graphs have equal maximum generic nullity, vertex connectivity, edge connectivity, and minimum degree. 相似文献
16.
We obtain spectral properties of the Pascal graphs by exploring its spectral graph invariants such as the algebraic connectivity, the first three largest Laplacian eigenvalues and the nullity. Some open problems pertaining to the Pascal graphs are given. 相似文献
17.
Shuchao Li 《Linear algebra and its applications》2008,429(7):1619-1628
The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. Cheng and Liu [B. Cheng, B. Liu, On the nullity of graphs, Electron. J. Linear Algebra 16 (2007) 60-67] characterized the extremal graphs attaining the upper bound n-2 and the second upper bound n-3. In this paper, as the continuance of it, we determine the extremal graphs with pendent vertices achieving the third upper bound n-4 and fourth upper bound n-5. We then proceed recursively to construct all graphs with pendent vertices which satisfy η(G)>0. Our results provide a unified approach to determine n-vertex unicyclic (respectively, bicyclic and tricyclic) graphs which achieve the maximal and second maximal nullity and characterize n-vertex extremal trees attaining the second and third maximal nullity. As a consequence we, respectively, determine the nullity sets of trees, unicyclic graphs, bicyclic graphs and tricyclic graphs on n vertices. 相似文献
18.
Let G be a graph with n(G) vertices and m(G) be its matching number.The nullity of G,denoted by η(G),is the multiplicity of the eigenvalue zero of adjacency matrix of G.It is well known that if G is a tree,then η(G) = n(G)-2m(G).Guo et al.[Jiming GUO,Weigen YAN,Yeongnan YEH.On the nullity and the matching number of unicyclic graphs.Linear Alg.Appl.,2009,431:1293 1301]proved that if G is a unicyclic graph,then η(G)equals n(G)-2m(G)-1,n(G)-2m(G),or n(G)-2m(G) +2.In this paper,we prove that if G is a bicyclic graph,then η(G) equals n(G)-2m(G),n(G)-2m(G)±1,n(G)-2m(G)±2or n(G)-2m(G) + 4.We also give a characterization of these six types of bicyclic graphs corresponding to each nullity. 相似文献
19.
Milan Nath 《Linear and Multilinear Algebra》2013,61(2):255-264
The nullity η(G) of a graph G is the multiplicity of zero as an eigenvalue of the adjacency matrix of G. If η(G)?=?1, then the core of G is the subgraph induced by the vertices associated with the nonzero entries of the kernel eigenvector. The set of vertices which are not in the core is the periphery of G. A graph G with nullity one is minimal configuration if no two vertices in the periphery are adjacent and deletion of any vertex in the periphery increases the nullity. An ∞-graph ∞(p,?l,?q) is a graph obtained by joining two vertex-disjoint cycles C p and C q by a path of length l?≥?0. Let ?* be the class of bicyclic graphs with an ∞-graph as an induced subgraph. In this article, we characterize the graphs in ?* which are minimal configurations. 相似文献
20.
单圈图的零度的一个注记 总被引:1,自引:0,他引:1
The number of zero eigenvalues in the spectrum of the graph G is called its nullity and is denoted by η(G).In this paper,we determine the all extremal unicyclic graphs achieving the fifth upper bound n-6 and the sixth upperbound n-7. 相似文献