共查询到20条相似文献,搜索用时 15 毫秒
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.
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 相似文献
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.
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.
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 . 相似文献
11.
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.
16.
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 . 相似文献
17.
18.
19.
20.
Let be a -connected graph of order . In [1], Bondy (1980) considered a degree sum condition for a graph to have a Hamiltonian cycle, say, to be covered by one cycle. He proved that if , then has a Hamiltonian cycle. On the other hand, concerning a degree sum condition for a graph to be covered by two cycles, Enomoto et al. (1995) [4] proved that if and , then can be covered by two cycles. By these results, we conjecture that if , then can be covered by two cycles. In this paper, we prove the case of this conjecture. In fact, we prove a stronger result; if is 2-connected with , then can be covered by two cycles, or belongs to an exceptional class. 相似文献