共查询到20条相似文献,搜索用时 0 毫秒
1.
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. 相似文献
2.
Aysel Erey 《Discrete Mathematics》2018,341(5):1419-1431
3.
4.
Tutte’s -flow conjecture states that every -edge-connected graph admits a nowhere-zero -flow. In this paper, we characterize all graphs with independence number at most that admit a nowhere-zero -flow. The characterization of -flow verifies Tutte’s -flow conjecture for graphs with independence number at most and with order at least . In addition, we prove that every odd--edge-connected graph with independence number at most admits a nowhere-zero -flow. To obtain these results, we introduce a new reduction method to handle odd wheels. 相似文献
5.
R.S. Manikandan 《Discrete Mathematics》2010,310(21):2776-2789
In this paper, it is shown that the tensor product of the complete bipartite graph, Kr,r,r≥2, and the regular complete multipartite graph, , is Hamilton cycle decomposable. 相似文献
6.
Pasha Zusmanovich 《Indagationes Mathematicae》2019,30(2):288-299
We prove that a Lie -algebra of cohomological dimension one is one-dimensional, and discuss related questions. 相似文献
7.
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. 相似文献
8.
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. 相似文献
9.
Daniela Ferrero Leslie Hogben Franklin H.J. Kenter Michael Young 《Discrete Mathematics》2018,341(6):1789-1797
Zero forcing and power domination are iterative processes on graphs where an initial set of vertices are observed, and additional vertices become observed based on some rules. In both cases, the goal is to eventually observe the entire graph using the fewest number of initial vertices. The concept of -power domination was introduced by Chang et al. (2012) as a generalization of power domination and standard graph domination. Independently, -forcing was defined by Amos et al. (2015) to generalize zero forcing. In this paper, we combine the study of -forcing and -power domination, providing a new approach to analyze both processes. We give a relationship between the -forcing and the -power domination numbers of a graph that bounds one in terms of the other. We also obtain results using the contraction of subgraphs that allow the parallel computation of -forcing and -power dominating sets. 相似文献
10.
R.S. Manikandan 《Discrete Mathematics》2008,308(16):3586-3606
In this paper, tensor product of two regular complete multipartite graphs is shown to be Hamilton cycle decomposable. Using this result, it is immediate that the tensor product of two complete graphs with at least three vertices is Hamilton cycle decomposable thereby providing an alternate proof of this fact. 相似文献
11.
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). 相似文献
12.
Paweł Wójcik 《Indagationes Mathematicae》2019,30(1):197-200
It is well known that a linear mapping preserving the Birkhoff orthogonality (i.e. ), has to be a similarity. For real spaces it has been proved by Koldobsky (1993); a proof including both real and complex spaces has been given by Blanco and Turn?ek (2006). In the present paper the author would like to present a somewhat simpler proof of this nice theorem. Moreover, we extend the Koldobsky theorem; more precisely, we show that the linearity assumption may be replaced by additivity. 相似文献
13.
Motivated by the relation , holding for the -generalized Catalan numbers of type and , the connection between dominant regions of the -Shi arrangement of type and is investigated. More precisely, it is explicitly shown how copies of the set of dominant regions of the -Shi arrangement of type , biject onto the set of type such regions. This is achieved by exploiting two different viewpoints of the representative alcove of each region: the Shi tableau and the abacus diagram. In the same line of thought, a bijection between copies of the set of -Dyck paths of height
and the set of lattice paths inside an rectangle is provided. 相似文献
14.
15.
Greg Malen 《Discrete Mathematics》2018,341(9):2567-2574
For any fixed graph , we prove that the topological connectivity of the graph homomorphism complex Hom() is at least , where , for the minimum degree of a vertex in a subgraph . This generalizes a theorem of C?uki? and Kozlov, in which the maximum degree was used in place of , and provides a high-dimensional analogue of the graph theoretic bound for chromatic number, , as . Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom when for a fixed constant . 相似文献
16.
17.
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. 相似文献
18.
Integer compositions and related enumeration problems have been of interest to combinatorialists and number theorists for a long time. The cyclic and colored analogues of this concept, although interesting, have not been extensively studied. In this paper we explore the combinatorics of -color cyclic compositions, presenting generating functions, bijections, asymptotic formulas related to the number of such compositions, the number of parts, and the number of restricted parts. 相似文献
19.
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 . 相似文献