Search

The path-connectivity of a graph G is the maximal k for which between any k pairs of vertices there are k edge-disjoint paths (one between each pair). An upper bound for the path-connectivity of nq(q

This paper surveys recent work in matroid representation theory and discusses a number of open problems.

It is shown that any set of three lattice points in n-dimensional Euclidean space Rn tiles the lattice Zn. An example is given of a set of cardinality 4n−2[12n] which does not tile Zn.

RésuméLes nombres d'Entringer qui avaient été introduits pour compter les permutations alternées en fonction de leur premier terme trouvent ici jeux interprétations naturelles pour les arbres d'André: ils répartissent ces arbres en fonction d'une part de l'antécédent direct du plus grand sommet, d'autre part de l'extrémité d'une certaine chaîne définite de maniére univoque.The Entringer's integers were introduced to enumerate the down-up (or up-down) permutations according to the first term; in this paper they are shown to enumerate Andre's trees according to the direct antecedent of the greatest vertex and also according to the vertex which is at the end of a specific sequence of vertices.

Dushnik and Miller defined the dimensions of a partially ordered set X,denoted dim X, as the smallest positive integer t for which there exist t linear extensions of X whose intersection is the partial ordering on X. Hiraguchi proved that if n ≥2 and |X| ≤2n+1, then dim X ≤ n. Bogart, Trotter and Kimble have given a forbidden subposet characterization of Hiraguchi's inequality by determining for each n ≥ 2, the minimum collection of posets ϱn such that if |X| ⩽2n+1, the dim X < n unless X contains one of the posets from ϱn. Although |ϱ3|=24, for each n ≥ 4, ϱn contains only the crown S0n — the poset consisting of all 1 element and n − 1 element subsets of an n element set ordered by inclusion. In this paper, we consider a variant of dimension, called interval dimension, and prove a forbidden subposet characterization of Hiraguchi's inequality for interval dimension: If n ≥2 and |X 2n+1, the interval dimension of X is less than n unless X contains S0n.

The problem of finding the complexity of the Nonlinear feedforward sequences has been analysed and a unified method has been developed for finding the complexity of such sequences for the cases when feedback is 1. (i) an irreducible polynomial; 2. (ii) product of two irreducible polynomials; 3. (iii) power of an irreducible polynomial. The method is based on the minimum polynomial of the compound matrix formed from the companion matrix of the feedback polynomial. Apart from being a unified method, this approach has the advantage that it can be applied to any level of logic and one can get the minimal generator of all possible non-linear feedforward sequences.

We find the Hamming weight distribution of some classes of linear codes. The cyclic codes in these classes have composite parity-check polynomials.

A general graph partitioning problem, which includes graph colouring, homomorphism to H, conditional colouring, contractibility to H, and partition into cliques as special cases, is introduced and its complexity is studied.

We describe a simple way of partitioning a planar graph into three edge-disjoint forests in O(n log n) time, where n is the number of its vertices. We can use this partition in Kannan et al.'s graph representation (1992) to label the planar graph vertices so that any two vertices' adjacency can be tested locally by comparing their names in constant time.

The paper presents several characterizations of outerplanar graphs, some of them are counterparts of the well-known characterizations of planar graphs and the other provide very efficient tools for outerplanarity testing, coding (i.e. isomorphism testing), and counting such graphs. Finally, we attempt to generalize these results for k -outerplanar graphs.

Two linear time algorithms are shown to solve the n -object SUBSET-SUM problem with probability approaching 1 as n gets large, for a uniform instance distribution. Precise evaluations of the probabilities involved are given.

We present a formal long-division algorithm for solving the well-known group minimisation problem. In fact, given some group elements with associated positive costs, the algorithm produces a listing of all products of these elements, in ascending order of total cost. It may thus be applied to the solution of all-integer linear programs, by finding the cheapest solution to the group minimisation problem consistent with feasibility.

Let G be a simple graph with e perfectly reliable edges and n nodes which fail independently and with the same probability p. The residual connectedness reliability R(G, p) of G is the probability that the graph induced by the surviving nodes is connected. If Γ(n, e) is the collection of all n node e edge simple graphs, then G ϵ Γ(n, e) is uniformly most reliable if R(G, p) ⩾ R(G′, p) for all G′ ϵ Γ(n, e) and all 0 < p < 1. If S3(G) is the number of three point induced connected subgraphs of G, then G ϵ Γ(n, e) is S3-maximum if S3(G) ⩾ S3(G′) for all G′ ϵ Γ (n, e). It is known that if G ϵ Γ(n, e) is S3-maximum and p is sufficiently large then R(G, p) > R(G, p′) for all non-S3-maximum graphs G′ ϵ Γ (n, e). This paper characterizes the S3-maximum graphs in Γ(n, e) for the range e ⩽ (n22/4) + (2n− 3)/4.

It is known that there exist EOL forms for which no form equivalent propagating EOL form exist. We present nondegenerate hierarchies refining this result.

With each bounded lattice L is associated a simplicial complex KL. If X is a cross-cut of L, then a simplicial complex KX is defined. It is shown that the geometric realizations of KX and KL are homotopy equivalent.

I introduce in the MV n algebras of Revaz Grigolia two chains of unary operations, which are the key in establishing many connections between these algebras and n -valued Lukasiewicz-Moisil algebras (LM n algebras for short). The study has three parts. It is self-contained as much as possible. The main result of the first part is that MV 4 algebras coincide with LM 4 algebras. The larger class of ‘relaxed’-MV n algebras is also introduced and studied. This class is related to the class of generalized LM n pre-algebras. The main results of the second part are that, for n ⩾5, any MV n algebra is an LM n algebra and that the canonical MV n algebra can be identified with the canonical LM n algebra. In the third part, the class of good LM n algebras and the class of ⊕-proper LM n algebras are introduced and studied. ⊕-proper LM n algebras coincide (can be identified) with Cignoli's proper n -valued Lukasiewicz algebras. MV n algebras coincide with good LM n algebras and with ⊕-proper LM n algebras ( n ⩾2). I also give the construction of an LM 3 (LM 4 ) algebra from the odd (respectively even)-valued LM n algebra ( n ⩾5), which proves that LM 4 algebras are as much important as LM 3 algebras; the MV n algebras help us to see that.

In this paper the Clar covering polynomial of a hexagonal system is introduced. In fact it is a kind of F polynomial [4] of a graph, and can be calculated by recurrence relations. We show that the number of aromatic sextets (in a Clar formula), the number of Clar formulas, the number of Kekule structures and the first Herndon number for any Kekulean hexagonal system can be easily obtained by its Clar covering polynomial. In addition, we give some theorems to calculate the Clar covering polynomial of a hexagonal system. As examples we finally derive the explicit expressions of the Clar covering polynomials for some small hexagonal systems and several types of catacondensed hexagonal systems. A relation between the resonance energy and the Clar covering polynomial of a hexagonal system is considered in the next paper.

We describe the notions of synchronization and simplification with respect to a given subsemigroup P of a semigroup S in terms of the syntactic semigroup of P. These notions derive from coding theory, which corresponds to the case where P is a free subsemigroup of a free semigroup; we apply the results to give a unified account of several theorems previously published.

The following inequality chain has been extensively studied in the discrete mathematical literature: if⩽y⩽i⩽β⩽Γ⩽ IR , where ir and IR denote the lower and upper irredundance numbers of a graph, γ and Γ denote the lower and upper domination numbers of a graph, i denotes the independent domination number and β denotes the vertex independence number of a graph. More than one hundred papers have been published on aspects of this chain. In this paper we define a simple mechanism which explains why this inequality chain exists and how it is possible to define many similar chains of potentially arbitrary length.

An explicit, non-recursive formula for the Wiener index of any given benzenoid chain is derived, greatly speeding up calculations and rendering it manually manageable, through a novel envisioning of chains as ternary strings. Previous results are encompassed and two completely new and useful ones are obtained, a formula to determine Wiener indices of benzenoid chains in periodic patterns, and another to estimate errors in the Wiener index induced by errors or indeterminate links in the graph.

We characterize the n -tuples (a 1 ,…,a n ) for which one can find a i lines in the i th direction in the n -cube, i =1,… n , so that all lines are disjoint.

We introduce the concept of a weakly metric association scheme, a generalization of metric schemes. We undertake a combinatorial study of the parameters of codes in these schemes, along the lines of [9]. Applications are codes over Zq for the Lee distance and arithmetic codes for the modular distance. Our main result is an inequality which generalizes both the Delsarte upper bound on covering radius, and the MacWilliams lower bound on the external distance, yielding a strong necessary existence condition on completely regular codes. The external distance (in the Lee metric) of some self-dual codes of moderate length over Z5 is computed.

Let W ( n , k ) denote the graph of order n obtained from a wheel W n by deleting all but k consecutive spokes. It is known that W ( n ,1) ( n ⩾4) and W ( n ,2) ( n ⩾4) are χ-unique. Chao and Whitehead [1] showed that W ( n ,3) ( n ⩾5) and W ( n ,4) ( n ⩾6)are also χ-unique but pointed out that W (7,5) is not so. In this note, we prove that W ( n ,5) is χ-unique for n ⩾8.

The join Knc ∨ 2K2 is the graph obtained by taking a copy of Knc and two disjoint copies of K2, disjoint from Knc, and joining every vertex of Knc to every vertex of 2K2. In this paper we show that for each positive integer n, the graph Knc ∨ 2K2 admits a p-valuation and has gracefulness 4n + 3. Further, for any finite set S0 of positive integers and n ⩾ 2Max {x ∈ ϵ S0} + 1, a new graph valuation, ρ(n; S0), is introduced. Finally, some open problems are proposed.

Let χ s ′(G), called the strong coloring number of G , denote the minimum number of colors for which there is a proper edge coloring of a graph G in which no two of its vertices is incident to edges colored with the same set of colors. It is shown that χ s ′(G) ⩽ ⌈cn⌉, 1 2 , whenever Λ ( G ) is appropriately bounded as a function of n , where n is the order of G . This result is in the direction of the conjecture that χ s ′( G ) ⩽ n + 1 for each graph G with no isolated edges and at most one isolated vertex.

We describe a general method of construction for sets of mutually orthogonal latin squares (MOLS) from left neofields. We give detailed information for all isomorphically distinct left neofields of order

A parallel algorithm to recognize cographs with a linear processor bound and a log2n time bound is presented. This result extends the result of Adhar and Peng (1990). Moreover, we get a better time processor product than the algorithm of Lin and Olariu (1991). As a consequence distance hereditary graphs can be recognized by the same processor and time bound.

A Steiner quasigroup is a quasigroup satisfying the identities x(xy) = y, (yx)x = y and x2 = x. It is well known that the spectrum for Steiner quasigroups is the set of all positive integers such that n ≡ 1 or 3 (mod 6). A Steiner quasigroup is reverse provided that its automorphism group contains an involution fixing exactly one element. The spectrum for reverse Steiner quasigroups has recently been shown to be set of all positive integers such that n ≡ 1, 3, 9 or 19 (mod 24). This paper gives a new construction for reverse Steiner quasigroups and is used to construct large numbers of nonisomorphic reverse Steiner quasigroups. (For example, 10500 nonisomorphic reverse Steiner quasigroups of order 171.

Let M be a matroid on a finite set E ( M ). Then M is packable by bases if E ( M ) is the disjoint union of bases. A partial packing of M is a collection of disjoint bases whose union is a proper subset of E ( M ). M is a randomly packable by bases if every partial packing can be extended to a packing of M . This paper determines the structure of the matroids that are randomly packable by bases. It also gives a characterization, in terms of forbidden restrictions, of the simple matroids that are randomly packable by 3-circuits.

In a linear (n, k) code, a set of k coordinates is said to be an information set for the code if the projection map onto those k coordinates is a vector space isomorphism. Extended (cyclic) quadratic-residue codes are linear (p+1,12(p+1)) codes, defined whenever p is prime. The automorphism group of this code contains PSL(2, p) (the Gleason-Prange theorem). This group includes elements with order 12(p+1) and it is conceivable that one or both orbits of such an element will serve as an information set for the code. When this happens, simplified decoding procedures are possible.These codes can be defined over a ring of algebraic integers in such a way that the QR code with entries in a finite field is just the image of this global code under a residue-class map. It is shown that the global code includes a codeword of the form (z(p) 0 0 … 0) on a given orbit, where z(p) is a rational integer. A series of theorems show that knowing this codeword is enough to answer the question (for either orbit) for QR codes over fields of any characteristic. (Briefly an orbit can fail to be an information set for the characteristic q case if and only if q devides z(p). A method for finding this codeword is given which is based on a connection between z(p) and the determinant of a certain 0, 1-matrix. The results of this technique are given which answer the question for 5 ⩽ p ⩽ 83.

It is shown that if a graph has a cycle double cover, then its line graph also has a cycle double cover. The converse of this result for 2-edge-connected graphs would imply the truth of the cycle double cover conjecture.

A finite subset of the union of the polar axis and the equator of a sphere is called a suspension. We prove that if n points in 3-space determine the maximum number of furthest neighbours then they form a suspension. The exact maximum and the optimal arrangement are also given. This sharpens a result of Avis, Erdos and Pach.

For a lattice L of finite length we denote by J(L) the set of all join-irreducible elements (≠0) of L. By u′ we mean the uniquely determined lower cover of an element uϵJ(L). Our main result is the following theorem: A lattice L of finite length is (upper) semimodular if and only if it satisfies the exchange property (EP): c⩽b∨u and c≰b∨u′ imply u⩽b∨c∨u′ (b, cϵL;uϵJ(L)).

In this paper a polynomial algorithm for the prime factorization of finite, connected nonbipartite graphs with respect to the cardinal product is presented. This algorithm also decomposes finite, connected graphs into their prime factors with respect to the strong product and provides the basis for a new proof of the uniqueness of the prime factorization of finite, connected nonbipartite graphs with respect to the cardinal product. Furthermore, some of the consequences of these results and several open problems are discussed.

Let G=(V,E) be a graph and e ∈E an unknown edge. In order to find ē we choose a sequence of test sets W⊂V, where after every test we are told whether both vertices incident to ē are in W, or not. For c(G), the minimum number of tests required, the inequality c(G)≥⌈log2|E|⌉ clearly holds (information theoretic lower bound). It was conjectured by Chang and Hwang that for a bipartite graph G this lower bound is always achieved. Here we show c(G)≤⌈log2|E|⌉+1 for bipartite graphs and c(G)≤⌈log2+|E|⌉+3 for arbitrary graphs.

We show that a regular graph G of order at least 6 whose complement Ḡ is bipartite has total chromatic number d(G)+1 if and only if 1. (i) G is not a complete graph, and 2. (ii) G ≠K n, n when n is even. As an aid in the proof of this, we also show that, for n⩾4, if the edges of a Hamiltonian path of K2n are coloured with 2n - 1 colours, each edge receiving a different colour, then this can be extended to an edge-colouring of K2n with the same set of 2n–1 colours.

This paper establishes a relation between the Clar covering polynomial of hexagonal systems and chromatic polynomials. As applications, the explicit expressions of chromatic polynomials of some types of graphs are derived. This paper also presents various results on Clar cover equivalence and uniqueness of hexagonal systems.

This paper gives a lower bound and an upper bound for the covering radius of optimum codes. The upper bound so obtained is better than other known upper bounds, restricted to optimum codes. Optimum codes of covering radius d −1 and d −2 are shown to be normal.

One approach to analyzing the structure of an ordered set has been to characterize its structure in terms of that of related objects, and vice versa. For example results in [2] characterize in terms of the ordered set P when the lattice Z(P) of lower sets (also called initial segments) of P and the ordered set Id(P) of order ideals (or simply ideals) of P have infinite antichains. The results in [2] are that Z(P) has an infinite antichain if and only if P has an infinite antichain or P has a copy of one of three specific ordered sets; likewise, it is shown that Id(P) has an infinite antichain if and only if P has one or P has a copy of a certain ordered set. In this paper we ‘dismantle’ these results by characterizing separately when P has an infinite antichain or a copy of each of the ordered sets which gives an infinite antichain in Z(P) or Id(P). We begin by describing the ordered sets which play a role in these results. We use w to denote the natural numbers in their usual order, 1 G 2 c 3, . . . , and md denotes the natural numbers in the opposite order, 12 223, . . . . By o @ md, we mean the disjoint union of w and md, where each is given the order indicated, and there is no comparison between elements of w and those of gd. Thus, an ordered set contains a copy of o @ md if and only if it has an infinite ascending chain and an infinite descending chain such that any pair of elements, one from each chain, is incomparable. Let K = {(i, j) E N X N 1 i < j}, and define an order on K by (i, j) s (r, s) if and only if i = r and j c s, or j < r. The Hasse diagram of K is given in Fig. 1, along with that of Kd, the set K with the opposite order.

We consider the problem of characterizing the matrices of 0's and 1's whose permanental minors are restricted to a prescribed set.

This is a partly survey, partly new results paper about Ramsey games. Ramsey games belong to the wider class of positional games. In Section 1 we briefly recall the basic concepts and results of positional games in general, and apply them to the particular case of Ramsey games. For a more detailed introduction to the theory of positional games, including proofs, we refer the reader to Beck [4] and [5].

We show that the lattice of noncrossing (set) partitions is self-dual and that it admits a symmetric chain decomposition. The self-duality is proved via an order-reversing involution. Two proofs are given of the existence of the symmetric chain decomposition, one recursive and one constructive. Several identities involving Catalan numbers emerge from the construction of the symmetric chain decomposition.

Let k be a nonzero, commutative ring with 1, and let R be a k-algebra with a countably-infinite ordered free k-basis B = [pn: n ⩾ 0]. We characterize and analyze those bases from which one can construct a k-algebra of ‘formal B-series’ of the form f=∑cnpn, with cn e k, showing inter alia that many classical polynomial bases fail to have this property.

We introduce a parameter called the level of nonmultiplicativity of a graph, which is related to Hedetniemi's conjecture. We show that this parameter is equal to the number of factors in a factorization of the graph into a product of multiplicative graphs. Apart from the known multiplicative graphs, no graph is known to have a finite level of nonmultiplicativity. We show that the countably infinite complete graph Kℵ0 has an infinite level of nonmultiplicativity and that there exist Kneser graphs with arbitrarily high levels of nonmultiplicativity.

Nous proposons une preuve combinatoire de la formule de Lagrange pour les fonctions a deux variables. Cette preuve s'appuie ur l'etude d'un langage generalisant celui de Lukacievicz et sur la λ-conjugaison notion qui etend la conjugaison habituelle des mots du monoide libre.

For a given integer λ ⩾ 1, we define a λ-claw as a graph H which is connected and contains a vertex w such that H-w is the union of three pairwise remote connected subgraphs with exactly λ vertices each. We define a graph to be λ-claw-free if it contains no induced subgraph isomorphic to a λ-claw. We show that if G is a k-connected (k integer, k ⩾ 2), λ-claw-free graph such that if for every two remote connected subgraphs S1, S2 of G of order λ we have d(S1) + d(S2) > n − (k + 1)λ − k, or if for every three pairwise remote, connected subgraphs S1, S2, S3 of G of order λ we have d(S1) + d(S2) + d(S3) > n − (k + 1)λ + 1, then G contains a cycle C such that every component of G − V(C) has at most λ − 1 vertices.

Let G be the collection of sets T such that the greedy algorithm obtains the optimal T-span of K"n for all n>=1, E the collection of sets T such that sp"T(G)=sp"T(K"@g"("G")) is true for all graphs G. Many families in G or E have been discovered. We know that r-initial set and k multiple of s set are all in [email protected]?E. Liu (T-colorings of graphs, Discrete Math. 10 (1992), 203-212) extended k multiple of s set by union with another set S^'. In this paper, we continue to study the T-set in G and E, extending some T-sets by the similar way.

Let S be an n-element set. In this paper, we determine the smallest number f(n) for which there exists a family of subsets of S{A"1,A"2,...,A"f"("n")} with the following property: Given any two elements x, y @? S (x y), there exist k, l such that A"k @? A"l= @A, and x @? A"k, y @? A"l. In particular it is shown that f(n)= 3 log"3n when n is a power of 3.