共查询到20条相似文献,搜索用时 31 毫秒
1.
Norman Biggs 《Journal of Algebraic Combinatorics》1999,10(2):115-133
The 'dollar game' represents a kind of diffusion process on a graph. Under the rules of the game some cofigurations are both stable and recurrent, and these are known as critical cofigurations. The set of critical configurations can be given the structure of an abelian group, and it turns out that the order of the group is the tree-number of the graph. Each critical configuration can be assigned a positive weight, and the generating function that enumerates critical configurations according to weight is a partial evaluation of the Tutte polynomial of the graph. It is shown that the weight enumerator can also be interpreted as a growth function, which leads to the conclusion that the (partial) Tutte polynomial itself is a growth function. 相似文献
2.
Molly Maxwell 《Journal of Combinatorial Theory, Series A》2009,116(2):351-378
We define involutively self-dual matroids and prove that an enumerator for their bases is the square of a related enumerator for their self-dual bases. This leads to a new proof of Tutte's theorem that the number of spanning trees of a central reflex is a perfect square, and it solves a problem posed by Kalai about higher dimensional spanning trees in simplicial complexes. We also give a weighted version of the latter result.We give an algebraic analogue relating to the critical group of a graph, a finite abelian group whose order is the number of spanning trees of the graph. We prove that the critical group of a central reflex is a direct sum of two copies of an abelian group, and conclude with an analogous result in Kalai's setting. 相似文献
3.
《Discrete Mathematics》2022,345(12):113107
Critical ideals of a graph G which are the determinantal ideals of its generalized Laplacian matrix were first introduced by Corrales and Valencia as a generalization of the critical group. Then it was shown that critical ideals are also closely related to other properties of the graph, such as the clique number and the zero forcing number. In this note, we give a simple proof of Theorem 4.13 proved in [7], which gives a Gröbner basis of the first nontrivial critical ideal of a cycle. After that as applications we determine explicit expressions for the characteristic ideals of a cycle and the critical groups of a family of thick wheels. 相似文献
4.
Lucas Sabalka 《Geometriae Dedicata》2007,124(1):191-198
We construct an embedding of any right-angled Artin group G(Δ) defined by a graph Δ into a graph braid group. The number of strands required for the braid group is equal to the chromatic
number of Δ. This construction yields an example of a hyperbolic surface subgroup embedded in a two strand planar graph braid
group.
相似文献
5.
Carlos A. Alfaro Carlos E. Valencia Adrián Vázquez-Ávila 《Linear and Multilinear Algebra》2018,66(10):2036-2048
Critical ideals generalize the critical group, Smith group and the characteristic polynomials of the adjacency and Laplacian matrices of a graph. We give a complete characterization of the digraphs with at most one trivial critical ideal. Which implies the characterizations of the digraphs whose critical group has one invariant factor equal to one, and the digraphs whose Smith group has one invariant factor equal to one. 相似文献
6.
一个κ-正则图若满足对任意正整数s,1≤s≤κ,均存在一个s-因子或一个2[s/2]因子,则称其有泛因子或偶泛因子性质.本文证明了每个奇度Cayley图是泛因子的,每个偶度Carley图是偶泛因子的.同时证明了二面体群上的每个Cayley图均是泛因子的. 相似文献
7.
设G是一个图 .设g和f是两个定义在V(G)上的整值函数使得对V(G)所有顶点x有g(x) ≤f(x) .图G被称为 (g ,f,n) 临界图 ,如果删去G的任意n个顶点后的子图都含有G的 (g ,f) 因子 .本文给出了图是 (a ,b ,n) 临界图几个充分条件 ,即度和邻域条件 .进一步指出这些条件是最佳的 . 相似文献
8.
A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle. 相似文献
9.
The authors introduce a notion of a weak graph map homotopy (they call it
M-homotopy), discuss its properties and applications. They prove that the weak graph
map homotopy equivalence between graphs coincides with the graph homotopy equivalence
defined by Yau et al in 2001. The difference between them is that the weak graph map
homotopy transformation is defined in terms of maps, while the graph homotopy transformation is defined by means of combinatorial operations. They discuss its advantages over
the graph homotopy transformation. As its applications, they investigate the mapping
class group of a graph and the 1-order MP-homotopy group of a pointed simple graph.
Moreover, they show that the 1-order MP-homotopy group of a pointed simple graph is
invariant up to the weak graph map homotopy equivalence. 相似文献
10.
For a positive integer n, does there exist a vertex-transitive graph Γ on n vertices which is not a Cayley graph, or, equivalently, a graph Γ on n vertices such that Aut Γ is transitive on vertices but none of its subgroups are regular on vertices? Previous work (by Alspach and Parsons, Frucht, Graver and Watkins, Marusic and Scapellato, and McKay and the second author) has produced answers to this question if n is prime, or divisible by the square of some prime, or if n is the product of two distinct primes. In this paper we consider the simplest unresolved case for even integers, namely for integers of the form n = 2pq, where 2 < q < p, and p and q are primes. We give a new construction of an infinite family of vertex-transitive graphs on 2pq vertices which are not Cayley graphs in the case where p ≡ 1 (mod q). Further, if p ? 1 (mod q), p ≡ q ≡ 3(mod 4), and if every vertex-transitive graph of order pq is a Cayley graph, then it is shown that, either 2pq = 66, or every vertex-transitive graph of order 2pq admitting a transitive imprimitive group of automorphisms is a Cayley graph. 相似文献
11.
Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group
Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper, we show that this conjecture is true for Cayley graph on generalized dihedral groups and generalized quaternion groups, which generalizes the result of F. Yang and X. Li [Inform. Process. Lett., 2011, 111: 416–419]. We also generalizes an early result of M. Nánásiová and M. ?koviera [J. Algebraic Combin., 2009, 30: 103–110]. 相似文献
12.
The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph, and which is closely related to the graph Laplacian. Its group structure has been determined for relatively few classes of graphs, e.g., complete graphs and complete bipartite graphs. For complete multipartite graphs , we describe the critical group structure completely. For Cartesian products of complete graphs , we generalize results of H. Bai on the k-dimensional cube, by bounding the number of invariant factors in the critical group, and describing completely its p-primary structure for all primes p that divide none of . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 231–250, 2003 相似文献
13.
The vertex-critical graph conjecture (critical graph conjecture respectively) states that every vertex-critical (critical) graph has an odd number of vertices. In this note we prove that if G is a critical graph of even order, then G has at least three vertices of less-than-maximum valency. In addition, if G is a 3-critical multigraph of smallest even order, then G is simple and has no triangles. 相似文献
14.
Andrew Berget Andrew Manion Molly Maxwell Aaron Potechin Victor Reiner 《Annals of Combinatorics》2012,16(3):449-488
The critical group of a graph is a finite abelian group whose order is the number of spanning forests of the graph. This paper provides three basic structural results on the critical group of a line graph.
- The first deals with connected graphs containing no cut-edge. Here the number of independent cycles in the graph, which is known to bound the number of generators for the critical group of the graph, is shown also to bound the number of generators for the critical group of its line graph.
- The second gives, for each prime p, a constraint on the p-primary structure of the critical group, based on the largest power of p dividing all sums of degrees of two adjacent vertices.
- The third deals with connected graphs whose line graph is regular. Here known results relating the number of spanning trees of the graph and of its line graph are sharpened to exact sequences which relate their critical groups.
15.
We investigate the set of those integers n for which directly indecomposable groups of order n exist. For even n such groups are easily constructed. In contrast, we show that the density of the set of odd numbers with this property is zero. For each n we define a graph whose connected components describe uniform direct decompositions of all groups of order n. We prove that for almost all odd numbers (i.e., with the exception of a set of density zero) this graph has a single ‘big’ connected component and all other vertices are isolated. We also give an asymptotic formula for the number of isolated vertices of the graph, i.e., for the number of prime divisors q of n such that every group of order n has a cyclic direct factor of order q. 相似文献
16.
首先对开关图的自同构群进行了研究,随即讨论了它的点传递性,并得到Calyley图的开关图依然是Cayley图. 相似文献
17.
The centers and cyclic radicals of generalized Baumslag–Solitar groups (GBS-groups) are studied. Criteria for their non-triviality are found and an algorithm to compute the center and cyclic radical is given. In addition, for each unimodular GBS-group, a GBS-cover, i.e., a GBS-group in whose underlying graph the weights around each vertex are constant in absolute value, is constructed. These groups are then characterized by a minimality property. 相似文献
18.
M.Kriesell证明了收缩临界5-连通图的平均度不超过24并猜想收缩临界5-连通图的平均度小于10.本文构造了一个反例证明M.Kriesell的猜想不成立并给出了收缩临界5-连通图平均度新的上界. 相似文献
19.
Dedicated to the memory of Paul Erdős
A facet of the stable set polytope of a graph G can be viewed as a generalization of the notion of an -critical graph. We extend several results from the theory of -critical graphs to facets. The defect of a nontrivial, full-dimensional facet of the stable set polytope of a graph G is defined by . We prove the upper bound for the degree of any node u in a critical facet-graph, and show that can occur only when . We also give a simple proof of the characterization of critical facet-graphs with defect 2 proved by Sewell [11]. As an
application of these techniques we sharpen a result of Surányi [13] by showing that if an -critical graph has defect and contains nodes of degree , then the graph is an odd subdivision of .
Received October 23, 1998 相似文献
20.
Vsevolod F. Lev 《Discrete Mathematics》2010,310(3):575-584
Given a finite abelian group G, consider the complete graph on the set of all elements of G. Find a Hamiltonian cycle in this graph and for each pair of consecutive vertices along the cycle compute their sum. What are the smallest and the largest possible number of distinct sums that can emerge in this way? What is the expected number of distinct sums if the cycle is chosen randomly? How do the answers change if an orientation is given to the cycle and differences (instead of sums) are computed? We give complete solutions to some of these problems and establish reasonably sharp estimates for the rest. 相似文献