Discrete Applied Mathematics

We study decision trees which are totally optimal relative to different sets of complexity parameters for Boolean functions. A totally optimal tree is an optimal tree relative to each parameter from the set simultaneously. We consider the parameters ...

It has been known since 1996 (work of Cai et al.) that the sequence of Hamming weights { w t ( f n ( x 1 , ź , x n ) ) } , where f n is a symmetric Boolean function of degree d in n variables, satisfies a linear recurrence with integer coefficients. In ...

Rotation symmetric Boolean functions have been used as components of different cryptosystems. In this paper, based on the knowledge of compositions of an integer, a new construction of balanced 2 p -variable rotation symmetric Boolean functions with ...

We consider a competitive diffusion process for two players on two-dimensional toroidal grid graphs. Pure Nash equilibria for the game are completely characterized; i.e., for arbitrary-sized toroidal grid graphs, we list all the initial positions that ...

V -order is a global order on strings related to Unique Maximal Factorization Families (UMFFs), themselves generalizations of Lyndon words. V -order has recently been proposed as an alternative to lexicographic order in the computation of suffix arrays ...

Given a tree and a set P of non-trivial simple paths on it, Vpt ( P ) is the VPT graph (i.e.źthe vertex intersection graph) of the paths P of the tree T , and Ept ( P ) is the EPT graph (i.e.źthe edge intersection graph) of P . These graphs have been ...

In this paper we study the set chromatic number of a random graph G ( n , p ) for a wide range of p = p ( n ) . We show that the set chromatic number, as a function of p , forms an intriguing zigzag shape.

A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. A plane (simple) graph in which each face is a triangle is called a (plane) triangulation. In the first of a sequence of three papers the authors ...

A piecewise linear simple curve in the plane made up of k + 1 line segments, each of which is either horizontal or vertical, with consecutive segments being of different orientation is called a k -bend path. Given a graph G , a collection of k -bend ...

A non-empty subset S of the vertices of a connected graph G = ( V ( G ) , E ( G ) ) is a safe set if, for every connected component C of G S and every connected component D of G - S , we have | C | ź | D | whenever there exists an edge of G between C ...

Given the Kekulé structure of a fullerene that gives its Clar structure, the Kekulé edges that do not lie on any benzene ring of the Clar structure lie on open chains that pair up the pentagonal faces and perhaps some closed chains. In this paper, we ...

We consider the problem of minimizing the makespan of a schedule on m parallel machines of n jobs, where each job requires exactly one of s additional unit resources. This problem collapses to P ź C max if every job requires a different resource. It is ...

In a fundamental paper in polyhedral combinatorics, Queyranne describes the complete facial structure of a classical object in combinatorial optimization, the single machine scheduling polytope. In the same paper, he answers essentially all relevant ...

The classical first and second Zagreb indices of a graph G are defined as M 1 ( G ) = ź v ź V d G ( v ) 2 and M 2 ( G ) = ź u v ź E ( G ) d G ( u ) d G ( v ) , where d G ( v ) is the degree of the vertex v of graph G . Recently, Furtula etźal. (2014) ...

A Grünbaum coloring of a triangulation G on a surface is a 3-edge coloring of G such that each face of G receives three distinct colors on its boundary edges. In this paper, we prove that every Fisk triangulation on the projective plane P has a Grünbaum ...

A k -hypertournament H on n vertices with 2 ź k ź n is a pair H = ( V , A H ) , where V is a set of n vertices and A H is a set of k -tuples of vertices, called arcs, such that for any k -subset S of V , A H contains exactly one of the k ! k -tuples ...

Let G be a undirected graph without loops and multiple edges. By ź ( G ) , ź ( G ) and p ( G ) we respectively denote the nullity, the dimension of cycle space, and the number of pendant vertices of G . If each component of G contains at least two ...

We use the well-known Maiorana-McFarland class to construct several important combinatorial structures. In the first place, we easily identify infinite classes of vectorial plateaued functions { F } : F 2 n ź F 2 n such that all non-zero linear ...

Motivated by the work of Zhang and Yan (2009), this paper considers the problem of computing resistance distances and Kirchhoff index of graphs with an involution. We show that if G is a weighted graph with an involution, then the resistance distance ...

The hidden weighted bit function (HWBF) is a well-known benchmark function in the branching program literature. In Wang etźal.ź(2014),authors investigated the cryptographic properties of the HWBF and found that it seems to be a very good candidate for ...

Let G be a cubic graph with a perfect matching. An edge e of G is a forcing edge if it is contained in a unique perfect matching M , and the perfect matching M is called uniquely forced. In this paper, we show that a 3-connected cubic graph with a ...

The atom-bond connectivity (ABC) index is a degree-based topological index. It was introduced due to its applications in modeling the properties of certain molecular structures and has been since extensively studied. In this note, we examine the ...

Let G be a connected graph of order n with diameter d . Remoteness ź of G is the maximum average distance from a vertex to all others and ź 1 ź ź ź ź n are the distance eigenvalues of G . Aouchiche and Hansen (0000), Aouchiche and Hansen conjectured ...

The edge revised Szeged index S z e ź ( G ) is defined as S z e ź ( G ) = ź e = u v ź E ( m u ( e ) + m 0 ( e ) / 2 ) ( m v ( e ) + m 0 ( e ) / 2 ) , where m u ( e ) and m v ( e ) are, respectively, the number of edges of G lying closer to vertex u than ...

We provide explicit formulas for the maximum number q k ( n ) of disjoint subgraphs isomorphic to the k -dimensional hypercube in the n -dimensional Fibonacci cube ź n for small k , and prove that the limit of the ratio of such cubes to the number of ...