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: The motivation for this paper is threefold. First, we study the connectivity properties of the homomorphism order of directed graphs, and more generally for relational structures. As opposed to the homomorphism order of undirected graphs (which has no non-trivial finite maximal antichains), the order of directed graphs has finite maximal antichains of any size. In this paper, we characterise explicitly all maximal antichains in the homomorphism order of directed graphs. Quite surprisingly, these maximal antichains correspond to generalised dualities. The notion of generalised duality is defined here in full generality as an extension of the notion of finitary duality, investigated in [J. Nešetřil, C. Tardif, Duality theorems for finite structures (characterising gaps and good characterisations), J. Combin. Theory Ser. B 80 (1) (2000) 80–97]. Building upon the results of the cited paper, we fully characterise the generalised dualities. It appears that these dualities are determined by forbidding homomorphisms from a finite set of forests (rather than trees). Finally, in the spirit of [A. Atserias, On digraph coloring problems and treewidth duality, in: Proceedings of the 21st IEEE Symposium on Logic in Computer Science, LICS’06, IEEE Computer Society, 2006; B. Larose, C. Loten, C. Tardif, A characterisation of first-order constraint satisfaction problems, in: Proceedings of the 21st IEEE Symposium on Logic in Computer Science, LICS’06, IEEE Computer Society, 2006; V. Dalmau, A. Krokhin, B. Larose, First-order definable retraction problems for posets and reflexive graphs, in: Proceedings of the 19th IEEE Symposium on Logic in Computer Science, LICS’04, IEEE Computer Society, 2004 ] we shall characterise “generalised” constraint satisfaction problems (defined also here) that are first-order definable. These are again just generalised dualities corresponding to finite maximal antichains in the homomorphism order. [Copyright &y& Elsevier]

