共查询到20条相似文献,搜索用时 15 毫秒
1.
A graph G on n vertices is a tight distance graph if there exists a set such that and if and only if . A characterization of the degree sequences of tight distance graphs is given. This characterization yields a fast method for recognizing and realizing degree sequences of tight distance graphs. 相似文献
2.
Let M=(mij) be a nonnegative irreducible n×n matrix with diagonal entries 0. The largest eigenvalue of M is called the spectral radius of the matrix M , denoted by ρ(M). In this paper, we give two sharp upper bounds of the spectral radius of matrix M. As corollaries, we give two sharp upper bounds of the distance matrix of a graph. 相似文献
3.
Christina J. Edholm Leslie Hogben My Huynh Joshua LaGrange Darren D. Row 《Linear algebra and its applications》2012,436(12):4352-4372
The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for ) is nonzero whenever is an edge in G and is zero otherwise; maximum nullity is taken over the same set of matrices. The zero forcing number is the minimum size of a zero forcing set of vertices and bounds the maximum nullity from above. The spread of a graph parameter at a vertex v or edge e of G is the difference between the value of the parameter on G and on or . Rank spread (at a vertex) was introduced in [4]. This paper introduces vertex spread of the zero forcing number and edge spreads for minimum rank/maximum nullity and zero forcing number. Properties of the spreads are established and used to determine values of the minimum rank/maximum nullity and zero forcing number for various types of grids with a vertex or edge deleted. 相似文献
4.
A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most 1, and its size is the number of edges which go across the two parts. In this paper, motivated by several questions and conjectures of Bollobás and Scott, we study maximum bisections of graphs. First, we extend the classical Edwards bound on maximum cuts to bisections. A simple corollary of our result implies that every graph on n vertices and m edges with no isolated vertices, and maximum degree at most n/3+1, admits a bisection of size at least m/2+n/6. Then using the tools that we developed to extend Edwards?s bound, we prove a judicious bisection result which states that graphs with large minimum degree have a bisection in which both parts span relatively few edges. A special case of this general theorem answers a conjecture of Bollobás and Scott, and shows that every graph on n vertices and m edges of minimum degree at least 2 admits a bisection in which the number of edges in each part is at most (1/3+o(1))m. We also present several other results on bisections of graphs. 相似文献
5.
Denote by D(G)=(di,j)n×n the distance matrix of a connected graph G with n vertices, where dij is equal to the distance between vertices vi and vj in G . The least eigenvalue of D(G) is called the least distance eigenvalue of G , denoted by λn. In this paper, we determine all the graphs with λn∈[−2.383,0]. 相似文献
6.
7.
8.
9.
10.
Let F be an infinite field with characteristic not equal to two. For a graph G=(V,E) with V={1,…,n}, let S(G;F) be the set of all symmetric n×n matrices A=[ai,j] over F with ai,j≠0, i≠j if and only if ij∈E. We show that if G is the complement of a partial k -tree and m?k+2, then for all nonsingular symmetric m×m matrices K over F, there exists an m×n matrix U such that UTKU∈S(G;F). As a corollary we obtain that, if k+2?m?n and G is the complement of a partial k-tree, then for any two nonnegative integers p and q with p+q=m, there exists a matrix in S(G;R) with p positive and q negative eigenvalues. 相似文献
11.
We develop a variational theory to study the free boundary regularity problem for elliptic operators: Lu=Dj(aij(x)Diu)+biui+c(x)u=0 in {u>0}, 〈aij(x)∇u,∇u〉=2 on ∂{u>0}. We use a singular perturbation framework to approximate this free boundary problem by regularizing ones of the form: Luε=βε(uε), where βε is a suitable approximation of Dirac delta function δ0. A useful variational characterization to solutions of the above approximating problem is established and used to obtain important geometric properties that enable regularity of the free boundary. This theory has been developed in connection to a very recent line of research as an effort to study existence and regularity theory for free boundary problems with gradient dependence upon the penalization. 相似文献
12.
The distance spectral radius ρ(G) of a graph G is the largest eigenvalue of the distance matrix D(G). In this paper, we characterize the graph with minimum distance spectral radius among trees with fixed number of pendent vertices. 相似文献
13.
The classic Cayley identity states that where X=(xij) is an n×n matrix of indeterminates and ∂=(∂/∂xij) is the corresponding matrix of partial derivatives. In this paper we present straightforward algebraic/combinatorial proofs of a variety of Cayley-type identities, both old and new. The most powerful of these proofs employ Grassmann algebra (= exterior algebra) and Grassmann–Berezin integration. Among the new identities proven here are a pair of “diagonal-parametrized” Cayley identities, a pair of “Laplacian-parametrized” Cayley identities, and the “product-parametrized” and “border-parametrized” rectangular Cayley identities. 相似文献
det(∂)(detX)s=s(s+1)?(s+n−1)(detX)s−1
14.
15.
Let M be a 3-connected binary matroid and let n be an integer exceeding 2. Ding, Oporowski, Oxley, and Vertigan proved that there is an integer f(n) so that if |E(M)|>f(n), then M has a minor isomorphic to one of the rank-n wheel, the rank-n tipless binary spike, or the cycle or bond matroid of K3,n. This result was recently extended by Chun, Oxley, and Whittle to show that there is an integer g(n) so that if |E(M)|>g(n) and x∈E(M), then x is an element of a minor of M isomorphic to one of the rank-n wheel, the rank-n binary spike with a tip and a cotip, or the cycle or bond matroid of K1,1,1,n. In this paper, we prove that, for each i in {2,3}, there is an integer hi(n) so that if |E(M)|>hi(n) and Z is an i-element rank-2 subset of M, then M has a minor from the last list whose ground set contains Z. 相似文献
16.
17.
18.
Nash-Williams [1] proved that every graph with n vertices and minimum degree n/2 has at least ⌊5n/224⌋ edge-disjoint Hamiltonian cycles. In [2], he raised the question of determining the maximum number of edge-disjoint Hamiltonian cycles, showing an upper bound of ⌊(n+4)/8⌋. 相似文献
19.
Jason Ekstrand Craig Erickson H. Tracy Hall Diana Hay Leslie Hogben Ryan Johnson Nicole Kingsley Steven Osborne Travis Peters Jolie Roat Arianne Ross Darren D. Row Nathan Warnberg Michael Young 《Linear algebra and its applications》2013
The positive semidefinite zero forcing number Z+(G) of a graph G was introduced in Barioli et al. (2010) [4]. We establish a variety of properties of Z+(G): Any vertex of G can be in a minimum positive semidefinite zero forcing set (this is not true for standard zero forcing). The graph parameters tw(G) (tree-width), Z+(G), and Z(G) (standard zero forcing number) all satisfy the Graph Complement Conjecture (see Barioli et al. (2012) [3]). Graphs having extreme values of the positive semidefinite zero forcing number are characterized. The effect of various graph operations on positive semidefinite zero forcing number and connections with other graph parameters are studied. 相似文献
20.
We study vertex partitions of graphs according to their Colin de Verdiere parameter μ. By a result of Ding et al. [DOSOO] we know that any graph G with admits a vertex partition into two graphs with μ at most . Here we prove that any graph G with admits a vertex partition into three graphs with μ at most . This study is extended to other minor-monotone graph parameters like the Hadwiger number. 相似文献