Search

Each nontrivial shell (i.e., subconstituent) of the Johnson association scheme J (v , k) is known to be a commutative association scheme which is the product of two smaller Johnson association schemes. The concept of t -designs in one shell of J (v , k) was naturally defined and studied by Martin in the context of mixed t -designs. The purpose of this paper is to try to push this study a bit further. First we give a direct proof of the theorem that if (Y , w) is a relative t -design in J (v , k) on p shells then the part in each shell must be a weighted (t − p + 1) -design in the shell. In particular, it is a mixed (t − p + 1) -design in one shell if the weight function is constant on each shell. We also present another approach that makes use of the Terwilliger algebra, based on the work of Tanaka. This result is essentially proved by Martin in 1998, but the proof there contains a small gap which is repaired in this paper. We also study the existence problems of tight 2-, 3- and 4-designs on one shell of Johnson association scheme J (v , k) with small parameters, say v ≤ 1000 , thereby expanding the range of search in the original paper of Martin in 1998. [ABSTRACT FROM AUTHOR]

In Di Nasso (2015) and Luperi Baglini (2012) it has been introduced a technique, based on nonstandard analysis, to study some problems in combinatorial number theory. In this paper we review such a technique and we present three of its applications: the first one is a new proof of a known result regarding the algebra of β N , namely that the center of the semigroup ( β N , ⊕ ) is N ; the second one is a generalization of a theorem of Bergelson and Hindman on arithmetic progressions of length three; the third one regards the study of which polynomials in several variables with integers coefficients have a monochromatic solution for every finite coloring of N . We will study this last application in more detail: we will prove some algebraical properties of the set P of such polynomials and we will present a few examples of nonlinear polynomials in P . In the first part of the paper we will recall the main results of the nonstandard technique that we want to use, which is based on a characterization of ultrafilters by means of nonstandard analysis. [ABSTRACT FROM AUTHOR]

The main goal of the paper is to make connections between two well-known, but, up to now, independently developed theories: the theory of violator spaces and the theory of closure spaces. Violator spaces were introduced by Matoušek et al. in 2008 as generalization of linear programming problems. The notion of closure arises in many disciplines, including topology, algebra, convexity analysis, logic etc. In this work, we investigate interrelations between violator spaces and closure spaces. We show that a violator mapping may be defined by a weak version of a closure operator. Interrelations between violator spaces and closure spaces give new insights on a number of well known findings. For example, we prove that violator spaces with a unique basis satisfy both the anti-exchange and the Krein–Milman properties. Finally, based on subsequent relaxations of the closure operator notion we introduce convex spaces as a generalization of violator spaces. [ABSTRACT FROM AUTHOR]

Let T = T (x 0) be the Terwilliger algebra of the Johnson scheme J (N , D) , where x 0 is a fixed base point. In Liang et al. (2017), an observation is made on the parameters of Leonard systems that arise from the irreducible representations of T. This paper accounts for the observation from the viewpoint of group representations. In particular, it is shown that T is isomorphic to the centralizer algebra for the stabilizer of the base point x 0 in the automorphism group of J (N , D). [ABSTRACT FROM AUTHOR]

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: This paper is devoted to the conjecture saying that, for any connected locally finite graph and any vertex-transitive group of automorphisms of , at least one of the following assertions holds: (1) There exists an imprimitivity system of on with finite (maybe one-element) blocks such that the stabilizer of a vertex of the factor graph in the induced group of automorphisms is finite. (2) The graph is hyperbolic (i.e., for some positive integer , the graph defined by and contains the regular tree of valency 3). Our approach to the conjecture consists in fixing a finite permutation group and considering the conjecture under the assumption that the stabilizer of a vertex of in induces on the neighborhood of the vertex a group permutation isomorphic to . In the paper we elaborate a method (the modified track method) which allows us to prove the conjecture for many groups . The paper consists of two parts. The present first part of the paper involves results on which the modified track method arguments are based, and a few first applications of the method. The second part is devoted to applications of the modified track method. [Copyright &y& Elsevier]

