共查询到10条相似文献,搜索用时 125 毫秒
1.
Given a nonnegative integer and a positive integer , a graph is said to be -colorable if the vertices of can be colored with colors such that every vertex has at most neighbors receiving the same color as itself. Let be the family of planar graphs without -cycles adjacent to cycles of length 3 or 5. This paper proves that everyone in is -colorable. This is the best possible in the sense that there are members in which are not -colorable. 相似文献
2.
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 . 相似文献
3.
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 . 相似文献
4.
5.
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). 相似文献
6.
7.
Aysel Erey 《Discrete Mathematics》2018,341(5):1419-1431
8.
David Gilat Isaac Meilijson Laura Sacerdote 《Stochastic Processes and their Applications》2018,128(6):1849-1856
For a martingale starting at with final variance , and an interval , let be the normalized length of the interval and let be the normalized distance from the initial point to the lower endpoint of the interval. The expected number of upcrossings of by is at most if and at most otherwise. Both bounds are sharp, attained by Standard Brownian Motion stopped at appropriate stopping times. Both bounds also attain the Doob upper bound on the expected number of upcrossings of for submartingales with the corresponding final distribution. Each of these two bounds is at most , with equality in the first bound for . The upper bound on the length covered by during upcrossings of an interval restricts the possible variability of a martingale in terms of its final variance. This is in the same spirit as the Dubins & Schwarz sharp upper bound on the expected maximum of above , the Dubins & Schwarz sharp upper bound on the expected maximal distance of from , and the Dubins, Gilat & Meilijson sharp upper bound on the expected diameter of . 相似文献
9.
10.
Houssein El Turkey 《Journal of Pure and Applied Algebra》2018,222(1):181-190
The complexity of a module is the rate of growth of the minimal projective resolution of the module while the z-complexity is the rate of growth of the number of indecomposable summands at each step in the resolution. Let () be the type II orthosymplectic Lie superalgebra of types B or D. In this paper, we compute the complexity and the z-complexity of the simple finite-dimensional -supermodules. We then give these complexities certain geometric interpretations using support and associated varieties. 相似文献