共查询到20条相似文献,搜索用时 15 毫秒
1.
Iwao Sato 《Linear algebra and its applications》2011,435(5):943-952
Recently, Levine [9] expressed the vertex weighted complexity on spanning trees (with a fixed root) of the directed line graph of a digraph D in terms of the edge weighted complexity on spanning trees (with a fixed root) of D. We present new proofs for two Levine’s Theorems. Furthermore, we express the number of unicycles of the directed line graph of a digraph D in terms of the number of unicycles of D. 相似文献
2.
Motivated by a Mohar’s paper proposing “how to order trees by the Laplacian coefficients”, we investigate a partial ordering of trees with diameters 3 and 4 by the Laplacian coefficients. These results are used to determine several orderings of trees by the Laplacian coefficients. 相似文献
3.
In this paper we analyse the vibrations of an N-stepped Rayleigh bar with sections of complex geometry, supported by end lumped masses and springs. Equations of motion and boundary conditions are derived from the Hamilton’s variational principal. The solutions for tapered and exponential sections are given. Two types of orthogonality for the eigenfunctions are obtained. The analytic solution to the N-stepped Rayleigh model is constructed in terms of Green function. 相似文献
4.
Knesers conjecture, first proved by Lovász in 1978,
states that the graph with all k-element subsets of {1, 2, . . . ,
n} as vertices and with edges
connecting disjoint sets has chromatic number
n–2k+2. We derive this result from
Tuckers combinatorial lemma on labeling the vertices of special
triangulations of the octahedral ball. By specializing a proof
of Tuckers lemma, we obtain self-contained purely combinatorial
proof of Knesers conjecture.* Research supported by Charles University grants
No. 158/99 and 159/99 and by ETH Zürich. 相似文献
5.
Ivo Klemeš 《Linear algebra and its applications》2007,422(1):164-185
We study determinant inequalities for certain Toeplitz-like matrices over C. For fixed n and N ? 1, let Q be the n × (n + N − 1) zero-one Toeplitz matrix with Qij = 1 for 0 ? j − i ? N − 1 and Qij = 0 otherwise. We prove that det(QQ∗) is the minimum of det(RR∗) over all complex matrices R with the same dimensions as Q satisfying ∣Rij∣ ? 1 whenever Qij = 1 and Rij = 0 otherwise. Although R has a Toeplitz-like band structure, it is not required to be actually Toeplitz. Our proof involves Alexandrov’s inequality for polarized determinants and its generalizations. This problem is motivated by Littlewood’s conjecture on the minimum 1-norm of N-term exponential sums on the unit circle. We also discuss polarized Bazin-Reiss-Picquet identities, some connections with k-tree enumeration, and analogous conjectured inequalities for the elementary symmetric functions of QQ∗. 相似文献
6.
Further computations are made on the traditional coupon collectors problem
when the collector shares his harvest with his younger brothers. When the book of the
p-th brother of the collector is completed, the books of
the younger brothers have certain
numbers of empty spots. On the average, how many? Several answers can be brought to
that question.To Gian-Carlo Rota, in memoriam 相似文献
7.
Brualdi brought to Geršgorin Theory the concept that the digraph G(A) of a matrix A is important in studying whether A is singular. He proved, for example, that if, for every directed cycle of G(A), the product of the diagonal entries exceeds the product of the row sums of the moduli of the off-diagonal entries, then the matrix is nonsingular. We will show how, in polynomial time, that condition can be tested and (if satisfied) produce a diagonal matrix D, with positive diagonal entries, such that AD (where A is any nonnnegative matrix satisfying the conditions) is strictly diagonally dominant (and so, A is nonsingular). The same D works for all matrices satisfying the conditions. Varga raised the question of whether Brualdi’s conditions are sharp. Improving Varga’s results, we show, if G is scwaltcy (strongly connected with at least two cycles), and if the Brualdi conditions do not hold, how to construct (again in polynomial time) a complex matrix whose moduli satisfy the given specifications, but is singular. 相似文献
8.
In 1970s, Gutman introduced the concept of the energy E(G) for a simple graph G, which is defined as the sum of the absolute values of the eigenvalues of G. This graph invariant has attracted much attention, and many lower and upper bounds have been established for some classes of graphs among which bipartite graphs are of particular interest. But there are only a few graphs attaining the equalities of those bounds. We however obtain an exact estimate of the energy for almost all graphs by Wigner’s semi-circle law, which generalizes a result of Nikiforov. We further investigate the energy of random multipartite graphs by considering a generalization of Wigner matrix, and obtain some estimates of the energy for random multipartite graphs. 相似文献
9.
Ahmet I. Seven 《Linear algebra and its applications》2010,433(6):1154-1169
Quivers of finite mutation type are certain directed graphs that first arised in Fomin-Zelevinsky’s theory of cluster algebras. It has been observed that these quivers are also closely related with different areas of mathematics. In fact, main examples of finite mutation type quivers are the quivers associated with triangulations of surfaces. In this paper, we study structural properties of finite mutation type quivers in relation with the corresponding skew-symmetric matrices. We obtain a characterization of finite mutation type quivers that are associated with triangulations of surfaces and give a new numerical invariant for their mutation classes. 相似文献
10.
In this paper, we derive some necessary spectral conditions for the existence of graph homomorphisms in which we also consider some parameters related to the corresponding eigenspaces such as nodal domains. In this approach, we consider the combinatorial Laplacian and co-Laplacian as well as the adjacency matrix. Also, we present some applications in graph decompositions where we prove a general version of Fisher’s inequality for G-designs. 相似文献
11.
Let L be an n×n matrix with zero row and column sums, n?3. We obtain a formula for any minor of the (n−2)-th compound of L. An application to counting spanning trees extending a given forest is given. 相似文献
12.
S. Akbari 《Linear algebra and its applications》2007,421(1):3-15
We study graphs whose adjacency matrices have determinant equal to 1 or −1, and characterize certain subclasses of these graphs. Graphs whose adjacency matrices are totally unimodular are also characterized. For bipartite graphs having a unique perfect matching, we provide a formula for the inverse of the corresponding adjacency matrix, and address the problem of when that inverse is diagonally similar to a nonnegative matrix. Special attention is paid to the case that such a graph is unicyclic. 相似文献
13.
B.D. Miller 《Annals of Pure and Applied Logic》2011,162(7):561
We give classical proofs, strengthenings, and generalizations of Lecomte’s characterizations of analytic ω-dimensional hypergraphs with countable Borel chromatic number. 相似文献
14.
The new methods for constructing matching-equivalence graphs 总被引:1,自引:0,他引:1
Haicheng Ma 《Discrete Mathematics》2007,307(1):125-131
Two graphs G and H with order n are said to be matching-equivalent if and only if the number of r-matchings (i.e., the number of ways in which r disjoint edges can be chosen) is the same for each of the graphs G and H for each r, where 0?r?n. In this paper, the new methods for constructing ‘matching-equivalent’ graphs are given, and some families of non-matching unique graphs are also obtained. 相似文献
15.
We prove three theorems. First, Lovászs theorem about
minimal imperfect clutters, including also Padbergs
corollaries. Second, Lehmans result on minimal nonideal
clutters. Third, a common generalization of these two. The
endeavor of working out a common denominator for Lovászs and
Lehmans theorems leads, besides the common generalization, to a
better understanding and simple polyhedral proofs of
both.* Visiting of the French Ministry of Research and
Technology, laboratoire LEIBNIZ, Grenoble, November 1995—April
1996. 相似文献
16.
Wayne Barrett H. Tracy Hall Raphael Loewy 《Linear algebra and its applications》2009,431(8):1147-2203
Let G be an undirected graph on n vertices and let S(G) be the set of all real symmetric n×n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The inverse inertia problem for G asks which inertias can be attained by a matrix in S(G). We give a complete answer to this question for trees in terms of a new family of graph parameters, the maximal disconnection numbers of a graph. We also give a formula for the inertia set of a graph with a cut vertex in terms of inertia sets of proper subgraphs. Finally, we give an example of a graph that is not inertia-balanced, which settles an open problem from the October 2006 AIM Workshop on Spectra of Families of Matrices described by Graphs, Digraphs and Sign Patterns. We also determine some restrictions on the inertia set of any graph. 相似文献
17.
Wenhua Zhao 《Journal of Pure and Applied Algebra》2004,186(3):311-327
Let A be a commutative k-algebra over a field of k and Ξ a linear operator defined on A. We define a family of A-valued invariants Ψ for finite rooted forests by a recurrent algorithm using the operator Ξ and show that the invariant Ψ distinguishes rooted forests if (and only if) it distinguishes rooted trees T, and if (and only if) it is finer than the quantity α(T)=|Aut(T)| of rooted trees T. We also consider the generating function with , where is the set of rooted trees with n vertices. We show that the generating function U(q) satisfies the equation . Consequently, we get a recurrent formula for Un (n?1), namely, U1=Ξ(1) and Un=ΞSn−1(U1,U2,…,Un−1) for any n?2, where are the elementary Schur polynomials. We also show that the (strict) order polynomials and two well-known quasi-symmetric function invariants of rooted forests are in the family of invariants Ψ and derive some consequences about these well-known invariants from our general results on Ψ. Finally, we generalize the invariant Ψ to labeled planar forests and discuss its certain relations with the Hopf algebra in Foissy (Bull. Sci. Math. 126 (2002) 193) spanned by labeled planar forests. 相似文献
18.
Norman L. Johnson 《Journal of Geometry》2006,85(1-2):61-71
Every semifield plane with spread in PG(3,K), where K is a field admitting a quadratic extension K+, is shown to admit a transitive parabolic unital.
The author gratefully acknowledges helpful comments of the referee in the writing of this article. 相似文献
19.
Hye Kyung Kim 《Discrete Mathematics》2008,308(4):555-564
For an abelian group Γ, a formula to compute the characteristic polynomial of a Γ-graph has been obtained by Lee and Kim [Characteristic polynomials of graphs having a semi-free action, Linear algebra Appl. 307 (2005) 35-46]. As a continuation of this work, we give a computational formula for generalized characteristic polynomial of a Γ-graph when Γ is a finite group. Moreover, after showing that the reciprocal of the Bartholdi zeta function of a graph can be derived from the generalized characteristic polynomial of a graph, we compute the reciprocals of the Bartholdi zeta functions of wheels and complete bipartite graphs as an application of our formula. 相似文献
20.
Thomas Quint 《Linear algebra and its applications》2007,422(1):236-249
We propose a new way to rate individual duplicate bridge players, which we believe is superior to the masterpoint system currently used by the American Contract Bridge League. This method measures only a player’s current skill level, and not how long or how frequently he has played. It is based on simple ideas from the theory of statistics and from linear algebra, and should be easy to implement.One particular issue which can occur within any system proposing to rate individual players using results earned by partnerships is what we call the “nonuniqueness problem”. This refers to the occasional inability for data to distinguish who is the “good player” and who is the “bad player” within particular partnerships. We prove that under our system this problem disappears if either (a) a certain “partnership graph” has no bipartite components, or if (b) every player is required to participate in at least one individual game.Finally, we present some data from a bridge club in Reno, NV. They show that even if (a) and (b) do not hold, our system will provide (unique) ratings for most players. 相似文献