Search

In 1977 Foata proved bijectively, among other things, that the joint distribution of ascent and distinct nonzero value numbers on the set of subexcedant sequences is the same as that of descent and inverse descent numbers on the set of permutations, and the generating function of the corresponding bistatistics is the double Eulerian polynomial. In 2013 Foata’s result was rediscovered by Visontai as a conjecture, and then reproved by Aas in 2014. In this paper, we define a permutation code (that is, a bijection between permutations and subexcedant sequences) and show the more general result that two 5-tuples of set-valued statistics on the set of permutations and on the set of subexcedant sequences, respectively, are equidistributed. In particular, these results give another bijective proof of Foata’s result. [ABSTRACT FROM AUTHOR]

Mobile guards on the vertices of a graph are used to defend the graph against an infinite sequence of attacks on vertices. A guard must move from a neighboring vertex to an attacked vertex (we assume attacks happen only at vertices containing no guard and that each vertex contains at most one guard). More than one guard is allowed to move in response to an attack. The m -eternal domination number, γ m ∞ ( G ) , of a graph G is the minimum number of guards needed to defend G against any such sequence. We characterize the class of trees of order n with maximum possible m -eternal domination number, which is ⌈ n 2 ⌉ . [ABSTRACT FROM AUTHOR]

Abstract: A global offensive alliance in a graph is a subset of such that for every vertex not in at least half of the vertices in the closed neighborhood of are in . The cardinality of a minimum size global offensive alliance in is called the global offensive alliance number of . We give an upper bound on the global (strong) offensive alliance number of a graph in terms of its degree sequence. We also study global offensive alliances of random graphs. In particular, it is proved that if then with high probability has a global offensive alliance of size at most if and no global offensive alliance of size at most if . [Copyright &y& Elsevier]

Abstract: The question of necessary and sufficient conditions for the existence of a simple hypergraph with a given degree sequence is a long-standing open problem. Let denote the set of all degree sequences of simple hypergraphs on vertex set that have edges. A simple characterisation of is defined in terms of its upper and/or lower elements (degree sequences). In the process of finding all upper degree sequences, a number of results have been achieved in this paper. Classes of upper degree sequences with lowest rank (sum of degrees) and with highest rank have been found; in the case of , the unique class of isomorphic hypergraphs has been determined; the case of leads to the simple uniform hypergraph degree sequence problem. A smaller generating set has been found for . New classes of upper degree sequences have been generated from the known sequences in dimensions less than . [Copyright &y& Elsevier]

Abstract: Let us call a lattice path in from to using , , and steps and never going below the -axis, a -path (of order ). A super -path is a -path which is permitted to go below the -axis. We relate the total number of humps in all of the -paths of order to the number of super -paths, where a hump is defined to be a sequence of steps of the form , . This generalizes recent results concerning the cases when and or . A similar relation may be given involving peaks (consecutive steps of the form ). [Copyright &y& Elsevier]

Abstract: A path covering of a graph is a set of vertex disjoint paths of containing all the vertices of . The path covering number of , denoted by , is the minimum number of paths in a path covering of . A - -labeling of a graph is a mapping from to the set such that if and if . The -labeling number of is the smallest number such that has a - -labeling. The purpose of this paper is to study path covering numbers and -labeling numbers of graphs. Our main work extends most of the results in [S.S. Adams, A. Trazkovich, D.S. Troxell, B. Westgate, On island sequences of labelings with a condition at distance two, Discrete Appl. Math. 158 (2010) 1–7] and can answer an open problem in [J. Georges, D.W. Mauro, On the structure of graphs with non-surjective (2, 1)-labelings, SIAM J. Discrete Math. 19 (2005) 208–223]. [Copyright &y& Elsevier]

