Search

In our previous paper, we presented the combinatorial theory for minimal isostatic pinned frameworks–Assur graphs–which arise in the analysis of mechanical linkages. In this paper we further explore the geometric properties of Assur graphs, with a focus on singular realizations which have static self-stresses. We provide a new geometric characterization of Assur graphs, based on special singular realizations. These singular positions are then related to dead-end positions in which an associated mechanism with an inserted driver will stop or jam. [Copyright &y& Elsevier]

Abstract: A graph is called tri-Cayley if it admits a semiregular subgroup of automorphisms having three orbits of equal length. In this paper, the structure of strongly regular tri-Cayley graphs is investigated. A structural description of strongly regular tri-Cayley graphs of cyclic groups is given. [Copyright &y& Elsevier]

Abstract: A Cayley map is a 2-cell embedding of a Cayley graph into an orientable surface such that all vertex-rotations correspond to the cyclic permutation of the generating set . It is called regular if its automorphism group acts regularly on the dart set. A regular Cayley map is called -balanced if for every . In this paper, we classify the regular -balanced Cayley maps on dicyclic groups for all . As a result, all such maps are 1-balanced. [Copyright &y& Elsevier]

Abstract: In this paper we prove the knight move theorem for the chromatic graph cohomologies with rational coefficients introduced by L. Helme-Guizon and Y. Rong. Namely, for a connected graph with vertices the only non-trivial cohomology groups come in isomorphic pairs: for if is non-bipartite, and for if is bipartite. As a corollary, the ranks of the cohomology groups are determined by the chromatic polynomial. At the end, we give an explicit formula for the Poincaré polynomial in terms of the chromatic polynomial and a deletion–contraction formula for the Poincaré polynomial. [Copyright &y& Elsevier]

Abstract: Catlin and Jaeger proved that the cycle matroid of a 4-edge-connected graph has a spanning cycle. This result can not be generalized to regular matroids as there exist infinitely many connected cographic matroids, each of which contains a minor and has arbitrarily large cogirth, that do not have spanning cycles. In this paper, we proved that if a connected regular matroid without a -minor has cogirth at least 4, then it has a spanning cycle. [Copyright &y& Elsevier]

Abstract: It was conjectured by Reed [B. Reed, , and , Journal of Graph Theory 27 (1998) 177–212] that for any graph , the graph’s chromatic number is bounded above by , where and are the maximum degree and clique number of , respectively. In this paper we prove that this bound holds if is the line graph of a multigraph. The proof yields a polynomial time algorithm that takes a line graph and produces a colouring that achieves our bound. [Copyright &y& Elsevier]

Abstract: In this paper, we apply some new algebraic no-homomorphism theorems in conjunction with some new chromatic parameters to estimate the circular chromatic number of graphs. To show the applicability of the general results, as a couple of examples, we generalize a well known inequality for the fractional chromatic number of graphs and we also show that the circular chromatic number of the graph obtained from the Petersen graph by excluding one vertex is equal to 3. Also, we focus on the Johnson–Holroyd–Stahl conjecture about the circular chromatic number of Kneser graphs and we propose an approach to this conjecture. In this regard, we introduce a new related conjecture on Kneser graphs and we also provide some supporting evidence. [Copyright &y& Elsevier]

Abstract: An element of a 3-connected matroid is said to be contractible provided that is 3-connected. In this paper, we show that a 3-connected matroid with exactly contractible elements has at least triangles. For each , we construct an infinite family of matroids that attain this bound. New sharp bounds for the number of triads of a minimally 3-connected matroid are obtained as a consequence of our main result. [Copyright &y& Elsevier]