共查询到20条相似文献,搜索用时 62 毫秒
1.
Let be an integer and be a graph. Let denote the graph obtained from by replacing each edge of with parallel edges. We say that has all -factors or all fractional -factors if has an -factor or a fractional -factor for every function with even. In this note, we come up with simple characterizations of a graph such that has all -factors or all fractional -factors. These characterizations are extensions of Tutte’s 1-Factor Theorem and Tutte’s Fractional 1-Factor Theorem. 相似文献
2.
Let be a simple connected graph with vertices and edges. The spectral radius of is the largest eigenvalue of its adjacency matrix. In this paper, we firstly consider the effect on the spectral radius of a graph by removing a vertex, and then as an application of the result, we obtain a new sharp upper bound of which improves some known bounds: If , where is an integer, then The equality holds if and only if is a complete graph or , where is the graph obtained from by deleting some edge . 相似文献
3.
Let be a simple graph, and let , and denote the maximum degree, the average degree and the chromatic index of , respectively. We called edge--critical if and for every proper subgraph of . Vizing in 1968 conjectured that if is an edge--critical graph of order , then . We prove that for any edge--critical graph , that is, This result improves the best known bound obtained by Woodall in 2007 for . 相似文献
4.
5.
《Discrete Mathematics》2021,344(12):112604
A well-known theorem of Vizing states that if G is a simple graph with maximum degree Δ, then the chromatic index of G is Δ or . A graph G is class 1 if , and class 2 if ; G is Δ-critical if it is connected, class 2 and for every . A long-standing conjecture of Vizing from 1968 states that every Δ-critical graph on n vertices has at least edges. We initiate the study of determining the minimum number of edges of class 1 graphs G, in addition, for every . Such graphs have intimate relation to -co-critical graphs, where a non-complete graph G is -co-critical if there exists a k-coloring of such that G does not contain a monochromatic copy of but every k-coloring of contains a monochromatic copy of for every . We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all -co-critical graphs. We prove that if G is a -co-critical graph on vertices, then where ε is the remainder of when divided by 2. This bound is best possible for all and . 相似文献
6.
For a graph , the -dominating graph of has vertices corresponding to the dominating sets of having cardinality at most , where two vertices of are adjacent if and only if the dominating set corresponding to one of the vertices can be obtained from the dominating set corresponding to the second vertex by the addition or deletion of a single vertex. We denote the domination and upper domination numbers of by and , respectively, and the smallest integer for which is connected for all by . It is known that , but constructing a graph such that appears to be difficult.We present two related constructions. The first construction shows that for each integer and each integer such that , there exists a graph such that , and . The second construction shows that for each integer and each integer such that , there exists a graph such that , and . 相似文献
7.
《Discrete Mathematics》2020,343(6):111712
The weak -coloring numbers of a graph were introduced by the first two authors as a generalization of the usual coloring number , and have since found interesting theoretical and algorithmic applications. This has motivated researchers to establish strong bounds on these parameters for various classes of graphs.Let denote the th power of . We show that, all integers and and graphs with satisfy ; for fixed tree width or fixed genus the ratio between this upper bound and worst case lower bounds is polynomial in . For the square of graphs , we also show that, if the maximum average degree , then . 相似文献
8.
9.
Kiyoshi Ando 《Discrete Mathematics》2019,342(12):111598
An edge of a -connected graph is said to be -contractible if the contraction of the edge results in a -connected graph. For a graph and a vertex of , let be the subgraph induced by the neighborhood of . We prove that if has less than edges for any vertex of a -connected graph , then has a -contractible edge. We also show that the bound is sharp. 相似文献
10.
11.
12.
《Discrete Mathematics》2020,343(12):112117
Let be an edge-colored graph of order . The minimum color degree of , denoted by , is the largest integer such that for every vertex , there are at least distinct colors on edges incident to . We say that an edge-colored graph is rainbow if all its edges have different colors. In this paper, we consider vertex-disjoint rainbow triangles in edge-colored graphs. Li (2013) showed that if , then contains a rainbow triangle and the lower bound is tight. Motivated by this result, we prove that if and , then contains two vertex-disjoint rainbow triangles. In particular, we conjecture that if , then contains vertex-disjoint rainbow triangles. For any integer , we show that if and , then contains vertex-disjoint rainbow triangles. Moreover, we provide sufficient conditions for the existence of edge-disjoint rainbow triangles. 相似文献
13.
14.
15.
《Discrete Mathematics》2022,345(12):113082
Let G be a graph of order n with an edge-coloring c, and let denote the minimum color-degree of G. A subgraph F of G is called rainbow if all edges of F have pairwise distinct colors. There have been a lot of results on rainbow cycles of edge-colored graphs. In this paper, we show that (i) if , then every vertex of G is contained in a rainbow triangle; (ii) if and , then every vertex of G is contained in a rainbow ; (iii) if G is complete, and , then G contains a rainbow cycle of length at least k, where . 相似文献
16.
A -list assignment of a graph is a mapping that assigns to each vertex a list of at least colors satisfying for each edge . A graph is -choosable if there exists an -coloring of for every -list assignment . This concept is also known as choosability with separation. In this paper, we prove that any planar graph is -choosable if any -cycle is not adjacent to a -cycle, where and . 相似文献
17.
18.
19.
20.
In 2009, Kyaw proved that every -vertex connected -free graph with contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected -free graphs. We show that every -vertex connected -free graph with contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “” is best possible. 相似文献