共查询到20条相似文献,搜索用时 796 毫秒
1.
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 . 相似文献
2.
3.
4.
Zoltán Füredi Alexandr Kostochka Ruth Luo Jacques Verstraëte 《Discrete Mathematics》2018,341(5):1253-1263
The Erd?s–Gallai Theorem states that for , any -vertex graph with no cycle of length at least has at most edges. A stronger version of the Erd?s–Gallai Theorem was given by Kopylov: If is a 2-connected -vertex graph with no cycle of length at least , then , where . Furthermore, Kopylov presented the two possible extremal graphs, one with edges and one with edges.In this paper, we complete a stability theorem which strengthens Kopylov’s result. In particular, we show that for odd and all , every -vertex 2-connected graph with no cycle of length at least is a subgraph of one of the two extremal graphs or . The upper bound for here is tight. 相似文献
5.
6.
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. 相似文献
7.
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 . 相似文献
8.
The -power graph of a graph is a graph with the same vertex set as , in that two vertices are adjacent if and only if, there is a path between them in of length at most . A -tree-power graph is the -power graph of a tree, a -leaf-power graph is the subgraph of some -tree-power graph induced by the leaves of the tree.We show that (1) every -tree-power graph has NLC-width at most and clique-width at most , (2) every -leaf-power graph has NLC-width at most and clique-width at most , and (3) every -power graph of a graph of tree-width has NLC-width at most , and clique-width at most . 相似文献
9.
10.
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 . 相似文献
11.
Yehong Shao 《Discrete Mathematics》2018,341(12):3441-3446
Let be a graph and be its line graph. In 1969, Chartrand and Stewart proved that , where and denote the edge connectivity of and respectively. We show a similar relationship holds for the essential edge connectivity of and , written and , respectively. In this note, it is proved that if is not a complete graph and does not have a vertex of degree two, then . An immediate corollary is that for such graphs , where the vertex connectivity of the line graph
and the second iterated line graph are written as and respectively. 相似文献
12.
13.
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 相似文献
14.
15.
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). 相似文献
16.
Christoph Brause Arnfried Kemnitz Massimiliano Marangio Anja Pruchnewski Margit Voigt 《Discrete Mathematics》2017,340(11):2633-2640
Let be a simple graph and for every vertex let be a set (list) of available colors. is called -colorable if there is a proper coloring of the vertices with for all . A function is called a choice function of and is said to be -list colorable if is -colorable for every list assignment choice function is defined by and the sum choice number
denotes the minimum size of a choice function of .Sum list colorings were introduced by Isaak in 2002 and got a lot of attention since then.For a generalized
-graph is a simple graph consisting of two vertices and connected by internally vertex disjoint paths of lengths
.In 2014, Carraher et al. determined the sum-paintability of all generalized -graphs which is an online-version of the sum choice number and consequently an upper bound for it.In this paper we obtain sharp upper bounds for the sum choice number of all generalized -graphs with and characterize all generalized -graphs which attain the trivial upper bound . 相似文献
17.
Given a graph , let be the set of all cycle lengths contained in and let . Let and let be the greatest common divisor of and all the positive pairwise differences of elements in . We prove that if a Hamiltonian graph of order has at least edges, where is an integer such that , then or is exceptional, by which we mean for some . We also discuss cases where is not exceptional, for example when is prime. Moreover, we show that , which if is bipartite implies that , where is the number of edges in . 相似文献
18.
19.