Search

A graph is equimatchable if all of its maximal matchings have the same size. A graph is claw-free if it does not have a claw as an induced subgraph. In this paper, we provide the first characterization of claw-free equimatchable graphs by identifying the equimatchable claw-free graph families. This characterization implies an efficient recognition algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we design an algorithm that, given a directed graph G and the Cartesian-product decomposition of its underlying undirected graph G ̃ , produces the directed Cartesian-product decomposition of G in linear time. This is the first time that the linear complexity is achieved for this problem, which has two major consequences. Firstly, it shows that the directed and undirected versions of the Cartesian-product decomposition of graphs are linear-time equivalent problems. And secondly, as there already exists a linear-time algorithm for solving the undirected version of the problem, combined together, it provides the first linear-time algorithm for computing the directed Cartesian-product decomposition of a directed graph. [ABSTRACT FROM AUTHOR]

Abstract: Dual maps have been introduced as a generalization to higher dimensions of word substitutions and free group morphisms. In this paper, we study the action of these dual maps on particular discrete planes and surfaces, namely stepped planes and stepped surfaces. We show that dual maps can be seen as discretizations of toral automorphisms. We then provide a connection between stepped planes and the Brun multi-dimensional continued fraction algorithm, based on a desubstitution process defined on local geometric configurations of stepped planes. By extending this connection to stepped surfaces, we obtain an effective characterization of stepped planes (more exactly, stepped quasi-planes) among stepped surfaces. [Copyright &y& Elsevier]

Abstract: An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of , denoted , is the minimum number of colors required for acyclic vertex coloring of graph . For a family of graphs, the acyclic chromatic number of , denoted by , is defined as the maximum over all the graphs . In this paper we show that where is the family of graphs of maximum degree 5 and give a linear time algorithm to achieve this bound. [ABSTRACT FROM AUTHOR]

Abstract: A word is a fixed point of a nontrivial morphism if and is not the identity on the alphabet of . The paper presents the first polynomial algorithm deciding whether a given finite word is such a fixed point. The algorithm also constructs the corresponding morphism, which has the smallest possible number of non-erased letters. [Copyright &y& Elsevier]

Abstract: The strong chromatic index of a graph is the minimum integer such that the edge set of can be partitioned into induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205–211] proposed an open problem: If is bipartite and if for each edge , , then . Let be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if (not necessarily bipartite) is not isomorphic to and for any edge of then . The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs. [Copyright &y& Elsevier]

Abstract: The goal of this paper is to give a comparatively short and simple analysis of the Adyan origional group constraction (S.I. Adyan, Unsolvability of some algorithmic problems in the theory of groups, Trudy MMO 6 (1957) 231–298). [Copyright &y& Elsevier]

Abstract: The concept of table algebra in the title is a real nonsingular generalized table algebra in the sense of [Z. Arad, E. Fisman, M. Muzychuk, Generalized table algebras, Israel J. Math. 114 (1999) 29–60]. In this paper we first give some definitions and facts about table algebras. It is well known that every association scheme gives a Hecke-algebra which is a table algebra too. This leads to the natural question which properties of association schemes stay valid for table algebras. For instance, we prove the Second Isomorphism Theorem and the Jordan–Holder''s theorem for standard table algebras. [Copyright &y& Elsevier]

Abstract: Constructibility is a combinatorial property of simplicial complexes. In general, it requires a great deal of time to decide whether a simplicial complex is constructible or not. In this paper, we consider sufficient conditions for nonconstructibility of simplicial 3-balls to investigate efficient algorithms for the decision problem. [Copyright &y& Elsevier]

Abstract: The 2-factor index of a graph G, denoted by is the smallest integer m such that the m-iterated line graph of G contains a 2-factor. In this paper, we provide a formula for , and point out that there is a polynomial time algorithm to determine . [Copyright &y& Elsevier]

Splitting off a pair of edges su, sv in a graph G means replacing these two edges by a new edge uv. This operation is well known in graph theory. Let G=(V+s,E+F) be a graph which is k-edge-connected in V and suppose that |F| is even. Here F denotes the set of edges incident with s. Lova´sz (Combinatorial Problems and Exercises, North-Holland, Amsterdam, 1979) proved that if k⩾2 then the edges in F can be split off in pairs preserving the k-edge-connectivity in V. This result was recently extended to the case where a bipartition R∪Q=V is given and every split edge must connect R and Q (SIAM J. Discrete Math. 12 (2) (1999) 160). In this paper, we investigate an even more general problem, where two disjoint subsets R,Q⊂V are given and the goal is to split off (the largest possible subset of) the edges of F preserving k-edge-connectivity in V in such a way that every split edge incident with a vertex from R has the other end-vertex in Q. Motivated by connectivity augmentation problems, we introduce another extension, the so-called split completion version of our problem. Here, the smallest set F* of edges incident to s has to be found for which all the edges of F+F* can be split off in the augmented graph G=(V+s, E+F+F*) preserving k-edge-connectivity and in such a way that every split edge incident with a vertex from R has the other end-vertex in Q. We solve each of the above extensions when k is even: we give min–max formulae and polynomial algorithms to find the optima. For the case when k is odd we show how to find a solution to the split completion problem using at most two edges more than the optimum. [Copyright &y& Elsevier]

Abstract: Given a finite set of nonnegative integers with no three-term arithmetic progressions, the Stanley sequence generated by , denoted as , is the infinite set created by beginning with and then greedily including strictly larger integers which do not introduce a three-term arithmetic progression in . Erdős et al. asked whether the counting function, , of a Stanley sequence satisfies for every and . In this paper we answer this question in the affirmative; in fact, we prove the slightly stronger result that for . [Copyright &y& Elsevier]