共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
设T为含n个顶点的树,L(T)为其Laplace矩阵,L(T)的次小特征值α(T)称为T的代数连通度,Fiedlcr给出如下关于α(T)的界的经典结论α(Pn)≤α(T)≤α(Sn),其中Pn,Sn分别为含有n个顶点的路和星.Merris和Mass独立地证明了:α(T)=α(Sn)当且仅当T=Sn.通过重新组合由Fiedler向量所赋予的顶点的值,本给出上述不等式的新证明,并证明了:α(T)=α(Pn)当且仅当T=Pn。 相似文献
3.
图G=(V,E)的次小的拉普拉斯特征值称为G的代数连通度,记为α(G).设δ(G)为G的最小度.Fiedler早在1973年便证明了α(G)≤δ(G),但他未能给出等号成立的极图刻划.后来,我们在[6]中确定了当δ(G)≤1/2|V(G)|时α(G)=δ(G)的充要条件.本文中,我们将确定任意情况下α(G)=δ(G)成立的所有极图. 相似文献
4.
5.
Mihai Ciucu 《Journal of Algebraic Combinatorics》1996,5(2):87-103
We introduce a family of graphs, called cellular, and consider the problem of enumerating their perfect matchings. We prove that the number of perfect matchings of a cellular graph equals a power of 2 times the number of perfect matchings of a certain subgraph, called the core of the graph. This yields, as a special case, a new proof of the fact that the Aztec diamond graph of order n introduced by Elkies, Kuperberg, Larsen and Propp has exactly 2
n(n+1)/2 perfect matchings. As further applications, we prove a recurrence for the number of perfect matchings of certain cellular graphs indexed by partitions, and we enumerate the perfect matchings of two other families of graphs called Aztec rectangles and Aztec triangles. 相似文献
6.
K.L. Patra 《Linear algebra and its applications》2008,428(4):855-864
Let G=(V,E) be a tree on n?2 vertices and let v∈V. Let L(G) be the Laplacian matrix of G and μ(G) be its algebraic connectivity. Let Gk,l, be the graph obtained from G by attaching two new paths P:vv1v2…vk and Q:vu1u2…ul of length k and l, respectively, at v. We prove that if l?k?1 then μ(Gk-1,l+1)?μ(Gk,l). Let (v1,v2) be an edge of G. Let be the tree obtained from G by deleting the edge (v1,v2) and identifying the vertices v1 and v2. Then we prove that As a corollary to the above results, we obtain the celebrated theorem on algebraic connectivity which states that among all trees on n vertices, the path has the smallest and the star has the largest algebraic connectivity. 相似文献
7.
Let G be a regular bipartite graph and . We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph , that is a graph G with exactly the edges from X being negative, is not equivalent to . In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge. Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. As an application of our results we show that each signed regular bipartite graph that contains an unbalanced circuit has a 2‐cycle‐cover such that each cycle contains an odd number of negative edges. 相似文献
8.
Let G be a graph on n vertices with vertex connectivity v with 1 ≤ v ≤ n -2. We produce an attainable upper bound on the absolute algebraic connectivity of G in terms of n and v . 相似文献
9.
Let G be a graph on n vertices with vertex connectivity v with 1 h v h n m 2. We produce an attainable upper bound on the absolute algebraic connectivity of G in terms of n and v . 相似文献
10.
Let T(n,i) be the set of all trees with order n and matching number i.We determine the third to sixth trees in T(2i + 1,i) and the third to fifth trees in T(n,i) for n ≥ 2i + 2 with the largest Laplacian spectral radius. 相似文献
11.
六角系统是2-连通的平面图,其每个内部面都是单位正六边形.六角系统的完美匹配是化学中苯类芳烃体系的Kekule结构.一个六角系统H完美匹配Z—变换图Z(H)是一个图,它的顶点集是H的完匹配集,两个匹配相邻当且仅当它们的对称差是一个单位正六边形.本文用乘积图刻划了沙位六角系统Z—变换图的结构. 相似文献
12.
13.
We investigate how the algebraic connectivity of a weighted tree behaves when the tree is perturbed by removing one of its branches and replacing it with another. This leads to a number of results, for example the facts that replacing a branch in an unweighted tree by a star on the same number of vertices will not decrease the algebraic connectivity, while replacing a certain branch by a path on the same number of vertices will not increase the algebraic connectivity. We also discuss how the arrangement of the weights on the edges of a tree affects the algebraic connectivity, and we produce a lower bound on the algebraic connectivity of any unweighted graph in terms of the diameter and the number of vertices. Throughout, our techniques exploit a connection between the algebraic connectivity of a weighted tree and certain positive matrices associated with the tree. 相似文献
14.
15.
In Aldred and Plummer (Discrete Math 197/198 (1999) 29–40) proved that every m‐connected ‐free graph of even order has a perfect matching M with and , where F1 and F2 are prescribed disjoint sets of independent edges with and . It is known that if l satisfies , then the star‐free condition in the above result is best possible. In this paper, for , we prove a refinement of the result in which the condition is replaced by the weaker condition that G is ‐free (note that the new condition does not depend on l). We also show that if m is even and either or , then for m‐connected graphs G with sufficiently large order, one can replace the condition by the still weaker condition that G is ‐free. The star‐free conditions in our results are best possible. 相似文献
16.
连通图G的Balaban指标(也称J指标)定义为J=J(G)=(|E(G)|)/μ+1∑_(uυ∈E(G)),其中σ_G(u)=∑(w∈V(G)d_G(u,w)此处μ是基圈数.Balaban指标常用于各种QSAR和QSPR的研究.本文根据Balaban指标的计算公式及文中提到的变换方式,我们得到了一些序关系.基于这些序关系,我们确定了n个顶点的树中具有最小Balaban指标的前21个树. 相似文献
17.
Stephen G. Hartke Derrick Stolee Douglas B. West Matthew Yancey 《Journal of Graph Theory》2013,73(4):449-468
Let denote the maximum number of edges in a graph having n vertices and exactly p perfect matchings. For fixed p, Dudek and Schmitt showed that for some constant when n is at least some constant . For , they also determined and . For fixed p, we show that the extremal graphs for all n are determined by those with vertices. As a corollary, a computer search determines and for . We also present lower bounds on proving that for (as conjectured by Dudek and Schmitt), and we conjecture an upper bound on . Our structural results are based on Lovász's Cathedral Theorem. 相似文献
18.
Let and denote the second largest eigenvalue and the maximum number of edge‐disjoint spanning trees of a graph G, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and bounds of , Cioab? and Wong conjectured that for any integers and a d‐regular graph G, if , then . They proved the conjecture for , and presented evidence for the cases when . Thus the conjecture remains open for . We propose a more general conjecture that for a graph G with minimum degree , if , then . In this article, we prove that for a graph G with minimum degree δ, each of the following holds.
- (i) For , if and , then .
- (ii) For , if and , then .
19.
20.
Hong Lin Xiao-feng Guo 《应用数学学报(英文版)》2007,23(1):155-160
Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!]. 相似文献