共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
Aysel Erey 《Discrete Mathematics》2018,341(5):1419-1431
3.
4.
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 . 相似文献
5.
Ju Zhou 《Discrete Mathematics》2018,341(4):1021-1031
A graph is induced matching extendable or IM-extendable if every induced matching of is contained in a perfect matching of . In 1998, Yuan proved that a connected IM-extendable graph on vertices has at least edges, and that the only IM-extendable graph with vertices and edges is , where is an arbitrary tree on vertices. In 2005, Zhou and Yuan proved that the only IM-extendable graph with vertices and edges is , where is an arbitrary tree on vertices and is an edge connecting two vertices that lie in different copies of and have distance 3 between them in . In this paper, we introduced the definition of -joint graph and characterized the connected IM-extendable graphs with vertices and edges. 相似文献
6.
For a subgraph of , let be the maximum number of vertices of that are pairwise distance at least three in . In this paper, we prove three theorems. Let be a positive integer, and let be a subgraph of an -connected claw-free graph . We prove that if , then either can be covered by a cycle in , or there exists a cycle in such that . This result generalizes the result of Broersma and Lu that has a cycle covering all the vertices of if . We also prove that if , then either can be covered by a path in , or there exists a path in such that . By using the second result, we prove the third result. For a tree , a vertex of with degree one is called a leaf of . For an integer , a tree which has at most leaves is called a -ended tree. We prove that if , then has a -ended tree covering all the vertices of . This result gives a positive answer to the conjecture proposed by Kano et al. (2012). 相似文献
7.
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. 相似文献
8.
The graph grabbing game is a two-player game on weighted connected graphs where all weights are non-negative. Two players, Alice and Bob, alternately remove a non-cut vertex from the graph (i.e., the resulting graph is still connected) and get the weight assigned to the vertex, where the starting player is Alice. Each player’s aim is to maximize his/her outcome when all vertices have been taken, and Alice wins the game if she gathered at least half of the total weight. Seacrest and Seacrest (2017) proved that Alice has a winning strategy for every weighted tree with even order, and conjectured that the same statement holds for every weighted connected bipartite graph with even order. In this paper, we prove that Alice wins the game on a type of a connected bipartite graph with even order called a -tree. 相似文献
9.
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 . 相似文献
10.
Francesca Astengo Michael G. Cowling Bianca Di Blasio 《Journal of Functional Analysis》2019,276(1):127-147
We compute the “norm” of irreducible uniformly bounded representations of . We show that the Kunze–Stein version of the uniformly bounded representations has minimal norm in its similarity class of uniformly bounded representations. 相似文献
11.
Adam Kabela 《Discrete Mathematics》2018,341(3):579-587
Studying the shortness of longest cycles in maximal planar graphs, we improve the upper bound on the shortness exponent of the class of -tough maximal planar graphs presented by Harant and Owens (1995). In addition, we present two generalizations of a similar result of Tká? who considered -tough maximal planar graphs (Tká?, 1996); we remark that one of these generalizations gives a tight upper bound. We fix a problematic argument used in both mentioned papers. 相似文献
12.
The aim of this paper is to investigate the existence and uniqueness of solutions for nonlinear fractional -difference equations with three-point boundary conditions. Our approach relies on a new fixed point theorem of increasing concave operators defined on ordered sets. Further, we can construct a monotone explicit iterative scheme to approximate the unique solution. Finally, the main results are illustrated with the aid of two interesting examples. 相似文献
13.
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 . 相似文献
14.
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 . 相似文献
15.
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 . 相似文献
16.
17.
18.
For integers , a -coloring of a graph is a proper coloring with at most colors such that for any vertex with degree , there are at least min different colors present at the neighborhood of . The -hued chromatic number of , , is the least integer such that a -coloring of exists. The list-hued chromatic number of is similarly defined. Thus if , then . We present examples to show that, for any sufficiently large integer , there exist graphs with maximum average degree less than 3 that cannot be -colored. We prove that, for any fraction , there exists an integer such that for each , every graph with maximum average degree is list -colorable. We present examples to show that for some there exist graphs with maximum average degree less than 4 that cannot be -hued colored with less than colors. We prove that, for any sufficiently small real number , there exists an integer such that every graph with maximum average degree satisfies . These results extend former results in Bonamy et al. (2014). 相似文献
19.
20.
Tathagata Basak 《Journal of Pure and Applied Algebra》2018,222(10):3036-3042