共查询到20条相似文献,搜索用时 0 毫秒
1.
Yi-Zheng Fan 《Linear and Multilinear Algebra》2013,61(2):97-113
Using the result on Fiedler vectors of a simple graph, we obtain a property on the structure of the eigenvectors of a nonsingular unicyclic mixed graph corresponding to its least eigenvalue. With the property, we get some results on minimizing and maximizing the least eigenvalue over all nonsingular unicyclic mixed graphs on n vertices with fixed girth. In particular, the graphs which minimize and maximize, respectively, the least eigenvalue are given over all such graphs with girth 3. 相似文献
2.
LARGEST EIGENVALUE OF A UNICYCLIC MIXED GRAPH 总被引:3,自引:0,他引:3
FanYizheng 《高校应用数学学报(英文版)》2004,19(2):140-148
The graphs which maximize and minimize respectively the largest eigenvalue over all unicyclic mixed graphs U on n vertices are determined. The unicyclic mixed graphs U with the largest eigenvalue λ1 (U)=n or λ1 (U)∈ (n ,n 1] are characterized. 相似文献
3.
Let U(n,d) be the set of unicyclic graphs on n vertices with diameter d. In this article, we determine the unique graph with minimal least eigenvalue among all graphs in U(n,d). It is found that the extremal graph is different from that for the corresponding problem on maximal eigenvalue as done by Liu et al. [H.Q. Liu, M. Lu, F. Tian, On the spectral radius of unicyclic graphs with fixed diameter, Linear Algebra Appl. 420 (2007) 449-457]. 相似文献
4.
Shuchao Li 《Discrete Applied Mathematics》2009,157(7):1387-1395
Let Un,d denote the set of unicyclic graphs with a given diameter d. In this paper, the unique unicyclic graph in Un,d with the maximum number of independent sets, is characterized. 相似文献
5.
A unicyclic graph is a graph whose number of edges is equal to the number of vertices. Guo Shu-Guang [S.G. Guo, The largest Laplacian spectral radius of unicyclic graph, Appl. Math. J. Chinese Univ. Ser. A. 16 (2) (2001) 131–135] determined the first four largest Laplacian spectral radii together with the corresponding graphs among all unicyclic graphs on n vertices. In this paper, we extend this ordering by determining the fifth to the ninth largest Laplacian spectral radii together with the corresponding graphs among all unicyclic graphs on n vertices. 相似文献
6.
7.
Ji-Ming Guo 《Discrete Mathematics》2008,308(24):6115-6131
In this paper, the first five sharp upper bounds on the spectral radii of unicyclic graphs with fixed matching number are presented. The first ten spectral radii over the class of unicyclic graphs on a given number of vertices and the first four spectral radii of unicyclic graphs with perfect matchings are also given, respectively. 相似文献
8.
Given a graph we are interested in studying the symmetric matrices associated to with a fixed number of negative eigenvalues. For this class of matrices we focus on the maximum possible nullity. For trees this parameter has already been studied and plenty of applications are known. In this work we derive a formula for the maximum nullity and completely describe its behavior as a function of the number of negative eigenvalues. In addition, we also carefully describe the matrices associated with trees that attain this maximum nullity. The analysis is then extended to the more general class of unicyclic graphs. Further our work is applied to re-describing all possible partial inertias associated with trees, and is employed to study an instance of the inverse eigenvalue problem for certain trees. 相似文献
9.
Fielder [M. Fielder, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298-305] has turned out that G is connected if and only if its algebraic connectivity a(G)>0. In 1998, Fallat and Kirkland [S.M. Fallat, S. Kirkland, Extremizing algebraic connectivity subject to graph theoretic constraints, Electron. J. Linear Algebra 3 (1998) 48-74] posed a conjecture: if G is a connected graph on n vertices with girth g≥3, then a(G)≥a(Cn,g) and that equality holds if and only if G is isomorphic to Cn,g. In 2007, Guo [J.M. Guo, A conjecture on the algebraic connectivity of connected graphs with fixed girth, Discrete Math. 308 (2008) 5702-5711] gave an affirmatively answer for the conjecture. In this paper, we determine the second and the third smallest algebraic connectivity among all unicyclic graphs with vertices. 相似文献
10.
Let be a finite simple graph. For , the difference of , where is the neighborhood of and is called the critical difference of . is called a critical set if equals the critical difference and is the intersection of all critical sets. is the union of all critical independent sets. An independent set is an inclusion minimal set with if no proper subset of has positive difference.A graph is called a König–Egerváry graph if the sum of its independence number and matching number equals .In this paper, we prove a conjecture which states that for any graph the number of inclusion minimal independent set with is at least the critical difference of the graph.We also give a new short proof of the inequality .A characterization of unicyclic non-König–Egerváry graphs is also presented and a conjecture which states that for such a graph , the critical difference equals , is proved.We also make an observation about using Edmonds–Gallai Structure Theorem as a concluding remark. 相似文献
11.
12.
Given a simple graph with vertex set and edge set , the mixed graph is obtained from by orienting some of its edges. Let denote the Hermitian adjacency matrix of and be the adjacency matrix of . The -rank (resp. rank) of (resp. ), written as (resp. ), is the rank of (resp. ). Denote by the dimension of cycle space of , that is , where denotes the number of connected components of . In this paper, we concentrate on the relation between the -rank of and the rank of . We first show that for every mixed graph . Then we characterize all the mixed graphs that attain the above lower (resp. upper) bound. By these obtained results in the current paper, all the main results obtained in Luo et al. (2018); Wong et al. (2016) may be deduced consequently. 相似文献
13.
For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let G(n,p) denote the set of unicyclic graphs with n vertices and p pendent vertices. In [H. Hua, M. Wang, Unicyclic graphs with given number of pendent vertices and minimal energy, Linear Algebra Appl. 426 (2007) 478-489], Hua and Wang discussed the graphs that have minimal energy in G(n,p), and determined the minimal-energy graphs among almost all different cases of n and p. In their work, certain case of the values was left as an open problem in which the minimal-energy species have to be chosen in two candidate graphs, but cannot be determined by comparing of the corresponding coefficients of their characteristic polynomials. This paper aims at solving the problem completely, by using the well-known Coulson integral formula. 相似文献
14.
15.
We derive new estimates for the lowest eigenvalue of the Schrödinger operator associated with a star graph in R2. We achieve this by a variational method and a procedure for identifying test functions which are sympathetic to the geometry of the star graph. 相似文献
16.
Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum. 相似文献
17.
J.P. Grossman 《Discrete Mathematics》2005,300(1-3):225-228
We present a lower bound for the smallest non-zero eigenvalue of the Laplacian of an undirected graph. The bound is primarily useful for graphs with small diameter. 相似文献
18.
19.
20.
Consider an eigenvector of the adjacency matrix of a G(n,p) graph. A nodal domain is a connected component of the set of vertices where this eigenvector has a constant sign. It is known that with high probability, there are exactly two nodal domains for each eigenvector corresponding to a nonleading eigenvalue. We prove that with high probability, the sizes of these nodal domains are approximately equal to each other. 相似文献