共查询到20条相似文献,搜索用时 31 毫秒
1.
Smallest domination number and largest independence number of graphs and forests with given degree sequence
下载免费PDF全文
![点击此处可从《Journal of Graph Theory》网站下载免费的PDF全文](/ch/ext_images/free.gif)
《Journal of Graph Theory》2018,88(1):131-145
For a sequence d of nonnegative integers, let and be the sets of all graphs and forests with degree sequence d, respectively. Let , , , and where is the domination number and is the independence number of a graph G. Adapting results of Havel and Hakimi, Rao showed in 1979 that can be determined in polynomial time. We establish the existence of realizations with , and with and that have strong structural properties. This leads to an efficient algorithm to determine for every given degree sequence d with bounded entries as well as closed formulas for and . 相似文献
2.
Thomassen proved that every ‐connected graph G contains an induced cycle C such that is k‐connected, establishing a conjecture of Lovász. In general, one could ask the following question: For any positive integers , does there exist a smallest positive integer such that for any ‐connected graph G, any with , and any , there is an induced cycle C in such that and is l‐connected? The case when is a well‐known conjecture of Lovász that is still open for . In this article, we prove and . We also consider a weaker version: For any positive integers , is there a smallest positive integer such that for every ‐connected graph G and any with , there is an induced cycle C in such that is l‐connected? The case when was studied by Thomassen. We prove and . 相似文献
3.
Let and denote the second largest eigenvalue and the maximum number of edge‐disjoint spanning trees of a graph G, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and bounds of , Cioab? and Wong conjectured that for any integers and a d‐regular graph G, if , then . They proved the conjecture for , and presented evidence for the cases when . Thus the conjecture remains open for . We propose a more general conjecture that for a graph G with minimum degree , if , then . In this article, we prove that for a graph G with minimum degree δ, each of the following holds.
- (i) For , if and , then .
- (ii) For , if and , then .
4.
Stephan Brandt Felix Joos Janina Müttel Dieter Rautenbach 《Journal of Graph Theory》2013,74(2):210-215
Let denote the set of lengths of cycles of a graph G of order n and let denote the complement of G. We show that if , then contains all odd ? with and all even ? with , where and denote the maximum odd and the maximum even integer in , respectively. From this we deduce that the set contains at least integers, which is sharp. 相似文献
5.
《Journal of Graph Theory》2018,87(3):305-316
For a finite set V and a positive integer k with , letting be the set of all k‐subsets of V, the pair is called the complete k‐hypergraph on V, while each k‐subset of V is called an edge. A factorization of the complete k‐hypergraph of index , simply a ‐factorization of order n, is a partition of the edges into s disjoint subsets such that each k‐hypergraph , called a factor, is a spanning subhypergraph of . Such a factorization is homogeneous if there exist two transitive subgroups G and M of the symmetric group of degree n such that G induces a transitive action on the set and M lies in the kernel of this action. In this article, we give a classification of homogeneous factorizations of that admit a group acting transitively on the edges of . It is shown that, for and , there exists an edge‐transitive homogeneous ‐factorization of order n if and only if is one of (32, 3, 5), (32, 3, 31), (33, 4, 5), , and , where and q is a prime power with . 相似文献
6.
《Journal of Graph Theory》2018,89(3):327-340
In this article, we are concerned with sufficient conditions for the existence of a ‐factor. We prove that for , there exists such that if a graph G satisfies for all , then G has a ‐factor, where is the number of components C of with . On the other hand, we construct infinitely many graphs G having no ‐factor such that for all . 相似文献
7.
Král' and Sgall (J Graph Theory 49(3) (2005), 177–186) introduced a refinement of list coloring where every color list must be subset to one predetermined palette of colors. We call this ‐choosability when the palette is of size at most ? and the lists must be of size at least k . They showed that, for any integer , there is an integer , satisfying as , such that, if a graph is ‐choosable, then it is C‐choosable, and asked if C is required to be exponential in k . We demonstrate it must satisfy . For an integer , if is the least integer such that a graph is ‐choosable if it is ‐choosable, then we more generally supply a lower bound on , one that is super‐polynomial in k if , by relation to an extremal set theoretic property. By the use of containers, we also give upper bounds on that improve on earlier bounds if . 相似文献
8.
Klas Markström 《Journal of Graph Theory》2014,76(2):101-105
For ordinary graphs it is known that any graph G with more edges than the Turán number of must contain several copies of , and a copy of , the complete graph on vertices with one missing edge. Erd?s asked if the same result is true for , the complete 3‐uniform hypergraph on s vertices. In this note, we show that for small values of n, the number of vertices in G, the answer is negative for . For the second property, that of containing a , we show that for the answer is negative for all large n as well, by proving that the Turán density of is greater than that of . 相似文献
9.
Jan van den Heuvel Daniel Král' Martin Kupec Jean‐Sébastien Sereni Jan Volec 《Journal of Graph Theory》2014,77(4):299-329
We study the following problem: given a real number k and an integer d, what is the smallest ε such that any fractional ‐precoloring of vertices at pairwise distances at least d of a fractionally k‐colorable graph can be extended to a fractional ‐coloring of the whole graph? The exact values of ε were known for and any d. We determine the exact values of ε for if , and if , and give upper bounds for if , and if . Surprisingly, ε viewed as a function of k is discontinuous for all those values of d. 相似文献
10.
《Journal of Graph Theory》2018,87(1):96-107
We generalize an unpublished result of C. Thomassen. Let be a digraph and let be a multiset of subsets of V in such a way that any backward‐infinite path in D meets all the sets . We show that if all is simultaneously reachable from the sets by edge‐disjoint paths, then there exists a system of edge‐disjoint spanning branchings in D where the root‐set of is . 相似文献
11.
Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles
下载免费PDF全文
![点击此处可从《Journal of Graph Theory》网站下载免费的PDF全文](/ch/ext_images/free.gif)
《Journal of Graph Theory》2018,87(4):660-671
If G is a graph and is a set of subgraphs of G, then an edge‐coloring of G is called ‐polychromatic if every graph from gets all colors present in G. The ‐polychromatic number of G, denoted , is the largest number of colors such that G has an ‐polychromatic coloring. In this article, is determined exactly when G is a complete graph and is the family of all 1‐factors. In addition is found up to an additive constant term when G is a complete graph and is the family of all 2‐factors, or the family of all Hamiltonian cycles. 相似文献
12.
For a graph , let denote the minimum number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to exactly one of them. It is easy to see that for every graph G , , where is the maximum size of an independent set of G . Erd?s conjectured in the 80s that for almost every graph G equality holds, that is that for the random graph , with high probability, that is with probability that tends to 1 as n tends to infinity. The first author showed that this is slightly false, proving that for most values of n tending to infinity and for , with high probability. We prove a stronger bound: there exists an absolute constant so that with high probability. 相似文献
13.
《Journal of Graph Theory》2018,88(3):411-427
Let be a graph of density p on n vertices. Following Erdős, Łuczak, and Spencer, an m‐vertex subgraph H of G is called full if H has minimum degree at least . Let denote the order of a largest full subgraph of G. If is a nonnegative integer, define Erdős, Łuczak, and Spencer proved that for , In this article, we prove the following lower bound: for , Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely many p near the elements of . In contrast, we show that for any n‐vertex graph G, either G or contains a full subgraph on vertices. Finally, we discuss full subgraphs of random and pseudo‐random graphs, and several open problems. 相似文献
14.
Alexey Pokrovskiy 《Journal of Graph Theory》2017,84(4):477-500
In this article we prove a new result about partitioning colored complete graphs and use it to determine certain Ramsey numbers exactly. The partitioning theorem we prove is that for , in every edge coloring of with the colors red and blue, it is possible to cover all the vertices with k disjoint red paths and a disjoint blue balanced complete ‐partite graph. When the coloring of is connected in red, we prove a stronger result—that it is possible to cover all the vertices with k red paths and a blue balanced complete ‐partite graph. Using these results we determine the Ramsey number of an n‐vertex path, , versus a balanced complete t‐partite graph on vertices, , whenever . We show that in this case , generalizing a result of Erd?s who proved the case of this result. We also determine the Ramsey number of a path versus the power of a path . We show that , solving a conjecture of Allen, Brightwell, and Skokan. 相似文献
15.
We study minimum degree conditions for which a graph with given odd girth has a simple structure. For example, the classical work of Andrásfai, Erd?s, and Sós implies that every n‐vertex graph with odd girth and minimum degree bigger than must be bipartite. We consider graphs with a weaker condition on the minimum degree. Generalizing results of Häggkvist and of Häggkvist and Jin for the cases and 3, we show that every n‐vertex graph with odd girth and minimum degree bigger than is homomorphic to the cycle of length . This is best possible in the sense that there are graphs with minimum degree and odd girth that are not homomorphic to the cycle of length . Similar results were obtained by Brandt and Ribe‐Baumann. 相似文献
16.
Michael Stiebitz 《Journal of Graph Theory》2017,85(1):278-287
The Erd?s–Lovász Tihany conjecture asserts that every graph G with ) contains two vertex disjoint subgraphs G 1 and G 2 such that and . Under the same assumption on G , we show that there are two vertex disjoint subgraphs G 1 and G 2 of G such that (a) and or (b) and . Here, is the chromatic number of is the clique number of G , and col(G ) is the coloring number of G . 相似文献
17.
Let be an integer, be the set of vertices of degree at least 2k in a graph G , and be the set of vertices of degree at most in G . In 1963, Dirac and Erd?s proved that G contains k (vertex) disjoint cycles whenever . The main result of this article is that for , every graph G with containing at most t disjoint triangles and with contains k disjoint cycles. This yields that if and , then G contains k disjoint cycles. This generalizes the Corrádi–Hajnal Theorem, which states that every graph G with and contains k disjoint cycles. 相似文献
18.
19.
《Journal of Graph Theory》2018,88(2):294-301
Suppose is a loopless graph and is the graph obtained from G by subdividing each of its edges k () times. Let be the set of all spanning trees of G, be the line graph of the graph and be the number of spanning trees of . By using techniques from electrical networks, we first obtain the following simple formula: Then we find it is in fact equivalent to a complicated formula obtained recently using combinatorial techniques in [F. M. Dong and W. G. Yan, Expression for the number of spanning trees of line graphs of arbitrary connected graphs, J. Graph Theory. 85 (2017) 74–93]. 相似文献
20.
A coloring of the edges of a graph G is strong if each color class is an induced matching of G. The strong chromatic index of G, denoted by , is the least number of colors in a strong edge coloring of G. Chang and Narayanan (J Graph Theory 73(2) (2013), 119–126) proved recently that for a 2‐degenerate graph G. They also conjectured that for any k‐degenerate graph G there is a linear bound , where c is an absolute constant. This conjecture is confirmed by the following three papers: in (G. Yu, Graphs Combin 31 (2015), 1815–1818), Yu showed that . In (M. Debski, J. Grytczuk, M. Sleszynska‐Nowak, Inf Process Lett 115(2) (2015), 326–330), D?bski, Grytczuk, and ?leszyńska‐Nowak showed that . In (T. Wang, Discrete Math 330(6) (2014), 17–19), Wang proved that . If G is a partial k‐tree, in (M. Debski, J. Grytczuk, M. Sleszynska‐Nowak, Inf Process Lett 115(2) (2015), 326–330), it is proven that . Let be the line graph of a graph G, and let be the square of the line graph . Then . We prove that if a graph G has an orientation with maximum out‐degree k, then has coloring number at most . If G is a k‐tree, then has coloring number at most . As a consequence, a graph with has , and a k‐tree G has . 相似文献