Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
More algorithmic results for problems of spread of influence in edge-weighted graphs with and without incentives: More algorithmic results for problems of spread of influence
No full textMany phenomena in real-world social networks are interpreted as the spread of influence between activated and non-activated elements within the network. These phenomena are formulated by combinatorial graphs, where vertices represent the elements and edges represent social ties between elements. A main problem is to study important subsets of elements (target sets or dynamic monopolies) such that their activation spreads to the entire network. In edge-weighted networks, the influence between two adjacent vertices depends on the weight of their edge. In models with incentives, the main problem is to minimize the total amount of incentives (called optimal target vectors) that can be offered to vertices such that some vertices are activated and their activation spreads to the whole network. Algorithmic study of target sets and vectors is a hot research field. We prove an inapproximability result for optimal target sets in edge-weighted networks, even for complete graphs. Some other hardness and polynomial time results are presented for optimal target vectors and degenerate threshold assignments in edge-weighted networks. Lastly, we obtain a hardness result for target sets in edge-weighted tournaments
Fibonacci numbers and n-color compositions
Full text linkAgarwal defined -colour compositions as ordered -colour partitions in 2000. In this paper, we relate -colour compositions with a problem of sewage water treatment using a bijection which involves the well-known Fibonacci numbers. In addition, we study a new restricted -colour composition function combinatorially. Our work also includes a one-to-one correspondence between restricted -colour compositions and the number of ways to tile a particular type of rectangle using dominoes and squares
Hankel determinants of certain sequences of Bernoulli polynomials: A direct proof of an inverse matrix entry from statistics
Full text linkWe calculate the Hankel determinants of sequences of Bernoulli polynomials. This corresponding Hankel matrix comes from statistically estimating the variance in nonparametric regression. Besides its entries’ natural and deep connection with Bernoulli polynomials, a special case of the matrix can be constructed from a corresponding Vandermonde matrix. As a result, instead of asymptotic analysis, we give a direct proof of calculating an entry of its inverse. Further extensions also include an identity of Stirling numbers of the both kinds
Beta distributions whose moment sequences are related to integer sequences listed in the OEIS
Full text linkWe recall some basic properties of the Beta distribution and some of its modifications. We identified around of the moment sequences of Beta distributions as important integer sequences in the OEIS base of integer sequences. Among those identified are Catalan, Riordan, Motzkin, or `super ballot numbers\u27. By applying a method of expansion of the ratio of densities of involved distributions we are able to obtain some known and many unknown relationships between e.g. Catalan numbers and other moment sequences of the Beta distributions
The existence of hypersolids in whose Heesch number is
No full textIn a recent article, it was shown that the Heesch number in is asymptotically unbounded for , by showing that, for each of the form , there exists a hypersolid in whose Heesch number equals . We here show that the same holds not only for of the form , but for any ,
Diophantine equation with balancing-like sequences associated with the Shorey–Tijdeman-type problem
Full text linkLet be the balancing-like sequence defined by with initial terms for . In this study, we demonstrate how to find all the solutions of the Diophantine equation,
in fixed integers , n_1 > n_2 > n_3\geq 0, n_4 >n_5 > n_6 \geq 0, and , where are given integers satisfying
On a construction of self-orthogonal codes from orbit matrices of 2-designs
Full text linkIn 2003, Harada and Tonchev presented a construction of self-orthogonal codes from orbit matrices of symmetric -designs with fixed point free automorphisms. Since then, the constructions of self-orthogonal codes from orbit matrices of -designs has been extensively studied. In this paper, we present new constructions of self-orthogonal codes from orbit matrices of -designs for the cases not covered by the previously described methods. We construct self-orthogonal codes from orbit matrices of - and - designs. Some of the constructed codes are optimal
Circuit partitions and signed interlacement in 4-regular graphs
Full text linkLet be a 4-regular graph. Each circuit partition of has a corresponding touch-graph ; the circuits in correspond to vertices of , and the vertices of correspond to edges of . We discuss the connection between modified versions of the interlacement matrix of an Euler system of and the cycle space of , over and
A different approach to Gauss Fibonacci polynomials
Full text linkIn this paper with the help of higher order Fibonacci polynomials, we introduce higher order Gauss Fibonacci polynomials that generalize the Gauss Fibonacci polynomials studied by Özkan and Taştan. We give a recurrence relation, Binet-like formula, generating and exponential generating functions, summation formula for the higher order Gauss Fibonacci polynomials. Moreover, we give two special matrices that we call and respectively. From these matrices, we obtain a matrix representation and derive the Cassini\u27s identity of higher order Gauss Fibonacci polynomials
Construction of (a, b, c) tilings of the Euclidean plane, hyperbolic plane, and the sphere
No full textAn tiling forms under its symmetry group orbits of vertices; orbits of edges; and orbits of tiles. This paper discusses a method to arrive at an tiling of the Euclidean plane (), hyperbolic plane () or 2-dimensional sphere (). An application of the method facilitates the complete enumeration of the tiling of and as well as a listing of tilings of