共查询到20条相似文献,搜索用时 46 毫秒
1.
《Discrete Mathematics》2022,345(9):112942
A graph G is k-degenerate if every subgraph of G has a vertex with degree at most k. Using the Euler's formula, one can obtain that planar graphs without 3-cycles are 3-degenerate. Wang and Lih, and Fijav? et al. proved the analogue results for planar graphs without 5-cycles and planar graphs without 6-cycles, respectively. Recently, Liu et al. showed that planar graphs without 3-cycles adjacent to 5-cycles are 3-degenerate. In this work, we generalized all aforementioned results by showing that planar graphs without mutually adjacent 3-,5-, and 6-cycles are 3-degenerate. A graph G without mutually adjacent 3-,5-, and 6-cycles means that G cannot contain three graphs, say , and , where is a 3-cycle, is a 5-cycle, and is a 6-cycle such that each pair of , and are adjacent. As an immediate consequence, we have that every planar graph without mutually adjacent 3-,5-, and 6-cycles is DP-4-colorable. This consequence also generalizes the result by Chen et al that planar graphs without 5-cycles adjacent to 6-cycles are DP-4-colorable. 相似文献
2.
3.
《Discrete Mathematics》2020,343(8):111922
Tribonacci cubes are induced subgraphs of , obtained by removing all the vertices that contain more than two consecutive 1’s. In the present work, we give some enumerative properties related to . We show that the number of vertices of weight in is and express the number of edges of these graphs in terms of convolved Tribonacci numbers. We investigate the cube polynomials of Tribonacci cubes and determine the corresponding generating function. Finally, we give a formula for the number of induced -cubes in . 相似文献
4.
5.
We give exact growth rates for the number of bipartite graceful permutations of the symbols that start with for (equivalently, -labelings of paths with vertices that have as a pendant label). In particular, when the growth is asymptotically like for . The number of graceful permutations of length grows at least this fast, improving on the best existing asymptotic lower bound of . Combined with existing theory, this improves the known lower bounds on the number of Hamiltonian decompositions of the complete graph and on the number of cyclic oriented triangular embeddings of and . We also give the first exponential lower bound on the number of R-sequencings of . 相似文献
6.
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. 相似文献
7.
8.
Jesse Geneson 《Discrete Mathematics》2019,342(5):1489-1491
Permutations of the positive integers avoiding arithmetic progressions of length 5 were constructed in Davis et al. (1977), implying the existence of permutations of the integers avoiding arithmetic progressions of length 7. We construct a permutation of the integers avoiding arithmetic progressions of length 6. We also prove a lower bound of on the lower density of subsets of positive integers that can be permuted to avoid arithmetic progressions of length 4, sharpening the lower bound of from LeSaulnier and Vijay (2011). 相似文献
9.
In this article, we study the structure of finitely ramified mixed characteristic valued fields. For any two complete discrete valued fields and of mixed characteristic with perfect residue fields, we show that if the n-th residue rings are isomorphic for each , then and are isometric and isomorphic. More generally, for , there is depending only on the ramification indices of and such that any homomorphism from the -th residue ring of to the -th residue ring of can be lifted to a homomorphism between the valuation rings. Moreover, we get a functor from the category of certain principal Artinian local rings of length n to the category of certain complete discrete valuation rings of mixed characteristic with perfect residue fields, which naturally generalizes the functorial property of unramified complete discrete valuation rings. Our lifting result improves Basarab's relative completeness theorem for finitely ramified henselian valued fields, which solves a question posed by Basarab, in the case of perfect residue fields. 相似文献
10.
An important problem on almost perfect nonlinear (APN) functions is the existence of APN permutations on even-degree extensions of larger than 6. Browning et al. (2010) gave the first known example of an APN permutation on the degree-6 extension of . The APN permutation is CCZ-equivalent to the previously known quadratic Kim κ-function (Browning et al. (2009)). Aside from the computer based CCZ-inequivalence results on known APN functions on even-degree extensions of with extension degrees less than 12, no theoretical CCZ-inequivalence result on infinite families is known. In this paper, we show that Gold and Kasami APN functions are not CCZ-equivalent to permutations on infinitely many even-degree extensions of . In the Gold case, we show that Gold APN functions are not equivalent to permutations on any even-degree extension of , whereas in the Kasami case we are able to prove inequivalence results for every doubly-even-degree extension of . 相似文献
11.
《Discrete Mathematics》2022,345(1):112659
In a recent paper, Gerbner, Patkós, Tuza and Vizer studied regular F-saturated graphs. One of the essential questions is given F, for which n does a regular n-vertex F-saturated graph exist. They proved that for all sufficiently large n, there is a regular -saturated graph with n vertices. We extend this result to both and and prove some partial results for larger complete graphs. Using a variation of sum-free sets from additive combinatorics, we prove that for all , there is a regular -saturated with n vertices for infinitely many n. Studying the sum-free sets that give rise to -saturated graphs is an interesting problem on its own and we state an open problem in this direction. 相似文献
12.
《Discrete Mathematics》2022,345(11):113065
13.
《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. 相似文献
14.
《Discrete Mathematics》2022,345(3):112740
In this paper, we construct a number of 4-GDDs where the group sizes are all congruent to 2 (mod 3). We also show that 4-GDDs of type exist for all but a finite number of feasible values of s and t. The largest unknown case has type and has 152 points. A number of 4-GDDs with at most 50 points are also constructed. These include one of type , the last feasible type of the form with at most 50 points for which no 4-GDD was known. 相似文献
15.
16.
17.
For any positive integers and , we prove that the number of monic irreducible polynomials of degree n over in which the coefficients of , and are prescribed has period 24 as a function of n, after a suitable normalization. A similar result holds over , with the period being 60. We also show that this is a phenomena unique to characteristics 2 and 5. The result is strongly related to the supersingularity of certain curves associated with cyclotomic function fields, and in particular it complements an equidistribution result of Katz. 相似文献
18.
We consider a stack sorting algorithm where only the appropriate output values are popped from the stack and then any remaining entries in the stack are run through the stack in reverse order. We identify the basis for the 2-reverse pass sortable permutations and give computational results for some classes with larger maximal rev-tier. We also show all classes of -reverse pass sortable permutations are finitely based. Additionally, a new Entringer family consisting of maximal rev-tier permutations of length was discovered along with a bijection between this family and the collection of alternating permutations of length . We calculate generating functions for the number permutations of length and exact rev-tier . 相似文献
19.
《Discrete Mathematics》2019,342(4):1089-1097
Given integers , a family of sets satisfies the property if among any members of it some intersect. We prove that for any fixed integer constants , a family of -intervals satisfying the property can be pierced by points, with constants depending only on and . This extends results of Tardos, Kaiser and Alon for the case , and of Kaiser and Rabinovich for the case . We further show that similar bounds hold in families of subgraphs of a tree or a graph of bounded tree-width, each consisting of at most connected components, extending results of Alon for the case . Finally, we prove an upper bound of on the fractional piercing number in families of -intervals satisfying the property, and show that this bound is asymptotically sharp. 相似文献
20.
《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. 相似文献