共查询到20条相似文献,搜索用时 15 毫秒
1.
《Quaestiones Mathematicae》2013,36(4):533-549
AbstractThe bipartiteness of a graph is the minimum number of vertices whose deletion from G results in a bipartite graph. If a graph invariant decreases or increases with addition of edges of its complement, then it is called a monotonic graph invariant. In this article, we determine the extremal values of some famous monotonic graph invariants, and characterize the corresponding extremal graphs in the class of all connected graphs with a given vertex bipartiteness. 相似文献
2.
Pavel Chebotarev 《Discrete Applied Mathematics》2008,156(5):813-821
For a graph G, let fij be the number of spanning rooted forests in which vertex j belongs to a tree rooted at i. In this paper, we show that for a path, the fij's can be expressed as the products of Fibonacci numbers; for a cycle, they are products of Fibonacci and Lucas numbers. The doubly stochastic graph matrix is the matrix F=(fij)n×n/f, where f is the total number of spanning rooted forests of G and n is the number of vertices in G. F provides a proximity measure for graph vertices. By the matrix forest theorem, F-1=I+L, where L is the Laplacian matrix of G. We show that for the paths and the so-called T-caterpillars, some diagonal entries of F (which provide a measure of the self-connectivity of vertices) converge to φ-1 or to 1-φ-1, where φ is the golden ratio, as the number of vertices goes to infinity. Thereby, in the asymptotic, the corresponding vertices can be metaphorically considered as “golden introverts” and “golden extroverts,” respectively. This metaphor is reinforced by a Markov chain interpretation of the doubly stochastic graph matrix, according to which F equals the overall transition matrix of a random walk with a random number of steps on G. 相似文献
3.
In this paper, boundary cubic rooted planar maps are investigated and exact enumerative formulae are given. First, an enumerative formula for boundary cubic inner-forest maps with the size (number of edges) as a parameter is derived. For the special case of boundary cubic inner-tree maps, a simple formula with two parameters is presented. Further, according to the duality, a corresponding result for outer-planar maps is obtained. Finally, some results for boundary cubic planar maps and general planar maps are obtained. Furthermore, two known Tutte's formulae are easily deduced in the paper. 相似文献
4.
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. 相似文献
5.
Peter J. Olver 《Differential Geometry and its Applications》2009,27(2):230-239
The algebra of differential invariants of a suitably generic surface S⊂R3, under either the usual Euclidean or equi-affine group actions, is shown to be generated, through invariant differentiation, by a single differential invariant. For Euclidean surfaces, the generating invariant is the mean curvature, and, as a consequence, the Gauss curvature can be expressed as an explicit rational function of the invariant derivatives, with respect to the Frenet frame, of the mean curvature. For equi-affine surfaces, the generating invariant is the third order Pick invariant. The proofs are based on the new, equivariant approach to the method of moving frames. 相似文献
6.
Over an algebraically closed base field k of characteristic 2, the ring RG of invariants is studied, G being the orthogonal group O(n) or the special orthogonal group SO(n) and acting naturally on the coordinate ring R of the m-fold direct sum kn⊕?⊕kn of the standard vector representation. It is proved for O(n) (n?2) and for SO(n) (n?3) that there exist m-linear invariants with m arbitrarily large that are indecomposable (i.e., not expressible as polynomials in invariants of lower degree). In fact, they are explicitly constructed for all possible values of m. Indecomposability of corresponding invariants over immediately follows. The constructions rely on analysing the Pfaffian of the skew-symmetric matrix whose entries above the diagonal are the scalar products of the vector variables. 相似文献
7.
Oscar Rojo 《Linear algebra and its applications》2006,414(1):218-243
Let T be an unweighted tree with vertex root v which is the union of two trees T1=(V1,E1), T2=(V2,E2) such that V1 ∩ V2 = {v} and T1 and T2 have the property that the vertices in each of their levels have equal degree. We characterize completely the eigenvalues of the adjacency matrix and of the Laplacian matrix of T. They are the eigenvalues of symmetric tridiagonal matrices whose entries are given in terms of the vertex degrees. Moreover, we give some results about the multiplicity of the eigenvalues. Applications to some particular trees are developed. 相似文献
8.
S. Amat 《Journal of Computational and Applied Mathematics》2010,234(4):1277-1290
Multiresolution representations of data are powerful tools in data compression. For a proper adaptation to the edges, a good strategy is to consider a nonlinear approach. Thus, one needs to control the stability of these representations. In this paper, 2D multiresolution processing algorithms that ensure this stability are introduced. A prescribed accuracy is ensured by these strategies. 相似文献
9.
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. 相似文献
10.
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. 相似文献
11.
The level of a vertex in a rooted graph is one more than its distance from the root vertex. A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree. We characterize completely the eigenvalues of the Laplacian, signless Laplacian and adjacency matrices of a weighted rooted graph G obtained from a weighted generalized Bethe tree of k levels and weighted cliques in which
- (1)
- the edges connecting vertices at consecutive levels have the same weight,
- (2)
- each set of children, in one or more levels, defines a weighted clique, and
- (3)
- cliques at the same level are isomorphic.
12.
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. 相似文献
13.
Bojan Mohar 《Linear algebra and its applications》2010,432(9):2273-2467
Wilf’s eigenvalue upper bound on the chromatic number is extended to the setting of digraphs. The proof uses a generalization of Brooks’ Theorem to digraph colorings. 相似文献
14.
Dongseok Kim 《Linear algebra and its applications》2008,429(4):688-697
In this paper, we find computational formulae for generalized characteristic polynomials of graph bundles. We show that the number of spanning trees in a graph is the partial derivative (at (0,1)) of the generalized characteristic polynomial of the graph. Since the reciprocal of the Bartholdi zeta function of a graph can be derived from the generalized characteristic polynomial of a graph, consequently, the Bartholdi zeta function of a graph bundle can be computed by using our computational formulae. 相似文献
15.
We consider the (Ihara) zeta functions of line graphs, middle graphs and total graphs of a regular graph and their (regular or irregular) covering graphs. Let L(G), M(G) and T(G) denote the line, middle and total graph of G, respectively. We show that the line, middle and total graph of a (regular and irregular, respectively) covering of a graph G is a (regular and irregular, respectively) covering of L(G), M(G) and T(G), respectively. For a regular graph G, we express the zeta functions of the line, middle and total graph of any (regular or irregular) covering of G in terms of the characteristic polynomial of the covering. Also, the complexities of the line, middle and total graph of any (regular or irregular) covering of G are computed. Furthermore, we discuss the L-functions of the line, middle and total graph of a regular graph G. 相似文献
16.
Gerard J. Chang Liang-Hao Huang Hong-Gwa Yeh 《Linear algebra and its applications》2011,434(8):1793-1798
The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: What is the structure of a connected graph with rank 4? This question has not yet been fully answered in the literature, and only some partial results are known. In this paper we resolve this question by completely characterizing graphs G whose adjacency matrix has rank 4. 相似文献
17.
Dongseok Kim 《Linear algebra and its applications》2010,433(2):348-355
The complexity of a graph can be obtained as a derivative of a variation of the zeta function [S. Northshield, A note on the zeta function of a graph, J. Combin. Theory Ser. B 74 (1998) 408-410] or a partial derivative of its generalized characteristic polynomial evaluated at a point [D. Kim, H.K. Kim, J. Lee, Generalized characteristic polynomials of graph bundles, Linear Algebra Appl. 429 (4) (2008) 688-697]. A similar result for the weighted complexity of weighted graphs was found using a determinant function [H. Mizuno, I. Sato, On the weighted complexity of a regular covering of a graph, J. Combin. Theory Ser. B 89 (2003) 17-26]. In this paper, we consider the determinant function of two variables and discover a condition that the weighted complexity of a weighted graph is a partial derivative of the determinant function evaluated at a point. Consequently, we simply obtain the previous results and disclose a new formula for the complexity from a variation of the Bartholdi zeta function. We also consider a new weighted complexity, for which the weights of spanning trees are taken as the sum of weights of edges in the tree, and find a similar formula for this new weighted complexity. As an application, we compute the weighted complexities of the product of the complete graphs. 相似文献
18.
Ashkan Nikeghbali 《Probability Theory and Related Fields》2006,136(4):524-540
Azéma associated with an honest time L the supermartingale
and established some of its important properties. This supermartingale plays a central role in the general theory of stochastic
processes and in particular in the theory of progressive enlargements of filtrations. In this paper, we shall give an additive
characterization for these supermartingales, which in turn will naturally provide many examples of enlargements of filtrations.
We combine this characterization with some arguments from both initial and progressive enlargements of filtrations to establish
some path decomposition results, closely related to or reminiscent of Williams' path decomposition results. In particular,
some of the fragments of the paths in our decompositions end or start with a new family of random times which are not stopping
times, nor honest times. 相似文献
19.
RenHan LiuYanpei 《高校应用数学学报(英文版)》1999,14(1):117-121
A Halin map is a kind of planar maps oriented by a tree. In this paper the rooted halin maps with the vertex partition as parameters are enumerated such that a famous result on rooted trees due to Harary. Prins, and Tutte is deduced as. a special ease. Further, by using Lagrangian inversion to obtain a number of summation free formulae dixectly, the various kinds of rooted Halin maps with up to three parameters have been counted. 相似文献
20.
We introduce a new graph polynomial in two variables. This interlace polynomial can be computed in two very different ways. The first is an expansion analogous to the state space expansion of the Tutte polynomial; the significant differences are that our expansion is over vertex rather than edge subsets, and the rank and nullity employed are those of an adjacency matrix rather than an incidence matrix.The second computation is by a three-term reduction formula involving a graph pivot; the pivot arose previously in the study of interlacement and Euler circuits in four-regular graphs.We consider a few properties and specializations of the two-variable interlace polynomial. One specialization, the vertex-nullity interlace polynomial, is the single-variable interlace graph polynomial we studied previously, closely related to the Tutte–Martin polynomial on isotropic systems previously considered by Bouchet. Another, the vertex-rank interlace polynomial, is equally interesting. Yet another specialization of the two-variable polynomial is the independent-set polynomial. Supported by NSF grant DMS-9971788. 相似文献