共查询到20条相似文献,搜索用时 62 毫秒
1.
2.
3.
Given a positive integer and a graph with degree sequence , we define . Caro and Yuster introduced a Turán-type problem for : Given a positive integer and a graph , determine the function , which is the maximum value of taken over all graphs on vertices that do not contain as a subgraph. Clearly, , where denotes the classical Turán number. Caro and Yuster determined the function for sufficiently large , where and denotes the path on vertices. In this paper, we generalise this result and determine for sufficiently large , where and is a linear forest. We also determine , where is a star forest; and , where is a broom graph with diameter at most six. 相似文献
4.
5.
Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs and , the -colored Gallai–Ramsey number is defined to be the minimum integer such that and for every , every rainbow -free coloring (using all colors) of the complete graph contains a monochromatic copy of . In this paper, we first provide some exact values and bounds of . Moreover, we define the -colored bipartite Gallai–Ramsey number as the minimum integer such that and for every , every rainbow -free coloring (using all colors) of the complete bipartite graph contains a monochromatic copy of . Furthermore, we describe the structures of complete bipartite graph with no rainbow and , respectively. Finally, we find the exact values of (), (where is a subgraph of ), and by using the structural results. 相似文献
6.
The tensor product of graphs , and is defined by and Let be the fractional chromatic number of a graph . In this paper, we prove that if one of the three graphs , and is a circular clique, 相似文献
7.
《Discrete Mathematics》2020,343(2):111679
A path in an edge-colored graph is called monochromatic if any two edges on the path have the same color. For , an edge-colored graph is said to be monochromatic -edge-connected if every two distinct vertices of are connected by at least edge-disjoint monochromatic paths, and is said to be uniformly monochromatic -edge-connected if every two distinct vertices are connected by at least edge-disjoint monochromatic paths such that all edges of these paths are colored with a same color. We use and to denote the maximum number of colors that ensures to be monochromatic -edge-connected and, respectively, to be uniformly monochromatic -edge-connected. In this paper, we first conjecture that for any -edge-connected graph , , where is a minimum -edge-connected spanning subgraph of . We verify the conjecture for . We also prove the conjecture for and with . When is a minimal -edge-connected graph, we give an upper bound of , i.e., . For the uniformly monochromatic -edge-connectivity, we prove that for all , , where is a minimum -edge-connected spanning subgraph of . 相似文献
8.
9.
10.
11.
Christian Bosse 《Discrete Mathematics》2019,342(12):111595
The Hadwiger number of a graph , denoted , is the largest integer such that contains as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph , , where denotes the chromatic number of . Let denote the independence number of . A graph is -free if it does not contain the graph as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that for all -free graphs with , where is any graph on four vertices with , , or is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs on five vertices with . In this note, we prove that for all -free graphs with , where denotes the wheel on six vertices. 相似文献
12.
13.
14.
《Discrete Mathematics》2022,345(8):112903
Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number is the least integer k for which G admits a coloring with k colors such that each color class induces a -degenerate subgraph of G. So is the chromatic number and is the point arboricity. The point partition number with was introduced by Lick and White. A graph G is called -critical if every proper subgraph H of G satisfies . In this paper we prove that if G is a -critical graph whose order satisfies , then G can be obtained from two non-empty disjoint subgraphs and by adding t edges between any pair of vertices with and . Based on this result we establish the minimum number of edges possible in a -critical graph G of order n and with , provided that and t is even. For the corresponding two results were obtained in 1963 by Tibor Gallai. 相似文献
15.
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. 相似文献
16.
Julia Semikina 《Journal of Pure and Applied Algebra》2019,223(10):4509-4523
I. Hambleton, L. Taylor and B. Williams conjectured a general formula in the spirit of H. Lenstra for the decomposition of for any finite group G and noetherian ring R. The conjectured decomposition was shown to hold for some large classes of finite groups. D. Webb and D. Yao discovered that the conjecture failed for the symmetric group , but remarked that it still might be reasonable to expect the HTW-decomposition for solvable groups. In this paper we show that the solvable group is also a counterexample to the conjectured HTW-decomposition. Nevertheless, we prove that for any finite group G the rank of does not exceed the rank of the expression in the HTW-decomposition. We also show that the HTW-decomposition predicts correct torsion for for any finite group G. Furthermore, we prove that for any degree other than the conjecture gives a correct prediction for the rank of . 相似文献
17.
In this paper we consider the relation between the spectrum and the number of short cycles in large graphs. Suppose is a sequence of finite and connected graphs that share a common universal cover and such that the proportion of eigenvalues of that lie within the support of the spectrum of tends to 1 in the large limit. This is a weak notion of being Ramanujan. We prove such a sequence of graphs is asymptotically locally tree-like. This is deduced by way of an analogous theorem proved for certain infinite sofic graphs and unimodular networks, which extends results for regular graphs and certain infinite Cayley graphs. 相似文献
18.
19.
Let be a weighted digraph with vertex set and arc set , where the arc weights are nonzero nonnegative symmetric matrices. In this paper, we obtain an upper bound on the signless Laplacian spectral radius of a weighted digraph , and if is strongly connected, we also characterize the digraphs achieving the upper bound. Moreover, we show that an upper bound of weighted digraphs or unweighted digraphs can be deduced from our upper bound. 相似文献