Search

Galois hulls are generalizations of Euclidean and Hermitian hulls, which have attracted interest because of their important applications in determining the complexity of some algorithms about linear codes and in constructing entanglement-assisted quantum error-correcting codes (EAQECCs). In this paper, the whole contribution is two-folded. On one hand, we propose explicit methods to construct linear codes of larger lengths with Galois hulls of arbitrary dimensions from given Galois self-orthogonal codes. Conditions required in our approach are proven to be relatively weak. On the other hand, we apply these results to construct EAQECCs. Two bounds for EAQECCs constructed from linear codes with prescribed dimensional Galois hull are given and EAQECCs with rates greater than or equal to 1 2 and positive net rates can be obtained. We also present many interesting examples to explain visually how these two aspects work. [ABSTRACT FROM AUTHOR]

Abstract: Let and be fixed positive integers. Assume that the vertices of a planar graph are partitioned into blocks (or empires) each containing exactly vertices. The -colouring problem (- COL r ) asks for a colouring of the vertices of the graph that uses at most colours, never assigns the same colour to adjacent vertices in different empires and, conversely, assigns the same colour to all vertices in the same empire, disregarding adjacencies. For the problem coincides with the classical vertex colouring problem on planar graphs. The generalization for was defined by Percy Heawood in 1890 in the same paper in which he refuted a previous “proof” of the famous Four Colour Theorem. In a recent paper we have shown that if , - COL r is NP-hard for linear forests if . Furthermore, the hardness extends to (resp. ) when (resp. for ) for arbitrary planar graphs. For trees, our argument entails a nice dichotomy: - COL r is NP-hard for and solvable in polynomial time for any other positive value of . In this paper we argue that linear forests do not make the problem any easier, even for small values of . We prove that the - COL r problem is NP-hard for linear forests even if and , or and . [Copyright &y& Elsevier]

Abstract Sometimes it is possible to embed an algebraic trapdoor into a block cipher. Building on previous research, in this paper we investigate an especially dangerous algebraic structure, which is called a hidden sum and which is related to some regular subgroups of the affine group. Mixing group theory arguments and cryptographic tools, we pass from characterizing our hidden sums to designing an efficient algorithm to perform the necessary preprocessing for the exploitation of the trapdoor. [ABSTRACT FROM AUTHOR]

Circular graphs are intersection graphs of arcs on a circle. These graphs are reported to have been studied since 1964, and they have been receiving considerable attention since a series of papers by Tucker in the 1970s. Various subclasses of circular-arc graphs have also been studied. Among these are the proper circular-arc graphs, unit circular-arc graphs, Helly circular-arc graphs and co-bipartite circular-arc graphs. Several characterizations and recognition algorithms have been formulated for circular-arc graphs and its subclasses. In particular, it should be mentioned that linear time algorithms are known for all these classes of graphs. In the present paper, we survey these characterizations and recognition algorithms, with emphasis on the linear time algorithms. [Copyright &y& Elsevier]

Abstract: Any given graph can be embedded in a chordal graph by adding edges, and the resulting chordal graph is called a triangulation of the input graph. In this paper we study minimal triangulations, which are the result of adding an inclusion minimal set of edges to produce a triangulation. This topic was first studied from the standpoint of sparse matrices and vertex elimination in graphs. Today we know that minimal triangulations are closely related to minimal separators of the input graph. Since the first papers presenting minimal triangulation algorithms appeared in 1976, several characterizations of minimal triangulations have been proved, and a variety of algorithms exist for computing minimal triangulations of both general and restricted graph classes. This survey presents and ties together these results in a unified modern notation, keeping an emphasis on the algorithms. [Copyright &y& Elsevier]