Abstract: The authors showed in an earlier paper that there is a tree that displays, up to a natural equivalence, all non-trivial 3-separations of a 3-connected matroid. The purpose of this paper is to show that if certain natural conditions are imposed on the tree, then it has a uniqueness property. In particular, suppose that, from every pair of edges that meet at a degree-2 vertex and have their other ends of degree at least three, one edge is contracted. Then the resulting tree is unique. [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 3-connected matroid is said to be minimally 3-connected if, for any element of , the matroid is not 3-connected. Dawes [R.W. Dawes, Minimally 3-connected graphs, J. Combin. Theory Ser. B 40 (1986) 159–168] showed that all minimally 3-connected graphs can be constructed from such that every graph in each intermediate step is also minimally 3-connected. Oxley [J.G. Oxley, On connectivity in matroids and graphs, Trans. Amer. Math. Soc. 265 (1981) 47–58] proved a similar result by giving a characterization of minimally 2-connected matroids. In this paper we generalize Dawes’ result to minimally 3-connected binary matroids. We give a constructive characterization of all minimally 3-connected binary matroids starting from , the 3-spoked wheel, and , the Fano dual. [Copyright &y& Elsevier]

Abstract: We construct a universal presentation for the fundamental group of a closed-connected orientable 3-manifold. This result may be of considerable interest not only for topologists but also for experts in combinatorial group theory. Some applications on periodic manifolds and geometric presentations complete the paper. [Copyright &y& Elsevier]

Abstract: In this paper, the -Pfaff-Saalschütz formula and the -Sheppard transformation formula are established combinatorially. [Copyright &y& Elsevier]

Abstract: In a graph , a vertex is said to dominate itself and all vertices adjacent to it. For a positive integer , the -tuple domination number of is the minimum size of a subset of such that every vertex in is dominated by at least vertices in . To generalize/improve known upper bounds for the -tuple domination number, this paper establishes that for any positive integer and any graph of vertices and minimum degree , where with the degree of the th vertex of . [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of length and a complete graph of order . In this paper we show that for and , with the former result confirming a conjecture due to Erdös, Faudree, Rousseau and Schelp that for and in the case where . [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: This paper extends the widely used activation strategy of the marking game on graphs to asymmetric marking games. The extended activation strategy is then applied to asymmetric marking games on chordal graphs, -pseudo partial -trees and interval graphs. Our results improve earlier upper bounds on and , where and denote the classes of interval and chordal graphs with maximum clique size respectively. Moreover, the upper bound of is tight when is a multiple of . [Copyright &y& Elsevier]

Abstract: A hypergraph is -arc transitive if its automorphism group acts transitively on the set of its -arcs. In this paper, we study -arc transitive hypergraphs. We show that if a hypergraph has degree at least three and all edges of sizes at least three, then . Besides, given an -arc transitive hypergraph, we prove that there are infinitely many -arc transitive hypergraphs that cover the given one. These results extend to hypergraph classical results by Tutte, Weiss and Biggs for graphs. [Copyright &y& Elsevier]

Abstract: For graphs and , a mapping is a homomorphism of to if implies . If, moreover, each vertex is associated with costs , then the cost of the homomorphism is . For each fixed graph , we have the minimum cost homomorphism problem, written as . The problem is to decide, for an input graph with costs , whether there exists a homomorphism of to and, if one exists, to find one of minimum cost. Minimum cost homomorphism problems encompass (or are related to) many well-studied optimization problems. We prove a dichotomy of the minimum cost homomorphism problems for graphs , with loops allowed. When each connected component of is either a reflexive proper interval graph or an irreflexive proper interval bigraph, the problem is polynomial time solvable. In all other cases the problem is NP-hard. This solves an open problem from an earlier paper. [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: It is known that the area of all Catalan paths of length is equal to , which coincides with the number of inversions of all 321-avoiding permutations of length . In this paper, a bijection between the two sets is established. Meanwhile, a number of interesting bijective results that pave the way to the required bijection are presented. [Copyright &y& Elsevier]

Abstract: In this paper, we show that the stabilizer subgroup of for a without multiple roots can be derived from the stabilizer of . As an application, we construct a family of 3-designs such as , where is a prime power such that and . [Copyright &y& Elsevier]

Abstract: In a paper by Klazar, several counting examples for rooted plane trees were given, including matchings and maximal matchings. Apart from asymptotical analysis, it was shown how to obtain exact formulas for some of the countings by means of the Lagrange inversion formula. In this note, the results of Klazar are extended to formulas for matchings, maximal matchings and maximum matchings for three types of simply generated trees. Finally, edge coverings are considered and the results are compared. [Copyright &y& Elsevier]

Abstract: A graph is called circular super-critical if for every vertex of . In this paper, analogous to a result of Dirac on chromatic critical graphs, a sharp lower bound on the vertex degree of circular super-critical graphs is proved. This lower bound provides a partial answer to a question of X. Zhu [The circular chromatic number of induced subgraphs, J. Combin. Theory Ser. B 92 (2004) 177–181]. Some other structural properties of circular super-critical graphs are also presented. [Copyright &y& Elsevier]

Abstract: In this paper we extend the notion of Gauss decomposition to a bimatroid. This is used to give an equivalent definition of a bimatroid. We show that representability of a bimatroid can be defined easily in terms of Gauss decomposition. [Copyright &y& Elsevier]

Abstract: A graph is chordal if and only if it is the intersection graph of some family of subtrees of a tree. Applying “tolerance” allows larger families of graphs to be represented by subtrees. A graph is in the family if there is a tree with maximum degree and subtrees corresponding to the vertices of such that each subtree has maximum degree at most and two vertices of are adjacent if and only if the subtrees corresponding to them have at least common vertices. It is known that both and are equal to the family of chordal graphs. Furthermore, one can easily observe that every graph belongs to for some . Denote by the minimum so that . In this paper, we study and parameters and In particular, our results imply that and . [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]

Abstract: Let be a set of positive integers. The distance graph with distance set is the graph with vertex set in which two vertices are adjacent if and only if . The fractional chromatic number, the chromatic number, and the circular chromatic number of for various have been extensively studied recently. In this paper, we investigate the fractional chromatic number, the chromatic number, and the circular chromatic number of the distance graphs with the distance sets of the form , where , , and are natural numbers with . In particular, we completely determine the chromatic number of for arbitrary , and . [Copyright &y& Elsevier]

Let N be a minor of a 3-connected matroid M such that no proper 3-connected minor of M has N as a minor. This paper proves a bound on |E(M)−E(N)| that is sharp when N is connected. [Copyright &y& Elsevier]