Almost any reasonable class of finite relational structures has the Ramsey property or a precompact Ramsey expansion. In contrast to that, the list of classes of finite algebras with the precompact Ramsey expansion is surprisingly short. In this paper we show that any nontrivial variety (that is, equationally defined class of algebras) enjoys various dual Ramsey properties. We develop a completely new set of strategies that rely on the fact that left adjoints preserve the dual Ramsey property, and then treat classes of algebras as Eilenberg–Moore categories for a monad. We show that finite algebras in any nontrivial variety have finite dual small Ramsey degrees, and that every finite algebra has finite dual big Ramsey degree in the free algebra on countably many free generators. As usual, these come as consequences of ordered versions of the statements. [ABSTRACT FROM AUTHOR]

We say that a pair ( A , B ) is a recovering pair if A and B are set systems on an n -element ground set, such that for every A , A ′ ∈ A and B , B ′ ∈ B we have ( A ∖ B = A ′ ∖ B ′ implies A = A ′ ) and symmetrically ( B ∖ A = B ′ ∖ A ′ implies B = B ′ ). G. Simonyi conjectured that if ( A , B ) is a recovering pair, then | A | | B | ≤ 2 n . For the quantity | A | | B | the best known upper bound is 2 . 326 4 n due to Holzman and Körner. In this paper we improve this upper bound to 2 . 281 4 n . [ABSTRACT FROM AUTHOR]

In this paper Seidel matrices are studied, and their spectrum and several related algebraic properties are determined for order n ≤ 13 . Based on this Seidel matrices with exactly three distinct eigenvalues of order n ≤ 23 are classified. One consequence of the computational results is that the maximum number of equiangular lines in R 12 with common angle 1 ∕ 5 is exactly 20 . [ABSTRACT FROM AUTHOR]

This work is a follow-up of the article (Noy et al., 2019), where the authors solved the problem of counting labelled 4-regular planar graphs. In this paper, we obtain a precise asymptotic estimate for the number g n of labelled 4-regular planar graphs on n vertices. Our estimate is of the form g n ∼ g ⋅ n − 7 / 2 ρ − n n ! , where g > 0 is a constant and ρ ≈ 0. 24377 is the radius of convergence of the generating function ∑ n ≥ 0 g n x n / n ! , and conforms to the universal pattern obtained previously in the enumeration of several classes of planar graphs. In addition to analytic methods, our solution needs intensive use of computer algebra in order to deal with large systems of multivariate polynomial equations. We also obtain asymptotic estimates for the number of 2- and 3-connected 4-regular planar graphs, and for the number of 4-regular simple maps, both connected and 2-connected. [ABSTRACT FROM AUTHOR]

Abstract: Regular and distance-regular characterizations of general graphs are well-known. In particular, the spectral excess theorem states that a connected graph is distance-regular if and only if its spectral excess (a number that can be computed from the spectrum) equals the average excess (the mean of the numbers of vertices at extremal distance from every vertex). The aim of this paper is to derive new characterizations of regularity and distance-regularity for the more restricted family of bipartite graphs. In this case, some characterizations of (bi)regular bipartite graphs are given in terms of the mean degrees in every partite set and the Hoffman polynomial. Moreover, it is shown that the conditions for having distance-regularity in such graphs can be relaxed when compared with general graphs. Finally, a new version of the spectral excess theorem for bipartite graphs is presented. [Copyright &y& Elsevier]

Let 1 2 H (n , 2) denote the halved n -cube with vertex set X and let T ≔ T (x 0) denote the Terwilliger algebra of 1 2 H (n , 2) with respect to a fixed vertex x 0 ∈ X. In this paper, we assume n ≥ 6. We first characterize T by considering the action of the automorphism group of 1 2 H (n , 2) on the set X × X × X. We show that T coincides with the centralizer algebra of the stabilizer of x 0 in the automorphism group, and display three subalgebras of T further. Then we study the homogeneous components of V ≔ ℂ X , each of which is a nonzero subspace of V spanned by the irreducible T -modules that are isomorphic. We give a computable basis for any homogeneous component of V. Finally, we describe the decomposition of T via its block-diagonalization and give a basis for the center of T by using the above homogeneous components of V. [ABSTRACT FROM AUTHOR]

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: In this paper we study monomial ideals attached to posets, introduce generalized Hibi rings and investigate their algebraic and homological properties. The main tools to study these objects are Gröbner basis theory, the concept of sortability due to Sturmfels and the theory of weakly polymatroidal ideals. [Copyright &y& Elsevier]