Abstract: We consider the problem of reconstructing a partition x of the integer n from the set of its t-subpartitions. These are the partitions of the integer obtained by deleting a total of t from the parts of x in all possible ways. It was shown (in a forthcoming paper) that all partitions of n can be reconstructed from t-subpartitions if n is sufficiently large in relation to t. In this paper we deal with efficient reconstruction, in the following sense: if all partitions of n are -reconstructible, what is the minimum number such that every partition of n can be identified from any distinct subpartitions? We determine the function and describe the corresponding algorithm for reconstruction. Superpartitions may be defined in a similar fashion and we determine also the maximum number of t-superpartitions common to two distinct partitions of n. [Copyright &y& Elsevier]

An Euler tour in a hypergraph is a closed walk that traverses each edge of the hypergraph exactly once, while an Euler family is a family of closed walks that jointly traverse each edge exactly once and cannot be concatenated. In this paper, we show how the problem of existence of an Euler tour (family) in a hypergraph H can be reduced to the analogous problem in some smaller hypergraphs that are derived from H using an edge cut of H. In the process, new techniques of edge cut assignments and collapsed hypergraphs are introduced. Moreover, we describe algorithms based on these characterizations that determine whether or not a hypergraph admits an Euler tour (family), and can also construct an Euler tour (family) if it exists. [ABSTRACT FROM AUTHOR]

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]

By a well-known theorem of Thomassen and a planar graph depicted by Voigt, we know that every planar graph is 5-choosable, and the bound is tight. In 1999, Lam, Xu and Liu reduced 5 to 4 on C 4 -free planar graphs. In the paper, by applying the famous Combinatorial Nullstellensatz, we design an effective algorithm to deal with list coloring problems. At the same time, we prove that a planar graph G is 4-choosable if any two 4-cycles having distance at least 5 in G , which extends the result of Lam et al. [ABSTRACT FROM AUTHOR]

It is well known that the circular flow number of a bridgeless cubic graph can be computed in terms of certain partitions of its vertex set with prescribed properties. In the present paper, we first study some of these properties that turn out to be useful in order to make an efficient and practical implementation of an algorithm for the computation of the circular flow number of a bridgeless cubic graph. Using this procedure, we determine the circular flow number of all snarks on up to 36 vertices as well as the circular flow number of various famous snarks. After that, as combination of the use of this algorithm with new theoretical results, we present an infinite family of snarks of order 8 k + 2 whose circular flow numbers meet a general lower bound presented by Lukot'ka and Škoviera in 2008. In particular this answers a question proposed in their paper. Moreover, we improve the best known upper bound for the circular flow number of Goldberg snarks and we conjecture that this new upper bound is optimal. [ABSTRACT FROM AUTHOR]

This paper generalizes the concept of SA -homotopy in finite topological adjacency category, which is introduced in our previous work, to graph category and discusses its properties. We prove that every SA -strong deformation retract of a simple graph G could be obtained by removing trivial vertices one by one, which makes it possible to allow an iterative algorithm of finding all SA -strong deformation retracts of G. We also obtain that two simple graphs are SA -homotopy equivalent if and only if they have graph isomorphic cores. Compared with the graph homotopy transformation defined by S.T. Yau et al. and the s -homotopy transformation defined by R. Boulet et al., the main advantage of SA -homotopy transformation is that it could reflect correspondences between vertices, and hence it more accurately describe the transformation process than the graph homotopy transformation and s -homotopy transformation. As an application of SA -homotopy on graphs, we introduce the mapping class group of a graph, which also shows its advantage over the graph homotopy transformation and the s -homotopy transformation. [ABSTRACT FROM AUTHOR]

This paper is devoted to the development of algorithms for finding unit distance graphs with chromatic number greater than 4, embedded in a two-dimensional sphere or plane. Such graphs provide a lower bound for the Hadwiger–Nelson problem on the chromatic number of the plane and its generalizations to the case of the sphere. A series of 5-chromatic unit distance graphs on 64513 vertices embedded into the plane is constructed. Unlike previously known examples, these graphs do not use the Moser spindle as the base element. The construction of 5-chromatic graphs embedded in a sphere at two values of the radius is given. Namely, the 5-chromatic unit distance graph on 372 vertices embedded into the circumsphere of an icosahedron with a unit edge length, and the 5-chromatic graph on 972 vertices embedded into the circumsphere of a great icosahedron are constructed. [ABSTRACT FROM AUTHOR]

