共查询到20条相似文献,搜索用时 15 毫秒
1.
Let σk(G) denote the minimum degree sum of k independent vertices in G and α(G) denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5(G) 〉 n + 3σ(G) + 11, then G is Hamiltonian. 相似文献
2.
Mingquan Zhan 《Discrete Applied Mathematics》2010,158(17):1971-1975
Let G be a graph and let D6(G)={v∈V(G)|dG(v)=6}. In this paper we prove that: (i) If G is a 6-connected claw-free graph and if |D6(G)|≤74 or G[D6(G)] contains at most 8 vertex disjoint K4’s, then G is Hamiltonian; (ii) If G is a 6-connected line graph and if |D6(G)|≤54 or G[D6(G)] contains at most 5 vertex disjoint K4’s, then G is Hamilton-connected. 相似文献
3.
Weihua Yang Liming Xiong Hongjian Lai Xiaofeng Guo 《Applied Mathematics Letters》2012,25(11):1835-1838
Thomassen conjectured that every 4-connected line graph is Hamiltonian. Lai et al. conjectured [H. Lai, Y. Shao, H. Wu, J. Zhou, Every 3-connected, essentially 11-connected line graph is Hamiltonian, J. Combin. Theory Ser. B 96 (2006) 571–576] that every 3-connected, essentially 4-connected line graph is Hamiltonian. In this note, we first show that the conjecture posed by Lai et al. is not true and there is an infinite family of counterexamples; we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is Hamiltonian; examples show that all conditions are sharp. 相似文献
4.
5.
We show in this paper that for k63, every 3-connected, k-regular simple graph on at most
vertices is hamiltonian. 相似文献
6.
Let be a class of graphs on n vertices. For an integer c, let be the smallest integer such that if G is a graph in with more than edges, then G contains a cycle of length more than c. A classical result of Erdös and Gallai is that if is the class of all simple graphs on n vertices, then . The result is best possible when n-1 is divisible by c-1, in view of the graph consisting of copies of Kc all having exactly one vertex in common. Woodall improved the result by giving best possible bounds for the remaining cases when n-1 is not divisible by c-1, and conjectured that if is the class of all 2-connected simple graphs on n vertices, thenwhere , 2tc/2, is the number of edges in the graph obtained from Kc+1-t by adding n-(c+1-t) isolated vertices each joined to the same t vertices of Kc+1-t. By using a result of Woodall together with an edge-switching technique, we confirm Woodall's conjecture in this paper. 相似文献
7.
We show that the Hamiltonicity of a regular graph G can be fully characterized by the numbers of blocks of consecutive ones in the binary matrix A+I, where A is the adjacency matrix of G, I is the unit matrix, and the blocks can be either linear or circular. Concretely, a k-regular graph G with girth g(G)?5 has a Hamiltonian circuit if and only if the matrix A+I can be permuted on rows such that each column has at most (or exactly) k-1 circular blocks of consecutive ones; and if the graph G is k-regular except for two (k-1)-degree vertices a and b, then there is a Hamiltonian path from a to b if and only if the matrix A+I can be permuted on rows to have at most (or exactly) k-1 linear blocks per column.Then we turn to the problem of determining whether a given matrix can have at most k blocks of consecutive ones per column by some row permutation. For this problem, Booth and Lueker gave a linear algorithm for k=1 [Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, 1975, pp. 255-265]; Flammini et al. showed its NP-completeness for general k [Algorithmica 16 (1996) 549-568]; and Goldberg et al. proved the same for every fixed k?2 [J. Comput. Biol. 2 (1) (1995) 139-152]. In this paper, we strengthen their result by proving that the problem remains NP-complete for every constant k?2 even if the matrix is restricted to (1) symmetric, or (2) having at most three blocks per row. 相似文献
8.
Zhicheng Gao 《Journal of Graph Theory》1995,20(3):327-338
In a recent paper, Barnette showed that every 3-connected planar graph has a 2-connected spanning subgraph of maximum degree at most fifteen, he also constructed a planar triangulation that does not have 2-connected spanning subgraphs of maximum degree five. In this paper, we show that every 3-connected graph which is embeddable in the sphere, the projective plane, the torus or the Klein bottle has a 2-connected spanning subgraph of maximum degree at most six. © 1995 John Wiley & Sons, Inc. 相似文献
9.
10.
Guantao Chen Ralph J. Faudree Ronald J. Gould Michael S. Jacobson Linda Lesniak 《Graphs and Combinatorics》1995,11(3):221-231
One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graphG has orderp and minimum degree at least
thenG is hamiltonian. Moon and Moser showed that a balanced bipartite graph (the two partite sets have the same order)G has orderp and minimum degree more than
thenG is hamiltonian. In this paper, their idea is generalized tok-partite graphs and the following result is obtained: LetG be a balancedk-partite graph with orderp = kn. If the minimum degree
\left\{ {\begin{array}{*{20}c} {\left( {\frac{k}{2} - \frac{1}{{k + 1}}} \right)n if k is odd } \\ {\left( {\frac{k}{2} - \frac{2}{{k + 2}}} \right)n if k is even} \\ \end{array} } \right.$$
" align="middle" vspace="20%" border="0"> 相似文献
11.
R. C. Entringer 《Journal of Graph Theory》1978,2(4):319-327
A graph G is critically 2-connected if G is 2-connected but, for any point p of G, G — p is not 2-connected. Critically 2-connected graphs on n points that have the maximum number of lines are characterized and shown to be unique for n ? 3, n ≠ 11. 相似文献
12.
Ioan Tomescu 《Journal of Graph Theory》1994,18(4):329-336
In this paper we obtain chromatic polynomials P(G; λ) of 2-connected graphs of order n that are maximum for positive integer-valued arguments λ ≧ 3. The extremal graphs are cycles Cn and these graphs are unique for every λ ≧ 3 and n ≠ 5. We also determine max{P(G; λ): G is 2-connected of order n and G ≠ Cn} and all extremal graphs relative to this property, with some consequences on the maximum number of 3-colorings in the class of 2-connected graphs of order n having X(G) = 2 and X(G) = 3, respectively. For every n ≧ 5 and λ ≧ 4, the first three maximum chromatic polynomials of 2-connected graphs are determined. 相似文献
13.
A graph is reconstructible if it is determined up to isomorphism from the collection of all its one-vertex deleted unlabelled subgraphs. It is shown that all distance hereditary 2-connected graphs such that or are reconstructible. 相似文献
15.
A graph G has the hourglass property if every induced hourglass S (a tree with a degree sequence 22224) contains two non-adjacent vertices which have a common neighbor in G - V(S).For an integer k ≥ 4,... 相似文献
16.
A graph is called -connected if is -edge-connected and is -edge-connected for every vertex . The study of -connected graphs is motivated by a theorem of Thomassen [J. Combin. Theory Ser. A 110 (2015), pp. 67–78] (that was a conjecture of Frank [SIAM J. Discrete Math. 5 (1992), no. 1, pp. 25–53]), which states that a graph has a -vertex-connected orientation if and only if it is (2,2)-connected. In this paper, we provide a construction of the family of -connected graphs for even, which generalizes the construction given by Jordán [J. Graph Theory 52 (2006), pp. 217–229] for (2,2)-connected graphs. We also solve the corresponding connectivity augmentation problem: given a graph and an integer , what is the minimum number of edges to be added to make -connected. Both these results are based on a new splitting-off theorem for -connected graphs. 相似文献
17.
Let us fix a function f(n)=o(nlnn) and real numbers 0≤α<β≤1. We present a polynomial time algorithm which, given a directed graph G with n vertices, decides either that one can add at most βn new edges to G so that G acquires a Hamiltonian circuit or that one cannot add αn or fewer new edges to G so that G acquires at least e−f(n)n! Hamiltonian circuits, or both. 相似文献
18.
19.
|