共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
3.
4.
For a graph , the -dominating graph of has vertices corresponding to the dominating sets of having cardinality at most , where two vertices of are adjacent if and only if the dominating set corresponding to one of the vertices can be obtained from the dominating set corresponding to the second vertex by the addition or deletion of a single vertex. We denote the domination and upper domination numbers of by and , respectively, and the smallest integer for which is connected for all by . It is known that , but constructing a graph such that appears to be difficult.We present two related constructions. The first construction shows that for each integer and each integer such that , there exists a graph such that , and . The second construction shows that for each integer and each integer such that , there exists a graph such that , and . 相似文献
5.
In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials and . Then, he defined and to be the polynomials satisfying and . In this paper, we give a combinatorial interpretation of the coefficients of and prove a symmetry of the coefficients, i.e., . We give a combinatorial interpretation of and prove that is a polynomial in with non-negative integer coefficients. We also prove that if then all coefficients of except the coefficient of are non-negative integers. For all , the coefficient of in is , and when some other coefficients of are also negative. 相似文献
6.
Let be an array of nonnegative numbers satisfying the recurrence relation with and unless . In this paper, we first prove that the array can be generated by some context-free Grammars, which gives a unified proof of many known results. Furthermore, we present criteria for real rootedness of row-generating functions and asymptotical normality of rows of . Applying the criteria to some arrays related to tree-like tableaux, interior and left peaks, alternating runs, flag descent numbers of group of type , and so on, we get many results in a unified manner. Additionally, we also obtain the continued fraction expansions for generating functions related to above examples. As results, we prove the strong -log-convexity of some generating functions. 相似文献
7.
《Stochastic Processes and their Applications》2020,130(4):2127-2158
Let be an ergodic diffusion with invariant distribution . Consider the empirical measure where is an Euler scheme with decreasing steps which approximates . Given a test function , we obtain sharp concentration inequalities for which improve the results in Honoré et al. (2019). Our hypotheses on the test function cover many real applications: either is supposed to be a coboundary of the infinitesimal generator of the diffusion, or is supposed to be Lipschitz. 相似文献
8.
Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs and , the -colored Gallai–Ramsey number is defined to be the minimum integer such that and for every , every rainbow -free coloring (using all colors) of the complete graph contains a monochromatic copy of . In this paper, we first provide some exact values and bounds of . Moreover, we define the -colored bipartite Gallai–Ramsey number as the minimum integer such that and for every , every rainbow -free coloring (using all colors) of the complete bipartite graph contains a monochromatic copy of . Furthermore, we describe the structures of complete bipartite graph with no rainbow and , respectively. Finally, we find the exact values of (), (where is a subgraph of ), and by using the structural results. 相似文献
9.
10.
《Indagationes Mathematicae》2019,30(6):1079-1086
Let be a nonzero integer. A set of nonzero integers such that is a perfect square for all is called a --tuple. In this paper, we consider the question, for a given integer which is not a perfect square, how large and how small can be the largest element in a -quadruple. We construct families of -quadruples in which the largest element is of order of magnitude , resp. . 相似文献
11.
A graph is -colorable if it admits a vertex partition into a graph with maximum degree at most and a graph with maximum degree at most . We show that every -free planar graph is -colorable. We also show that deciding whether a -free planar graph is -colorable is NP-complete. 相似文献
12.
《Discrete Mathematics》2022,345(8):112903
Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number is the least integer k for which G admits a coloring with k colors such that each color class induces a -degenerate subgraph of G. So is the chromatic number and is the point arboricity. The point partition number with was introduced by Lick and White. A graph G is called -critical if every proper subgraph H of G satisfies . In this paper we prove that if G is a -critical graph whose order satisfies , then G can be obtained from two non-empty disjoint subgraphs and by adding t edges between any pair of vertices with and . Based on this result we establish the minimum number of edges possible in a -critical graph G of order n and with , provided that and t is even. For the corresponding two results were obtained in 1963 by Tibor Gallai. 相似文献
13.
Let and be positive integers with . Given a permutation of integers , we consider -consecutive sums of , i.e., for , where we let . What we want to do in this paper is to know the exact value of where denotes the set of all permutations of . In this paper, we determine the exact values of for some particular cases of and . As a corollary of the results, we obtain , and for any . 相似文献
14.
《Discrete Mathematics》2022,345(11):113059
Let be the finite field of q elements and let be the dihedral group of 2n elements. Left ideals of the group algebra are known as left dihedral codes over of length 2n, and abbreviated as left -codes. Let . In this paper, we give an explicit representation for the Euclidean hull of every left -code over . On this basis, we determine all distinct Euclidean LCD codes and Euclidean self-orthogonal codes which are left -codes over . In particular, we provide an explicit representation and a precise enumeration for these two subclasses of left -codes and self-dual left -codes, respectively. Moreover, we give a direct and simple method for determining the encoder (generator matrix) of any left -code over , and present several numerical examples to illustrative our applications. 相似文献
15.
《Discrete Mathematics》2022,345(9):112977
Consider functions , where A and C are disjoint finite sets. The weakly connected components of the digraph of such a function are cycles of rooted trees, as in random mappings, and isolated rooted trees. Let and . When a function is chosen from all possibilities uniformly at random, then we find the following limiting behaviour as . If , then the size of the maximal mapping component goes to infinity almost surely; if , a constant, then process counting numbers of mapping components of different sizes converges; if , then the number of mapping components converges to 0 in probability. We get estimates on the size of the largest tree component which are of order when and constant when , . These results are similar to ones obtained previously for random injections, for which the weakly connected components are cycles and linear trees. 相似文献
16.
Alexander Iksanov Konrad Kolesko Matthias Meiners 《Stochastic Processes and their Applications》2019,129(11):4480-4499
Let be Biggins’ martingale associated with a supercritical branching random walk, and let be its almost sure limit. Under a natural condition for the offspring point process in the branching random walk, we show that if the law of belongs to the domain of normal attraction of an -stable distribution for some , then, as , there is weak convergence of the tail process , properly normalized, to a random scale multiple of a stationary autoregressive process of order one with -stable marginals. 相似文献
17.
18.
Let be the -color Ramsey number of an odd cycle of length . It is shown that for each fixed , for all sufficiently large , where is a constant. This improves an old result by Bondy and Erd?s (1973). 相似文献
19.
20.