The method of augmenting graphs is a general approach to solve the Maximum Independent Set problem. Our objective is to employ this approach to develop polynomial-time algorithms for some so-called Maximum Set problems, i.e. problems which can be stated as follows. Given a (simple) graph G , find a maximum vertex subset S of G such that the subgraph induced by S satisfies a given property Π . Such problems were shown to be NP-hard in general if the properties considered are non-trivial and hereditary Lewis and Yannakakis (1980) and Yannakakis (1978). In this paper, using the augmenting graph technique, we describe a graph class, in which some problems can be solved in polynomial time. We also prove the NP-hardness of some Maximum Set problems where the considered properties are not hereditary. [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]

Given two positive integers l and m , with l ≤ m , an [ l , m ] - covering of a graph G is a set M of matchings of G whose union is the edge set of G and such that l ≤ | M | ≤ m for every M ∈ M . An [ l , m ] -covering M of G is an excessive [ l , m ] - factorization of G if the cardinality of M is as small as possible. The number of matchings in an excessive [ l , m ] -factorization of G (or ∞ , if G does not admit an excessive [ l , m ] -factorization) is a graph parameter called the excessive [ l , m ] - index of G and denoted by χ [ l , m ] ′ ( G ) . In this paper we study such parameter. Our main result is a general formula for the excessive [ l , m ] -index of a graph G in terms of other graph parameters. Furthermore, we give a polynomial time algorithm which computes χ [ l , m ] ′ ( G ) for any fixed constants l and m and outputs an excessive [ l , m ] -factorization of G , whenever the latter exists. [ABSTRACT FROM AUTHOR]

This paper examines a problem in enumerative and asymptotic combinatorics involving the classical structure of integer compositions. What is sought is an analysis on average and in distribution of the length of the longest run of consecutive equal parts in a composition of size n . The problem was posed by Herbert Wilf at the Analysis of Algorithms conference in July 2009 (see arXiv:0906.5196 ). [ABSTRACT FROM AUTHOR]

Abstract: The topological containment problem, TC( ), has been shown to be polynomial-time solvable for any fixed pattern graph , but practical algorithms have been developed only for a few specific pattern graphs. Among these are the wheels with four, five, and six spokes. This paper examines the topological containment problem where the pattern graph is a wheel with seven spokes, and gives a result that describes graphs with no -subdivision, showing how they can be built up, using certain operations, from smaller ‘pieces’ that meet certain conditions. We also discuss algorithmic aspects of the problem. [Copyright &y& Elsevier]

Abstract: Star-ladder graphs were introduced by Gross in his development of a quadratic-time algorithm for the genus distribution of a cubic outerplanar graph. This paper derives a formula for the genus distribution of star-ladder graphs, using overlap matrix and Chebyshev polynomials. [Copyright &y& Elsevier]

Abstract: In this paper, we prove that if a finite reflexive digraph admits Gumm operations, then it also admits a near unanimity operation. This is a generalization of similar results obtained earlier for posets and symmetric reflexive digraphs by the second author and his collaborators. In the special case of reflexive digraphs, our new result confirms a conjecture of Valeriote that states that any finite relational structure of finite signature that admits Gumm operations also admits an edge operation. We also prove that every finite reflexive digraph that admits a near unanimity operation admits totally symmetric idempotent operations of all arities. Finally, the aforementioned results yield a polynomial-time algorithm to decide whether a finite reflexive digraph admits a near unanimity operation. [Copyright &y& Elsevier]

