Search

A new graph invariant called the secure vertex cover pebbling number, which is a combination of two graph invariants, namely, 'secure vertex cover' and 'cover pebbling number', is introduced in this paper. The secure vertex cover pebbling number of a graph, G , is the minimum number m so that every distribution of m pebbles can reach some secure vertex cover of G by a sequence of pebbling moves. In this paper, the complexity of the secure vertex cover problem and secure vertex cover pebbling problem are discussed. Also, we obtain some basic results and the secure vertex cover pebbling number for complete r -partite graphs, paths, Friendship graphs, and wheel graphs. [ABSTRACT FROM AUTHOR]

A set system F is intersecting if for any F , F ′ ∈ F , F ∩ F ′ ≠ ∅ . A fundamental theorem of Erdős, Ko and Rado states that if F is an intersecting family of r -subsets of [ n ] = { 1 , … , n } , and n ≥ 2 r , then | F | ≤ n − 1 r − 1 . Furthermore, when n > 2 r , equality holds if and only if F is the family of all r -subsets of [ n ] containing a fixed element. This was proved as part of a stronger result by Hilton and Milner. In this note, we provide new injective proofs of the Erdős–Ko–Rado and the Hilton–Milner theorems. [ABSTRACT FROM AUTHOR]

A Gray code is a listing structure for a set of combinatorial objects such that some consistent (usually minimal) change property is maintained throughout adjacent elements in the list. While Gray codes for m-ary strings have been considered in the past, we provide a new, simple Gray code for fixed-weight m-ary strings. In addition, we consider a relatively new type of Gray code known as overlap cycles and prove basic existence results concerning overlap cycles for fixed-weight and weight-range m-ary words. [ABSTRACT FROM AUTHOR]

Graph pebbling is a network optimization model for transporting discrete resources that are consumed in transit: the movement of 2 pebbles across an edge consumes one of the pebbles. The pebbling number of a graph is the fewest number of pebbles t so that, from any initial configuration of t pebbles on its vertices, one can place a pebble on any given target vertex via such pebbling steps. It is known that deciding whether a given configuration on a particular graph can reach a specified target is NP-complete, even for diameter 2 graphs, and that deciding whether the pebbling number has a prescribed upper bound is Πp2-complete. On the other hand, for many families of graphs there are formulas or polynomial algorithms for computing pebbling numbers; for example, complete graphs, products of paths (including cubes), trees, cycles, diameter 2 graphs, and more. Moreover, graphs having minimum pebbling number are called Class 0, and many authors have studied which graphs are Class 0 and what graph properties guarantee it, with no characterization in sight. In this paper we investigate an important family of diameter 3 chordal graphs called split graphs; graphs whose vertex set can be partitioned into a clique and an independent set. We provide a formula for the pebbling number of a split graph, along with an algorithm for calculating it that runs in O(nβ) time, where β = 2ω/(ω +1) #8773; 1.41 and ω ≅ 2.376 is the exponent of matrix multiplication. Furthermore we determine that all split graphs with minimum degree at least 3 are Class 0. [ABSTRACT FROM AUTHOR]

Steiner quadruple systems are set systems in which every triple is contained in a unique quadruple. It is well known that Steiner quadruple systems of order v, or SQS( v), exist if and only if [ABSTRACT FROM AUTHOR]

Universal cycles are generalizations of de Bruijn cycles and Gray codes that were introduced originally by Chung, Diaconis, and Graham in 1992. They have been developed by many authors since, for various combinatorial objects such as strings, subsets, permutations, partitions, vector spaces, and designs. One generalization of universal cycles, which require almost complete overlap of consecutive words, is s-overlap cycles, which relax such a constraint. In this paper we study weak orders, which are relations that are transitive and complete. We prove the existence of universal and s-overlap cycles for weak orders, as well as for fixed height and/or weight weak orders, and apply the results to cycles for ordered partitions. [ABSTRACT FROM AUTHOR]

