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: Recently, Deutsch and Elizalde have studied the largest and the smallest fixed points of permutations. Motivated by their work, we consider the analogous problems in set partitions. Let denote the number of partitions of with the largest singleton for . In this paper, several explicit formulas for , involving a Dobinski-type analog, are obtained by algebraic and combinatorial methods. Furthermore, many combinatorial identities involving and Bell numbers are presented by operator methods, and congruence properties of are also investigated. It is shown that the sequences and (mod ) are periodic for any prime , and contain a string of consecutive zeroes. Moreover their minimum periods are conjectured to be . [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: In [B. De Bruyn, A. Pasini, Minimal scattered sets and polarized embeddings of dual polar spaces, European J. Combin. 28 (2007) 1890–1909], it was shown that every full polarized embedding of a dual polar space of rank has vector dimension at least . In the present paper, we will give alternative proofs of that result which hold for more general classes of dense near polygons. These alternative proofs allow us to characterize full polarized embeddings of minimal vector dimension . Using this characterization result, we can prove a decomposition theorem for the embedding space. We will use this decomposition theorem to get information on the structure of the spin-embedding of the dual polar space . [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: Sen’s theorem, which highlights the conflict between the Pareto condition and individual rights, is a fundamental result in the area of social choice. In this paper, we give an analog of Sen’s theorem for consensus functions on hierarchies by showing that in almost all cases it is not possible to find a ternary Pareto consensus function where two distinct algorithms will have the same decisive impact on the consensus output. [Copyright &y& Elsevier]

Abstract: The purpose of this paper is to introduce new parametric families of complex Hadamard matrices in two different ways. First, we prove that every real Hadamard matrix of order admits an affine orbit. This settles a recent open problem of Tadej and Życzkowski [W. Tadej, K. Życzkowski, A concise guide to complex Hadamard matrices, Open Syst. Inf. Dyn. 13 (2006) 133–177], who asked whether a real Hadamard matrix can be isolated among complex ones. In particular, we apply our construction to the only (up to equivalence) real Hadamard matrix of order 12 and show that the arising affine family is different from all previously known examples listed in [W. Tadej, K. Życzkowski, A concise guide to complex Hadamard matrices, Open Syst. Inf. Dyn. 13 (2006) 133–177]. Second, we recall a well-known construction related to real conference matrices, and show how to introduce an affine parameter in the arising complex Hadamard matrices. This leads to new parametric families of orders 10 and 14. An interesting feature of both of our constructions is that the arising families cannot be obtained via Diţă’s general method [P. Diţă, Some results on the parametrization of complex Hadamard matrices, J. Phys. A 37 (20) (2004) 5355–5374]. Our results extend the recent catalogue of complex Hadamard matrices [W. Tadej, K. Życzkowski, A concise guide to complex Hadamard matrices, Open Syst. Inf. Dyn. 13 (2006) 133–177], and may lead to direct applications in quantum-information theory. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce and study the notion of a partial -hypergroupoid, associated with a binary relation. Some important results concerning Rosenberg partial hypergroupoids, induced by relations, are generalized to the case of -hypergroupoids. Then, -hypergroups associated with union, intersection, products of relations and also mutually associative -hypergroupoids are analyzed. Finally, -hypergroupoids associated with relations are used in order to study the transitivity of the relation in -semihypergroups. [Copyright &y& Elsevier]

Abstract: In this paper, the endomorphism monoid of , the complement of a path with vertices, is explored explicitly. It is shown that is orthodox. Some enumerative problems concerning are solved. In particular, the endomorphism spectrum and the endomorphism type of are 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 enumerate the number of ways of selecting objects from objects arrayed in a line such that no two selected ones are separated by objects and provide three different formulas when and . Also, we prove that the number of ways of selecting objects from objects arrayed in a circle such that no two selected ones are separated by objects is given by , where and . [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: A language is called a relatively regular language if its syntactic monoid has finite ideals. In this paper, we show that there are close relationships between the relatively regular languages and some other classes of languages such as (generalized) disjunctive languages, fd-domains and 2-codes. In particular, we prove that every relatively regular 2-code is thin. Thus, the well known result of Bestel and Perrin in 1985 becomes an easy corollary of our result. [Copyright &y& Elsevier]

Abstract: In this paper, we consider a relation between the Hall–Janko graph and the Witt system . We will reconstruct the Hall–Janko graph from the group and the hexacode. [Copyright &y& Elsevier]

Abstract: In this paper, we characterize by lexicographic order all finite Sturmian and episturmian words, i.e., all (finite) factors of such infinite words. Consequently, we obtain a characterization of infinite episturmian words in a wide sense (episturmian and episkew infinite words). That is, we characterize the set of all infinite words whose factors are (finite) episturmian. Similarly, we characterize by lexicographic order all balanced infinite words over a 2-letter alphabet; in other words, all Sturmian and skew infinite words, the factors of which are (finite) Sturmian. [Copyright &y& Elsevier]

Abstract: A drawing of a graph in the plane is even if nonadjacent edges have an even number of intersections. Hanani’s theorem characterizes planar graphs as those graphs that have an even drawing. In this paper we present an algebraic characterization of graphs that have an even drawing. Together with Hanani’s theorem this yields an algebraic characterization of planar graphs. We will also present algebraic characterizations of subgraphs of paths, and of outerplanar graphs. [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: Consider a polar space weakly embedded in a projective space . A secant of is the intersection of the point set of with a line of spanned by two non-collinear points of . The geometry consisting of the points of and as lines the secants is a so-called Delta space. In this paper we give a characterization of this and some related geometries. [Copyright &y& Elsevier]

Abstract: In [B. De Bruyn, H. Pralle, The hyperplanes of , preprint 2005], we showed the existence of five isomorphism classes of hyperplanes in each dual polar space of type . We also proved there that every hyperplane of belongs to one of these five classes if . In the present paper, we classify all hyperplanes of and find four additional isomorphism classes of hyperplanes. [Copyright &y& Elsevier]

Abstract: In [B. De Bruyn, P. Vandecasteele, Near polygons with a nice chain of sub near polygons, J. Combin. Theory Ser. A 108 (2004) 297–311], we determined all dense near -gons of order with a nice chain of subpolygons, i.e. a chain of convex subpolygons satisfying (i) , , is a near -gon, and (ii) , , is big in . In the present paper, we describe a method which can be used for classifying general dense near polygons with such a chain. We will use this method to determine all dense near polygons with a nice chain of subpolygons if every hex is either classical or glued. We will apply the latter result to determine all dense near octagons of order with a nice chain of subpolygons. [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: We present various techniques to count proportions of permutations with restricted cycle structure in finite permutation groups. For example, we show how a generalized block theory for symmetric groups, developed by Külshammer, Olsson, and Robinson, can be used for such calculations. The paper includes improvements of recurrence relations of Glasby, results on average numbers of fixed points in certain permutations, and a remark on a conjecture of Robinson related to the so-called -problem of representation theory. We extend and give alternative proofs for previous results of Erdős and Turán; Glasby; and Beals, Leedham-Green, Niemeyer, Praeger and Seress. [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]