共查询到20条相似文献，搜索用时 31 毫秒
1.
《Journal of Graph Theory》2018,88(4):577-591
Given a zero‐sum function with , an orientation D of G with in for every vertex is called a β‐orientation. A graph G is ‐connected if G admits a β‐orientation for every zero‐sum function β. Jaeger et al. conjectured that every 5‐edge‐connected graph is ‐connected. A graph is ‐extendable at vertex v if any preorientation at v can be extended to a β‐orientation of G for any zero‐sum function β. We observe that if every 5‐edge‐connected essentially 6‐edge‐connected graph is ‐extendable at any degree five vertex, then the above‐mentioned conjecture by Jaeger et al. holds as well. Furthermore, applying the partial flow extension method of Thomassen and of Lovász et al., we prove that every graph with at least four edge‐disjoint spanning trees is ‐connected. Consequently, every 5‐edge‐connected essentially 23‐edge‐connected graph is ‐extendable at any degree five vertex. 相似文献
2.
1. IntroductionLet G be a simple graph with vertex set V = {yi, v2,'', v.} and edge set E ~ E(G).Denote the degree of vertex yi by di. Let D(G) ~ diag (dl, d2,'', da) and A(G) be thediagonal mains of vertex degrees and the adjacency matrix of G, respectively. Then L(G) D(G)-A(G) is the Laplacian matrix of G. It seems that L(G) first occurred in the celebratedMatriX-Thee Theorem:Theorem 1.1. If Li j is the submatrix of L(G) obtained by deleting its i-th row andj-th column, then (-… 相似文献
3.
In this paper, we give the upper bound and lower bound ofk-th largest eigenvalue λk of the Laplacian matrix of a graphG in terms of the edge number ofG and the number of spanning trees ofG.
This research is supported by the National Natural Science Foundation of China (Grant No.19971086) and the Doctoral Program
Foundation of State Education Department of China. 相似文献
4.
设T是一个树,V是T的顶点集．记dv是υ∈V的度,△是T的最大顶点度．设υ∈V且dw=1．记k=ew+1,这里ew是w的excentricity．设δj′= max{dυ:dist(υ,w)=j},j=1,2,…,k-2,我们证明和这里μ1(T)和λ1(T)分别是T的Laplacian矩阵和邻接矩阵的最大特征值．特别地,记δo′=2． 相似文献
5.
6.
Two graphs are said to be A-cospectral if they have the same adjacency spectrum. A graph G is said to be determined by its adjacency spectrum if there is no other non-isomorphic graph A-cospectral with G. A tree is called starlike if it has exactly one vertex of degree greater than 2. In this article, we prove that the line graphs of starlike trees with maximum degree at least 12 are determined by their adjacency spectra. 相似文献
7.
8.
9.
Ji‐Ming Guo 《Journal of Graph Theory》2007,54(1):51-57
Let λk(G) be the kth Laplacian eigenvalue of a graph G. It is shown that a tree T with n vertices has and that equality holds if and only if k < n, k|n and T is spanned by k vertex disjoint copies of , the star on vertices. © 2006 Wiley Periodicals, Inc. J Graph Theory 相似文献
10.
图G的无符号拉普拉斯矩阵定义为图G的邻接矩阵与度对角矩阵的和,其特征值称为图G的Q-特征值.图G的一个Q-特征值称为Q-主特征值,如果它有一个特征向量其分量的和不等于零.确定了所有恰有两个Q-主特征值的三圈图. 相似文献
11.
Shilin Wang 《Linear and Multilinear Algebra》2013,61(2):197-204
We give complete information about the signless Laplacian spectrum of the corona of a graph G 1 and a regular graph G 2, and complete information about the signless Laplacian spectrum of the edge corona of a connected regular graph G 1 and a regular graph G 2. 相似文献
12.
Trees are very common in the theory and applications of combinatorics. In this article, we consider graphs whose underlying structure is a tree, except that its vertices are graphs in their own right and where adjacent graphs (vertices) are linked by taking their join. We study the spectral properties of the Laplacian matrices of such graphs. It turns out that in order to capture known spectral properties of the Laplacian matrices of trees, it is necessary to consider the Laplacians of vertex-weighted graphs. We focus on the second smallest eigenvalue of such Laplacians and on the properties of their corresponding eigenvector. We characterize the second smallest eigenvalue in terms of the Perron branches of a tree. Finally, we show that our results are applicable to advancing the solution to the problem of whether there exists a graph on n vertices whose Laplacian has the integer eigenvalues 0, 1, …, n ? 1. 相似文献
13.
Kinkar Ch. Das 《Graphs and Combinatorics》2007,23(6):625-632
Let G = (V,E) be a simple graph with n vertices, e edges and d1 be the highest degree. Further let λi, i = 1,2,...,n be the non-increasing eigenvalues of the Laplacian matrix of the graph G. In this paper, we obtain the following result: For connected graph G, λ2 = λ3 = ... = λn-1 if and only if G is a complete graph or a star graph or a (d1,d1) complete bipartite graph.
Also we establish the following upper bound for the number of spanning trees of G on n, e and d1 only:
The equality holds if and only if G is a star graph or a complete graph. Earlier bounds by Grimmett [5], Grone and Merris [6], Nosal [11], and Kelmans [2] were
sharp for complete graphs only. Also our bound depends on n, e and d1 only.
This work was done while the author was doing postdoctoral research in LRI, Université Paris-XI, Orsay, France. 相似文献
14.
The signless Laplacian matrix of a graph is the sum of its diagonal matrix of vertex degrees and its adjacency matrix. Li and Feng gave some basic results on the largest eigenvalue and characteristic polynomial of adjacency matrix of a graph in 1979. In this paper, we translate these results into the signless Laplacian matrix of a graph and obtain the similar results. 相似文献
15.
Suppose that the vertex set of a graph G is
16.
In this paper, we characterize the trees with the largest Laplacian and adjacency spectral radii among all trees with fixed number of vertices and fixed maximal degree, respectively. 相似文献
17.
18.
We show that a k‐edge‐connected graph on n vertices has at least spanning trees. This bound is tight if k is even and the extremal graph is the n‐cycle with edge multiplicities . For k odd, however, there is a lower bound , where . Specifically, and . Not surprisingly, c3 is smaller than the corresponding number for 4‐edge‐connected graphs. Examples show that . However, we have no examples of 5‐edge‐connected graphs with fewer spanning trees than the n‐cycle with all edge multiplicities (except one) equal to 3, which is almost 6‐regular. We have no examples of 5‐regular 5‐edge‐connected graphs with fewer than spanning trees, which is more than the corresponding number for 6‐regular 6‐edge‐connected graphs. The analogous surprising phenomenon occurs for each higher odd edge connectivity and regularity. 相似文献
19.
20.