Abstract: A matrix with nonnegative integer entries is minimal if the nonincreasing sequence of its entries (called -sequence) is minimal, in the dominance order of partitions, among all nonincreasing sequences of entries of matrices with nonnegative integers that have the same 1-marginals as . The starting point for this work is an identity that relates the number of minimal matrices that have fixed 1-marginals and -sequence to a linear combination of Kronecker coefficients. In this paper we provide a bijection that realizes combinatorially this identity. From this bijection we obtain an algorithm that to each minimal matrix associates a minimal component, with respect to the dominance order, in a Kronecker product, and a combinatorial description of the corresponding Kronecker coefficient in terms of minimal matrices and tableau insertion. Our bijection follows from a generalization of the dual RSK correspondence to 3-dimensional binary matrices, which we state and prove. With the same tools we also obtain a generalization of the RSK correspondence to 3-dimensional integer matrices. [Copyright &y& Elsevier]

Abstract: Fuzzy circular interval graphs are a generalization of proper circular arc graphs and have been recently introduced by Chudnovsky and Seymour as a fundamental subclass of claw-free graphs. In this paper, we provide a polynomial time algorithm for recognizing such graphs, and more importantly for building a suitable model for these graphs. [Copyright &y& Elsevier]

Abstract: For the multi-peg Tower of Hanoi problem with pegs, so far the best solution is obtained by the Stewart’s algorithm in , based on the following recurrence relation: In this paper, we generalize this recurrence relation to for two sequences of arbitrary positive integers and and we show that the sequence of differences consists of numbers of the form , with for all , arranged in nondecreasing order. We also apply this result to analyze recurrence relations for the Tower of Hanoi problems on several graphs. [Copyright &y& Elsevier]

Abstract: The antiblocking decoding algorithm established in Kroll and Vincenti (2010) is based on the notion of an antiblocking system. It is comparable with the permutation decoding algorithm. Instead of a permutation decoding set, called a PD-set, consisting of automorphisms of the code, it uses an antiblocking system, called an AI-system, consisting of information sets. As the permutation decoding algorithm is more efficient the smaller the PD-set, so the antiblocking decoding algorithm is more effective the smaller the AI-system. Therefore, it is important for the applications to find small AI-systems. As in the case of PD-sets, there is no method that guarantees in general how to construct optimal or nearly optimal AI-systems. In this paper, we present first some general results on the existence and construction of small antiblocking systems using properties of antiblocking systems derived in Kroll and Vincenti (2008) . The crucial point for the construction of antiblocking systems is a lemma, in which a recursive procedure is provided. In the second part, we apply these findings to construct small AI-systems for some codes arising from a cap of 20 points in PG(4,3). [Copyright &y& Elsevier]

Abstract: A maximum stable set in a graph is a stable set of maximum cardinality. is a local maximum stable set of , and we write , if is a maximum stable set of the subgraph induced by , where is the neighborhood of . A greedoid is called a local maximum stable set greedoid if there exists a graph such that . Nemhauser and Trotter Jr. (1975) , proved that any is a subset of a maximum stable set of . In Levit and Mandrescu (2002) we have shown that the family of a forest forms a greedoid on its vertex set. The cases where is bipartite, triangle-free, well-covered, unicycle, while is a greedoid, were analyzed in Levit and Mandrescu (2004, 2007, 2008, 2001, 2009) , respectively. In this paper, we demonstrate that if the family satisfies the accessibility property, then, first, is a greedoid, and, second, this greedoid, which we called the local maximum stable set greedoid defined by , is an interval greedoid. We also characterize those graphs whose families of local maximum stable sets are either antimatroids or matroids. For these cases, some polynomial recognition algorithms are suggested. [Copyright &y& Elsevier]

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: In this paper we establish a dichotomy theorem for the complexity of homomorphisms to fixed locally semicomplete digraphs. It is also shown that the same dichotomy holds for list homomorphisms. The polynomial algorithms follow from a different, shorter proof of a result by Gutjahr, Welzl and Woeginger. [ABSTRACT FROM AUTHOR]