Graph pebbling is a game played on a connected graph G. A player purchases pebbles at a dollar a piece and hands them to an adversary who distributes them among the vertices of G (called a configuration) and chooses a target vertex r. The player may make a pebbling move by taking two pebbles off of one vertex and moving one of them to a neighboring vertex. The player wins the game if he can move k pebbles to r. The value of the game ( G, k), called the k-pebbling number of G and denoted ππk( G), is the minimum cost to the player to guarantee a win. That is, it is the smallest positive integer m of pebbles so that, from every configuration of size m, one can move k pebbles to any target. In this paper, we use the block structure of graphs to investigate pebbling numbers, and we present the exact pebbling number of the graphs whose blocks are complete. We also provide an upper bound for the k-pebbling number of diameter-two graphs, which can be the basis for further investigation into the pebbling numbers of graphs with blocks that have diameter at most two. [ABSTRACT FROM AUTHOR]

Let S be a cyclic n–ary sequence. We say that S is a universal cycle ((n, k)–Ucycle) for k–subsets of [n] if every such subset appears exactly once contiguously in S, and is a Ucycle packing if every such subset appears at most once. Few examples of Ucycles are known to exist, so the relaxation to packings merits investigation. A family (Sn) of (n, k)–Ucycle packings for fixed k is a near–Ucycle if the length of Sn is (1 – o(1)) (n k) . In this paper we prove that near–(n, k)–Ucycles exist for all k. [ABSTRACT FROM AUTHOR]

Abstract: Deo and Micikevicius recently gave a new bijection for spanning trees of complete bipartite graphs. In this paper we devise a generalization of Deo and Micikevicius''s method, which is also a modification of Olah''s method for encoding the spanning trees of any complete multipartite graph . We also give a bijection between the spanning trees of a planar graph and those of any of its planar duals. Finally we discuss the possibility of bijections for spanning trees of DeBriujn graphs, cubes, and regular graphs such as the Petersen graph that have integer eigenvalues. [Copyright &y& Elsevier]

The pebbling number of a graph is the smallest number t such that from any initial configuration of t pebbles one can move a pebble to any prescribed vertex by a sequence of pebbling steps. It is known that graphs whose connectivity is high compared to their diameter have a pebbling number as small as possible. We will use the above result to prove two related theorems. First, answering a question of the second author, we show that there exist graphs of arbitrarily high constant girth and least possible pebbling number. In the second application, we prove that the product of two graphs of high minimum degree has a pebbling number equal to the number of vertices of the product. This shows that Graham's product conjecture is true in the case of high minimum degree graphs. In addition, we consider a probabilistic variant of the pebbling problem and establish a pebbling threshold result for products of paths. The last result shows that the sequence of paths satisfies the probabilistic analogue of Graham's product conjecture. [ABSTRACT FROM AUTHOR]

A family of sets is intersecting if any two sets in the family intersect. Given a graph G and an integer r ≥ 1 , let I (r) (G) denote the family of independent sets of size r of G. For a vertex v of G , the family of independent sets of size r that contain v is called an r -star. Then G is said to be r -EKR if no intersecting subfamily of I (r) (G) is bigger than the largest r -star. Let n be a positive integer, and let G consist of the disjoint union of n paths each of length 2. We prove that if 1 ≤ r ≤ n ∕ 2 , then G is r -EKR. This affirms a longstanding conjecture of Holroyd and Talbot for this class of graphs and can be seen as an analogue of a well-known theorem on signed sets, proved using different methods, by Deza and Frankl and by Bollobás and Leader. Our main approach is a novel probabilistic extension of Katona's elegant cycle method, which might be of independent interest. [ABSTRACT FROM AUTHOR]

A partially ordered set P is called a circle containment order provided one can assign to each x∈ P a circle Cso that $$x \leqslant y \Leftrightarrow C_x \subseteq C_y $$ . We show that the infinite three-dimensional poset N is not a circle containment order and note that it is still unknown whether or not [ n] is such an order for arbitrarily large n. [ABSTRACT FROM AUTHOR]

Graph pebbling is a network model for transporting discrete resources that are consumed in transit. Deciding whether a given configuration on a particular graph can reach a specified target is NP -complete, even for diameter two graphs, and deciding whether the pebbling number has a prescribed upper bound is Π 2 P -complete. Recently we proved that the pebbling number of a split graph can be computed in polynomial time. This paper advances the program of finding other polynomial classes, moving away from the large tree width, small diameter case (such as split graphs) to small tree width, large diameter, continuing an investigation on the important subfamily of chordal graphs called k -trees. In particular, we provide a formula, that can be calculated in polynomial time, for the pebbling number of any semi-2-tree, falling shy of the result for the full class of 2-trees. [ABSTRACT FROM AUTHOR]