Vol. 13 no. 3

1. Digital search trees with m trees: Level polynomials and insertion costs

Prodinger, Helmut.
We adapt a novel idea of Cichon's related to Approximate Counting to the present instance of Digital Search Trees, by using m (instead of one) such trees. We investigate the level polynomials, which have as coefficients the expected numbers of data on a given level, and the insertion costs. The […]
Section: Analysis of Algorithms

2. On the number of maximal independent sets in a graph

Wood, David, .
Miller and Muller (1960) and independently Moon and Moser (1965) determined the maximum number of maximal independent sets in an n-vertex graph. We give a new and simple proof of this result.
Section: Combinatorics

3. New Upper Bounds for the Heights of Some Light Subgraphs in 1-Planar Graphs with High Minimum Degree

Zhang, Xin ; Wu, Jian-Liang ; Liu, Guizhen.
A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph of minimum degree 6 contains a copy of 4-cycle with all vertices of degree at most 19. In addition, we also show that the complete graph K 4 […]
Section: Combinatorics

4. The Variance of the Profile in Digital Search Trees

Kazemi, Ramin ; Vahidi-Asl, Mohammad Q..
What today we call digital search tree (DST) is Coffman and Eve's sequence tree introduced in 1970. A digital search tree is a binary tree whose ordering of nodes is based on the values of bits in the binary representation of a node's key. In fact, a digital search tree is a digital tree in which […]
Section: Analysis of Algorithms

5. On the Book Thickness of k-Trees

Dujmović, Vida ; Wood, David, .
Every k-tree has book thickness at most k + 1, and this bound is best possible for all k \textgreater= 3. Vandenbussche et al. [SIAM J. Discrete Math., 2009] proved that every k-tree that has a smooth degree-3 tree decomposition with width k has book thickness at most k. We prove this result is best […]
Section: Graph and Algorithms

6. On the complexity of vertex-coloring edge-weightings

Dudek, Andrzej ; Wajc, David.
Given a graph G = (V; E) and a weight function omega : E -\textgreater R, a coloring of vertices of G, induced by omega, is defined by chi(omega) (nu) = Sigma(e(sic)nu) omega (e) for all nu is an element of V. In this paper, we show that determining whether a particular graph has a weighting of the […]
Section: Graph and Algorithms

7. On the number of factors in codings of three interval exchange

Ambrož, Petr ; Frid, Anna ; Masáková, Zuzana ; Pelantová, Edita.
We consider exchange of three intervals with permutation (3, 2, 1). The aim of this paper is to count the cardinality of the set 3iet (N) of all words of length N which appear as factors in infinite words coding such transformations. We use the strong relation of 3iet words and words coding exchange […]
Section: Graph Theory

8. On packing of two copies of a hypergraph

Pilsniak, Monika ; WoźniaK, Mariusz.
A 2-packing of a hypergraph H is a permutation sigma on V (H) such that if an edge e belongs to epsilon(H), then sigma(e) does not belong to epsilon(H). Let H be a hypergraph of order n which contains edges of cardinality at least 2 and at most n - 2. We prove that if H has at most n - 2 edges then […]
Section: Graph and Algorithms

9. The largest singletons in weighted set partitions and its applications

Sun, Yidong ; Xu, Yanjie.
Recently, Deutsch and Elizalde studied the largest fixed points of permutations. Motivated by their work, we consider the analogous problems in weighted set partitions. Let A (n,k) (t) denote the total weight of partitions on [n + 1] = \1,2,..., n + 1\ with the largest singleton \k + 1\. In this […]
Section: Combinatorics

10. Nordhaus-Gaddum Type Results for Total Domination

Henning, Michael,  ; Joubert, Ernst ; Southey, Justin.
A Nordhaus-Gaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In this paper we study Nordhaus-Gaddum-type results for total domination. We examine the sum and product of γt(G1) and γt(G2) where G1 ⊕G2 = K(s,s), and γt is the total […]
Section: Graph Theory

11. 8-star-choosability of a graph with maximum average degree less than 3

Chen, Min ; Raspaud, André ; Wang, Weifan.
A proper vertex coloring of a graphGis called a star-coloring if there is no path on four vertices assigned to two colors. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring c such that c(v) epsilon L(v). If G is L-star-colorable for any list assignment L with […]
Section: Graph and Algorithms