Abstract: A total acquisition move in a weighted graph moves all weight from a vertex to a neighboring vertex , provided that before this move the weight on is at least the weight on . The total acquisition number, , is the minimum number of vertices with positive weight that remain in after a sequence of total acquisition moves, starting with a uniform weighting of the vertices of . For , Lampert and Slater showed that when has vertices, and this is sharp. We characterize the graphs achieving equality: if and only if , where is the family of trees that can be constructed from by iteratively growing paths with three edges from neighbors of leaves. [Copyright &y& Elsevier]

Abstract: A set of vertices in a graph is a total dominating set if every vertex of is adjacent to some vertex in . The total domination number is the minimum cardinality of a total dominating set in . The annihilation number is the largest integer such that the sum of the first terms of the non-decreasing degree sequence of is at most the number of edges in . In this paper, we investigate relationships between the annihilation number and the total domination number of a graph. Let be a tree of order . We show that , and we characterize the extremal trees achieving equality in this bound. [Copyright &y& Elsevier]

Abstract: The standard Sturmian words (standard words in short) are extensively studied in combinatorics of words. They are complicated enough to have many interesting properties, and, at the same time, due to their recurrent structure, they are highly compressible. In this paper, we present compact formulas for the number of cubic runs in any standard word (denoted by ). We show also that where is the golden ratio, and present a sequence of strictly growing standard words achieving this limit. The exact asymptotic ratio here is irrational, contrary to the situation of squares and runs in the same class of words. Furthermore, we design an efficient algorithm for computing the number of cubic runs in standard words in linear time with respect to the size of a directive sequence, i.e., the compressed representation describing the word (recurrences). The explicit size of a word can be exponential with respect to this representation, and hence this is yet another example of a very fast computation on highly compressible texts. [Copyright &y& Elsevier]

Abstract: We analyze the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin deletions. We also show how some of these transformations are related to the notion of even pair introduced to color some classes of perfect graphs. Then, some properties of edge deletion and twin deletion are given and a conjecture is formulated about the class of graphs for which these transformations can be used to determine the stability number. [Copyright &y& Elsevier]

Abstract: The eternal domination problem requires a graph to be protected against an infinitely long sequence of attacks on vertices by guards located at vertices, the configuration of guards inducing a dominating set at all times. An attack at a vertex with no guard is defended by sending a guard from a neighboring vertex to the attacked vertex. We allow any number of guards to move to neighboring vertices at the same time in response to an attack. We compare the eternal domination number with the vertex cover number of a graph. One of our main results is that the eternal domination number is less than the vertex cover number of any graph of minimum degree at least two having girth at least nine. [Copyright &y& Elsevier]

Abstract: In this note, we present two sufficient conditions for determining the signs of three-term recurrence sequences. In order to determine the signs of some sequences, by our method, it suffices to compute a constant number of terms at the beginning. For example, in order to prove the positivity of the central Delannoy number , by our method, it just needs to know the recurrence relation of and the values of for . As applications, we determine the signs of some famous sequences. [Copyright &y& Elsevier]

Abstract: An unlabeled poset is said to be -free if it does not contain an induced subposet that is isomorphic to , the union of two disjoint 2-element chains. Let denote the number of -free posets of size . In a recent paper, Bousquet-Mélou et al. found, using the so called ascent sequences, the generating function for the number of -free posets of size : . We extend this result in two ways. First, we find the generating function for -free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. Second, we show that if equals the number of -free posets of size with minimal elements, then . The second result cannot be derived from the first one by a substitution. Our enumeration results are extended to certain restricted permutations and to regular linearized chord diagrams through bijections in . Finally, we define a subset of ascent sequences counted by the Catalan numbers and we discuss its relations with - and -free posets. [Copyright &y& Elsevier]

Abstract: A vertex colouring of a graph is nonrepetitive if for any path in , the first half is coloured differently from the second half. The Thue choice number of is the least integer such that for every -list assignment of , there exists a nonrepetitive -colouring of . We prove that for any positive integer , there is a tree with . On the other hand, it is proved that if is a graph of maximum degree , and is obtained from by attaching to each vertex of a connected graph of tree-depth at most rooted at , then for some constant depending only on and . [Copyright &y& Elsevier]