共查询到20条相似文献,搜索用时 46 毫秒
1.
This paper considers a degree sum condition sufficient to imply the existence of vertex-disjoint cycles in a graph . For an integer , let be the smallest sum of degrees of independent vertices of . We prove that if has order at least and , with , then contains vertex-disjoint cycles. We also show that the degree sum condition on is sharp and conjecture a degree sum condition on sufficient to imply contains vertex-disjoint cycles for . 相似文献
2.
3.
4.
Let be a finite connected graph. In this note, we show that the complexity of can be obtained from the partial derivatives at of a determinant in terms of the Bartholdi zeta function of . Moreover, the second order partial derivatives at of this determinant can all be expressed as the linear combination of the Kirchhoff index, the additive degree-Kirchhoff index, and the multiplicative degree-Kirchhoff index of the graph . 相似文献
5.
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. 相似文献
6.
Susan A. van Aardt Christoph Brause Alewyn P. Burger Marietjie Frick Arnfried Kemnitz Ingo Schiermeyer 《Discrete Mathematics》2017,340(11):2673-2677
An edge-coloured graph is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph denoted by , is the smallest number of colours that are needed in order to make properly connected. Our main result is the following: Let be a connected graph of order and . If , then except when and where and 相似文献
7.
8.
Let and be two integers with and . For a graph and a vertex of , we use to denote the degree of in . Define to be the minimum value of , where is an independent set of with . This paper proves the following conjecture proposed by Gould et al. (2018). If is a graph of sufficiently large order with , then contains vertex-disjoint cycles. 相似文献
9.
David Galvin 《Discrete Mathematics》2012,312(19):2881-2892
10.
11.
Consider a graph consisting of a vertex set and an edge set . Let and denote the maximum degree and the chromatic number of , respectively. We say that is equitably -colorable if there exists a proper -coloring of such that the sizes of any two color classes differ by at most one. Obviously, if is equitably -colorable, then . Conversely, even if satisfies , we cannot guarantee that must be equitably -colorable. In 1994, the Equitable -Coloring Conjecture asserts that a connected graph with is equitably -colorable if is different from for all . In this paper, we give necessary conditions for a graph (not necessarily connected) with to be equitably -colorable and prove that those necessary conditions are also sufficient conditions when is a bipartite graph, or satisfies , or satisfies . 相似文献
12.
13.
Two graphs are said to be -cospectral (respectively, -cospectral) if they have the same (respectively, signless) Laplacian spectra, and a graph is said to be (respectively, ) if there does not exist other non-isomorphic graph such that and are -cospectral (respectively, -cospectral). Let be the degree sequence of a graph with vertices. In this paper, we prove that except for two exceptions (respectively, the graphs with ), if is -cospectral (respectively, -cospectral) with a connected graph and , then has the same degree sequence as . A spider graph is a unicyclic graph obtained by attaching some paths to a common vertex of the cycle. As an application of our result, we show that every spider graph and its complement graph are both , which extends the corresponding results of Haemers et al. (2008), Liu et al. (2011), Zhang et al. (2009) and Yu et al. (2014). 相似文献
14.
15.
Let be a set of at least two vertices in a graph . A subtree of is a -Steiner tree if . Two -Steiner trees and are edge-disjoint (resp. internally vertex-disjoint) if (resp. and ). Let (resp. ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) -Steiner trees in , and let (resp. ) be the minimum (resp. ) for ranges over all -subset of . Kriesell conjectured that if for any , then . He proved that the conjecture holds for . In this paper, we give a short proof of Kriesell’s Conjecture for , and also show that (resp. ) if (resp. ) in , where . Moreover, we also study the relation between and , where is the line graph of . 相似文献
16.
17.
18.
19.
A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs
Let be a balanced bipartite graph of order , and let be the minimum degree sum of two non-adjacent vertices in different partite sets of . In 1963, Moon and Moser proved that if , then is hamiltonian. In this note, we show that if is a positive integer, then the Moon–Moser condition also implies the existence of a 2-factor with exactly cycles for sufficiently large graphs. In order to prove this, we also give a condition for the existence of vertex-disjoint alternating cycles with respect to a chosen perfect matching in . 相似文献