共查询到20条相似文献,搜索用时 31 毫秒
1.
Cory Palmer Michael Tait Craig Timmons Adam Zsolt Wagner 《Discrete Mathematics》2019,342(6):1553-1563
Let be a graph. We say that a hypergraph is a Berge- if there is a bijection such that for every . Note that Berge- actually denotes a class of hypergraphs. The maximum number of edges in an -vertex -graph with no subhypergraph isomorphic to any Berge- is denoted . In this paper, we investigate the case when and establish an upper-bound when , and a lower-bound when and is large enough compared to . Additionally, we prove a counting result for -graphs of girth five that complements the asymptotic formula of Lazebnik and Verstraëte (2003). 相似文献
2.
Given two graphs and , the maximum possible number of copies of in an -free graph on vertices is denoted by . We investigate the function , where denotes vertex disjoint copies of a fixed graph . Our results include cases when is a complete graph, cycle or a complete bipartite graph. 相似文献
3.
4.
5.
Given a simple graph with vertex set and edge set , the mixed graph is obtained from by orienting some of its edges. Let denote the Hermitian adjacency matrix of and be the adjacency matrix of . The -rank (resp. rank) of (resp. ), written as (resp. ), is the rank of (resp. ). Denote by the dimension of cycle space of , that is , where denotes the number of connected components of . In this paper, we concentrate on the relation between the -rank of and the rank of . We first show that for every mixed graph . Then we characterize all the mixed graphs that attain the above lower (resp. upper) bound. By these obtained results in the current paper, all the main results obtained in Luo et al. (2018); Wong et al. (2016) may be deduced consequently. 相似文献
6.
7.
8.
《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 . 相似文献
9.
A matching in a 3-uniform hypergraph is a set of pairwise disjoint edges. We use to denote the 3-uniform hypergraph whose vertex set can be partitioned into two vertex classes and of size and , respectively, and whose edge set consists of all the triples containing at least two vertices of . Let be a 3-uniform hypergraph of order with no isolated vertex and for any two adjacent vertices . In this paper, we show that contains a matching of size if and only if is not a subgraph of . This result improves our previous one in Zhang and Lu (2018). 相似文献
10.
《Discrete Mathematics》2022,345(1):112659
In a recent paper, Gerbner, Patkós, Tuza and Vizer studied regular F-saturated graphs. One of the essential questions is given F, for which n does a regular n-vertex F-saturated graph exist. They proved that for all sufficiently large n, there is a regular -saturated graph with n vertices. We extend this result to both and and prove some partial results for larger complete graphs. Using a variation of sum-free sets from additive combinatorics, we prove that for all , there is a regular -saturated with n vertices for infinitely many n. Studying the sum-free sets that give rise to -saturated graphs is an interesting problem on its own and we state an open problem in this direction. 相似文献
11.
The paper deals with panchromatic 3-colorings of random hypergraphs. A vertex 3-coloring is said to be panchromatic for a hypergraph if every color can be found on every edge. Let denote the binomial model of a random -uniform hypergraph on vertices. For given fixed , and , we prove that if then admits a panchromatic 3-coloring with probability tending to 1 as , but if is large enough and then does not admit a panchromatic 3-coloring with probability tending to 1 as . 相似文献
12.
13.
14.
15.
16.
17.
《Discrete Mathematics》2020,343(10):111996
A Gallai coloring of a complete graph is an edge coloring without triangles colored with three different colors. A sequence of positive integers is an -sequence if . An -sequence is a G-sequence if there is a Gallai coloring of with colors such that there are edges of color for all . Gyárfás, Pálvölgyi, Patkós and Wales proved that for any integer there exists an integer such that every -sequence is a G-sequence if and only if . They showed that and .We show that and give almost matching lower and upper bounds for by showing that with suitable constants , for all sufficiently large . 相似文献
18.