Abstract: We consider the minimum rainbow subgraph problem (MRS): given a graph , whose edges are coloured with colours. Find a subgraph of of minimum order and with edges such that each colour occurs exactly once. For graphs with maximum degree there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of . In this paper we present a polynomial-time approximation algorithm with an approximation ratio of for . [ABSTRACT FROM AUTHOR]

Abstract: The Grundy number of a graph , denoted by , is the largest such that has a greedy -colouring, that is a colouring with colours obtained by applying the greedy algorithm according to some ordering of the vertices of . In this paper, we study the Grundy number of the lexicographic and cartesian products of two graphs in terms of the Grundy numbers of these graphs. Regarding the lexicographic product, we show that . In addition, we show that if is a tree or , then . We then deduce that for every fixed , given a graph , it is CoNP-Complete to decide if and it is CoNP-Complete to decide if . Regarding the cartesian product, we show that there is no upper bound of as a function of and . Nevertheless, we prove that . [Copyright &y& Elsevier]

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: -dimensional polycubes are the generalization of planar polyominoes to higher dimensions. That is, a -D polycube of size is a connected set of cells of a -dimensional hypercubic lattice, where connectivity is through -dimensional faces of the cells. Computing , the number of distinct -dimensional polycubes of size , is a long-standing elusive problem in discrete geometry. In a previous work we described the generalization from two to higher dimensions of a polyomino-counting algorithm of Redelmeier [D.H. Redelmeier, Counting polyominoes: Yet another attack, Discrete Math. 36 (1981) 191–203]. The main deficiency of the algorithm is that it keeps the entire set of cells that appear in any possible polycube in memory at all times. Thus, the amount of required memory grows exponentially with the dimension. In this paper we present an improved version of the same method, whose order of memory consumption is a (very low) polynomial in both and . We also describe how we parallelized the algorithm and ran it through the Internet on dozens of computers simultaneously. [Copyright &y& Elsevier]

Abstract: The -sparse Graph Sandwich Problem asks, given two graphs and , whether there exists a graph such that and is -sparse. In this paper we present a polynomial-time algorithm for solving the Graph Sandwich Problem for -sparse graphs. [Copyright &y& Elsevier]

Abstract: The adoption of the stress-majorization method from multi-dimensional scaling into graph layout has provided an improved mathematical basis and better convergence properties for so-called “force-directed placement” techniques. In this paper we explore algorithms for augmenting such stress-majorization techniques with simple linear constraints using gradient-projection optimization techniques. Our main focus is a particularly simple class of constraints called “orthogonal-ordering constraints” but we also discuss how gradient-projection methods may be extended to solve more general linear “separation constraints”. In addition, we demonstrate several graph-drawing applications where these types of constraints can be very useful. [Copyright &y& Elsevier]

