共查询到20条相似文献,搜索用时 250 毫秒
1.
Jeong-Hyun Kang 《Discrete Mathematics》2018,341(1):96-103
The vertices of Kneser graph are the subsets of of cardinality , two vertices are adjacent if and only if they are disjoint. The square of a graph is defined on the vertex set of with two vertices adjacent if their distance in is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when . It is believed that where is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: for 1 (Kim and Park, 2014) and for (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to , where is a constant in , depending on . 相似文献
2.
3.
A second order asymptotic expansion in the local limit theorem for a simple branching random walk in
Zhi-Qiang Gao 《Stochastic Processes and their Applications》2018,128(12):4000-4017
Consider a branching random walk, where the underlying branching mechanism is governed by a Galton–Watson process and the migration of particles by a simple random walk in . Denote by the number of particles of generation located at site . We give the second order asymptotic expansion for . The higher order expansion can be derived by using our method here. As a by-product, we give the second order expansion for a simple random walk on , which is used in the proof of the main theorem and is of independent interest. 相似文献
4.
5.
6.
A graph is minimally -tough if the toughness of is and the deletion of any edge from decreases the toughness. Kriesell conjectured that for every minimally -tough graph the minimum degree . We show that in every minimally -tough graph . We also prove that every minimally -tough, claw-free graph is a cycle. On the other hand, we show that for every positive rational number any graph can be embedded as an induced subgraph into a minimally -tough graph. 相似文献
7.
Let be a prime power and be a positive integer. A subspace partition of , the vector space of dimension over , is a collection of subspaces of such that each nonzero vector of is contained in exactly one subspace in ; the multiset of dimensions of subspaces in is then called a Gaussian partition of . We say that contains a direct sum if there exist subspaces such that . In this paper, we study the problem of classifying the subspace partitions that contain a direct sum. In particular, given integers and with , our main theorem shows that if is a subspace partition of with subspaces of dimension for , then contains a direct sum when has a solution for some integers and belongs to the union of two natural intervals. The lower bound of captures all subspace partitions with dimensions in that are currently known to exist. Moreover, we show the existence of infinite classes of subspace partitions without a direct sum when or when the condition on the existence of a nonnegative integral solution is not satisfied. We further conjecture that this theorem can be extended to any number of distinct dimensions, where the number of subspaces in each dimension has appropriate bounds. These results offer further evidence of the natural combinatorial relationship between Gaussian and integer partitions (when ) as well as subspace and set partitions. 相似文献
8.
Let and be two positive integers such that and . A graph is an -parity factor of a graph if is a spanning subgraph of and for all vertices , and . In this paper we prove that every connected graph with vertices has an -parity factor if is even, , and for any two nonadjacent vertices , . This extends an earlier result of Nishimura (1992) and strengthens a result of Cai and Li (1998). 相似文献
9.
10.
The purpose of this note is to show a new series of examples of homogeneous ideals I in for which the containment fails. These ideals are supported on certain arrangements of lines in , which resemble Fermat configurations of points in , see [14]. All examples exhibiting the failure of the containment constructed so far have been supported on points or cones over configurations of points. Apart from providing new counterexamples, these ideals seem quite interesting on their own. 相似文献
11.
Aysel Erey 《Discrete Mathematics》2018,341(5):1419-1431
12.
A matching in a 3-uniform hypergraph is a set of pairwise disjoint edges. A -matching in a 3-uniform hypergraph is a matching of size . Let be a partition of vertices such that and . Denote by the 3-uniform hypergraph with vertex set consisting of all those edges which contain at least two vertices of . Let be a 3-uniform hypergraph of order such that for any two adjacent vertices . In this paper, we prove contains a -matching if and only if is not a subgraph of . 相似文献
13.
Johnson proved that if are coprime integers, then the th moment of the size of an -core is a polynomial of degree in for fixed . After that, by defining a statistic size on elements of affine Weyl group, which is preserved under the bijection between minimal coset representatives of and -cores, Thiel and Williams obtained the variance and the third moment about the mean of the size of an -core. Later, Ekhad and Zeilberger stated the first six moments about the mean of the size of an -core and the first nine moments about the mean of the size of an -core using Maple. To get the moments about the mean of the size of a self-conjugate -core, we proceed to follow the approach of Thiel and Williams, however, their approach does not seem to directly apply to the self-conjugate case. In this paper, following Johnson’s approach, by Ehrhart theory and Euler–Maclaurin theory, we prove that if are coprime integers, then the th moment about the mean of the size of a self-conjugate -core is a quasipolynomial of period 2 and degree in for fixed odd . Then, based on a bijection of Ford, Mai and Sze between self-conjugate -cores and lattice paths in rectangle and a formula of Chen, Huang and Wang on the size of self-conjugate -cores, we obtain the variance, the third moment and the fourth moment about the mean of the size of a self-conjugate -core. 相似文献
14.
Haiyang Zhu Lianying Miao Sheng Chen Xinzhong Lü Wenyao Song 《Discrete Mathematics》2018,341(8):2211-2219
Let be the set of all positive integers. A list assignment of a graph is a function that assigns each vertex a list for all . We say that is --choosable if there exists a function such that for all , if and are adjacent, and if and are at distance 2. The list--labeling number of is the minimum such that for every list assignment , is --choosable. We prove that if is a planar graph with girth
and its maximum degree is large enough, then . There are graphs with large enough and having . 相似文献
15.
16.
17.
In this paper, we employed lattice model to describe the three internally vertex-disjoint paths that span the vertex set of the generalized Petersen graph . We showed that the is 3-spanning connected for odd . Based on the lattice model, five amalgamated and one extension mechanisms are introduced to recursively establish the 3-spanning connectivity of the . In each amalgamated mechanism, a particular lattice trail was amalgamated with the lattice trails that was dismembered, transferred, or extended from parts of the lattice trails for , where a lattice tail is a trail in the lattice model that represents a path in . 相似文献
18.
We study solutions of the focusing energy-critical nonlinear heat equation in . We show that solutions emanating from initial data with energy and -norm below those of the stationary solution W are global and decay to zero, via the “concentration-compactness plus rigidity” strategy of Kenig–Merle [33], [34]. First, global such solutions are shown to dissipate to zero, using a refinement of the small data theory and the -dissipation relation. Finite-time blow-up is then ruled out using the backwards-uniqueness of Escauriaza–Seregin–Sverak [17], [18] in an argument similar to that of Kenig–Koch [32] for the Navier–Stokes equations. 相似文献
19.
In this paper, we consider -cycle decomposition of
and directed -cycle decompositions of and , where and denote the wreath product and tensor product of graphs, respectively. Using the results obtained here, we prove that for , the obvious necessary conditions for the existence of a -decomposition of are sufficient whenever where is a prime and . Also, we show that the necessary conditions for the existence of -decompositions of and are sufficient whenever is a prime, where denotes the directed cycle of length . 相似文献
20.
Fares Maalouf 《Journal of Pure and Applied Algebra》2018,222(5):1003-1005
We show that if k is an infinite field, then there exists a subspace of dimension , such that no nonzero member of W has infinitely many zeros. This generalizes a result from a paper by Bergman and Nahlus, and partly answers another question from the same paper. 相似文献