共查询到20条相似文献,搜索用时 187 毫秒
1.
Bojan Vučković 《Discrete Mathematics》2018,341(5):1472-1478
An adjacent vertex distinguishing total -coloring of a graph is a proper total -coloring of such that any pair of adjacent vertices have different sets of colors. The minimum number needed for such a total coloring of is denoted by . In this paper we prove that if , and in general. This improves a result in Huang et al. (2012) which states that for any graph with . 相似文献
2.
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. 相似文献
3.
A graph is packable if it is a subgraph of its complement. The following statement was conjectured by Faudree, Rousseau, Schelp and Schuster in 1981: every non-star graph with girth at least is packable.The conjecture was proved by Faudree et al. with the additional condition that has at most edges. In this paper, for each integer , we prove that every non-star graph with girth at least and at most edges is packable, where is for every . This implies that the conjecture is true for sufficiently large planar graphs. 相似文献
4.
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). 相似文献
5.
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 . 相似文献
6.
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 . 相似文献
7.
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. 相似文献
8.
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 . 相似文献
9.
A conjecture of Gyárfás and Sárközy says that in every -coloring of the edges of the complete -uniform hypergraph , there are two disjoint monochromatic loose paths of distinct colors such that they cover all but at most vertices. A weaker form of this conjecture with uncovered vertices instead of is proved. Thus the conjecture holds for . The main result of this paper states that the conjecture is true for all . 相似文献
10.
The neighbor-distinguishing total chromatic number of a graph is the smallest integer such that can be totally colored using colors with a condition that any two adjacent vertices have different sets of colors. In this paper, we give a sufficient and necessary condition for a planar graph with maximum degree 13 to have or . Precisely, we show that if is a planar graph of maximum degree 13, then ; and if and only if contains two adjacent 13-vertices. 相似文献
11.
In 1962, Erd?s proved that if a graph with vertices satisfies where the minimum degree and , then it is Hamiltonian. For , let , where “” is the “join” operation. One can observe and is not Hamiltonian. As contains induced claws for , a natural question is to characterize all 2-connected claw-free non-Hamiltonian graphs with the largest possible number of edges. We answer this question completely by proving a claw-free analog of Erd?s’ theorem. Moreover, as byproducts, we establish several tight spectral conditions for a 2-connected claw-free graph to be Hamiltonian. Similar results for the traceability of connected claw-free graphs are also obtained. Our tools include Ryjá?ek’s claw-free closure theory and Brousek’s characterization of minimal 2-connected claw-free non-Hamiltonian graphs. 相似文献
12.
13.
Dong Ye 《Discrete Mathematics》2018,341(5):1195-1198
It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph with has a maximum matching such that any two -unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for -regular graphs with . All counterexamples for -regular graphs given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all -regular simple graphs and also -regular multigraphs with . 相似文献
14.
A star edge-coloring of a graph is a proper edge coloring such that every 2-colored connected subgraph of is a path of length at most 3. For a graph , let the list star chromatic index of , , be the minimum such that for any -uniform list assignment for the set of edges, has a star edge-coloring from . Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph is less than (resp. 3), then (resp. ). 相似文献
15.
16.
Given , the Fox–Kleitman conjecture from 2006 states that there exists a nonzero integer such that the -variable linear Diophantine equation is -regular. This is best possible, since Fox and Kleitman showed that for all , this equation is not -regular. While the conjecture has recently been settled for all , here we focus on the case and determine the degree of regularity of the corresponding equation for all . In particular, this independently confirms the conjecture for . We also briefly discuss the case . 相似文献
17.
Let G be a graph with n vertices and edges, and let be the Laplacian eigenvalues of G. Let , where . Brouwer conjectured that for . It has been shown in Haemers et al. [7] that the conjecture is true for trees. We give upper bounds for , and in particular, we show that the conjecture is true for unicyclic and bicyclic graphs. 相似文献
18.
19.
A strong -edge-coloring of a graph G is an edge-coloring with colors in which every color class is an induced matching. The strong chromatic index of , denoted by , is the minimum for which has a strong -edge-coloring. In 1985, Erd?s and Ne?et?il conjectured that , where is the maximum degree of . When is a graph with maximum degree at most 3, the conjecture was verified independently by Andersen and Horák, Qing, and Trotter. In this paper, we consider the list version of strong edge-coloring. In particular, we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10. 相似文献
20.
Daniel W. Cranston William B. Kinnersley Suil O Douglas B. West 《Discrete Applied Mathematics》2013,161(13-14):1828-1836