Abstract: An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. In this paper we provide an algorithm to determine the cardinalities of endomorphism monoids of finite undirected paths. [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: In this paper we consider the problem of packing a set of d-dimensional congruent cubes into a sphere of smallest radius. We describe and investigate an approach based on a function called the maximal inflation function. In the three-dimensional case, we localize the contact between two inflated cubes and we thus improve the efficiency of calculating . This approach and a stochastic algorithm are used to find dense packings of cubes in 3 dimensions up to . For example, we obtain a packing of eight cubes that improves on the cubic lattice packing. [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: An adjacent vertex distinguishing total-coloring of a simple graph is a proper total-coloring of such that no pair of adjacent vertices meets the same set of colors. The minimum number of colors required to give an adjacent vertex distinguishing total-coloring is studied. We proved for graphs with maximum degree in this paper. [Copyright &y& Elsevier]

Abstract: In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in -time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of of the optimum in -time, where is the minimum k such that there is a spanning tree of the graph with maximum degree k. [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: Golumbic, Kaplan, and Shamir [Graph sandwich problems, J. Algorithms 19 (1995) 449–473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown [C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete. [Copyright &y& Elsevier]

Abstract: The coefficient of fragmentability of a class of graphs measures the proportion of vertices that need to be removed from the graphs in the class in order to leave behind bounded sized components. We have previously given bounds on this parameter for the class of graphs satisfying a given constant bound on maximum degree. In this paper, we give fragmentability bounds for some classes of graphs of bounded average degree, as well as classes of given thickness, the class of -colourable graphs, and the class of n-dimensional cubes. In order to establish the fragmentability results for bounded average degree, we prove that the proportion of vertices that must be removed from a graph of average degree at most in order to leave behind a planar subgraph (in fact, a series-parallel subgraph) is at most , provided or the graph is connected and . The proof yields an algorithm for finding large induced planar subgraphs and (under certain conditions) a lower bound on the size of the induced planar subgraph it finds. This bound is similar in form to the one we found for a previous algorithm we developed for that problem, but applies to a larger class of graphs. [Copyright &y& Elsevier]

Abstract: Let be the collection of all simple graphs with vertices and edges, and for let be the chromatic polynomial of . A graph is said to be optimal if another graph does not exist with for all , with strict inequality holding for some . In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of and for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4. [Copyright &y& Elsevier]

Abstract: In this paper we investigate weighted cross-intersecting families: if are given constants, we want to find the maximum of for uniform cross-intersecting families. We determine the maximum sum, even if we have restrictions of the size of . As corollaries, we will obtain some new bounds on the shadows and the shades of uniform families. We give direct proofs for these bounds, as well, and show that the theorems for cross-intersecting families also follow from these results. Finally, we will generalize the LYM inequality not only for cross-intersecting families, but also for arbitrary Sperner families. [Copyright &y& Elsevier]

Abstract: A d-dimensional array of real numbers is called monotone increasing if its entries are increasing along each dimension. Given , a monotone increasing d-dimensional array with n entries along each dimension, and a real number x, we want to decide whether , by performing a sequence of comparisons between x and some entries of . We want to minimize the number of comparisons used. In this paper we investigate this search problem, we generalize Linial and Saks’ search algorithm [N. Linial, M. Saks, Searching ordered structures, J. Algorithms 6 (1985) 86–103] for monotone three-dimensional arrays to d-dimensions for . For , our new algorithm is optimal up to the lower order terms. [Copyright &y& Elsevier]

Abstract: In this paper, we characterize the graphs with infinite cyclic edge connectivity. Then we design an efficient algorithm to determine whether a graph has finite cyclic edge connectivity or infinite cyclic edge connectivity. [Copyright &y& Elsevier]

Abstract: The binary reflected Gray code function b is defined as follows: If m is a nonnegative integer, then is the integer obtained when initial zeros are omitted from the binary reflected Gray code of m. This paper examines this Gray code function and its inverse and gives simple algorithms to generate both. It also simplifies Conder''s result that the jth letter of the kth word of the binary reflected Gray code of length n is by replacing the binomial coefficient by [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: A set S of vertices in a graph G is said to be an edge-dominating set if every edge in G is incident with a vertex in S. A cycle in G is said to be a dominating cycle if its vertex set is an edge-dominating set. Nash-Williams [Edge-disjoint hamiltonian circuits in graphs with vertices of large valency, Studies in Pure Mathematics, Academic Press, London, 1971, pp. 157–183] has proved that every longest cycle in a 2-connected graph of order n and minimum degree at least is a dominating cycle. In this paper, we prove that for a prescribed positive integer k, under the same minimum degree condition, if n is sufficiently large and if we take k disjoint cycles so that they contain as many vertices as possible, then these cycles form an edge-dominating set. Nash-Williams’ Theorem corresponds to the case of of this result. [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]