Abstract: In this paper, we prove the existence of acute triangulations for general polyhedral surfaces. We also show how to obtain nonobtuse subtriangulations of triangulated polyhedral surfaces. [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 wedge product of Schur rings was introduced by K.H. Leung and S.H. Man in order to classify Schur rings over a cyclic group. The wedge product presented by Leung and Man was defined in an internal form. The external version of wedge product of Schur rings was described by Evdokimov and Ponomarenko under the name “generalized wreath product”. The goal of this paper is to generalize this operation to arbitrary association schemes. [Copyright &y& Elsevier]

Abstract: In this paper, we will prove a result which is formally dual to the long-standing conjecture of Bannai and Ito which claims that there are only finitely many distance-regular graphs of valency for each . That is, we prove that, for any fixed , there are only finitely many cometric association schemes with the property that the first idempotent in a -polynomial ordering has rank . As a key preliminary result, we show that the splitting field of any such association scheme is at most a degree two extension of the rationals. All of the tools involved in the proof are fairly elementary yet have wide applicability. To indicate this, a more general theorem is proved here with the result alluded to in the title appearing as a corollary to this theorem. [Copyright &y& Elsevier]

Abstract: In [H. Suzuki, Imprimitive -polynomial association schemes, J. Algebraic Combin. 7 (2) (1998) 165–180], it was shown that an imprimitive -polynomial scheme is either dual bipartite, dual antipodal or of class 4 or 6. In this paper, it will be shown that the scheme of class 4 does not occur using the integrality conditions of the entries of the first eigenmatrix of . These integrality conditions arise from the fact that has exactly one -polynomial ordering [H. Suzuki, Association schemes with multiple -polynomial structures, J. Algebraic Combin. 7 (2) (1998) 181–196]. [Copyright &y& Elsevier]

Abstract: In this paper we will determine the spectra of the local graphs of the twisted Grassmann graphs and look at its consequences for the associated Terwilliger algebras. In particular, we show that the Terwilliger algebra for the twisted Grassmann graphs does depend on the base point. More specifically, we show that for the twisted Grassmann graphs there are two vertices and such that for the Terwilliger algebra with base point all the irreducible modules are thin and for the Terwilliger algebra with base point there exist non-thin irreducible modules. [Copyright &y& Elsevier]

Let Γ denote a finite, simple, connected and bipartite graph. Fix a vertex x of Γ and let T = T (x) denote the Terwilliger algebra of Γ with respect to x. Assume that x is a distance-regularized vertex, which is not a leaf. We consider the property that Γ has, up to isomorphism, a unique irreducible T -module with endpoint 1, and that this T -module is thin. The main result of the paper is a combinatorial characterization of this property. [ABSTRACT FROM AUTHOR]

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: Let be a simple graph satisfying the Ore-condition with . In this paper, we prove that is -connected for any abelian group with if and only if is not one of the 12 completely described graphs. [Copyright &y& Elsevier]

Abstract: This paper is devoted to computing the number of isomorphism classes of pointed hyperelliptic curves over finite fields. We deal with the genus-4 case and the finite fields are of odd characteristic. The number of isomorphism classes is computed. This number can be represented as a polynomial in of degree 7, where is the order of the finite field. The results have applications in the classification problems and in the hyperelliptic curve cryptosystems. [Copyright &y& Elsevier]

Abstract: In this paper, we compute the congruences of Catalan and Motzkin numbers modulo 4 and 8. In particular, we prove the conjecture proposed by Deutsch and Sagan that no Motzkin number is a multiple of 8. [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: 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 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 -Pfaff-Saalschütz formula and the -Sheppard transformation formula are established combinatorially. [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: 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: 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: 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: 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: 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: 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: 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: A graph is half-arc-transitive if its automorphism group acts transitively on vertices and edges, but not on arcs. It is known that for a prime there is no tetravalent half-arc-transitive graphs of order or . Xu [M.Y. Xu, Half-transitive graphs of prime-cube order, J. Algebraic Combin. 1 (1992) 275–282] classified the tetravalent half-arc-transitive graphs of order . As a continuation, we classify in this paper the tetravalent half-arc-transitive graphs of order . It shows that there are exactly nonisomorphic connected tetravalent half-arc-transitive graphs of order for each odd prime . [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: 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: 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 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: 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: 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: 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: 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]