اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMore non-bipartite forcing pairs
85
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We study pairs of graphs (H_1,H_2) such that every graph with the densities of H_1 and H_2 close to the densities of H_1 and H_2 in a random graph is quasirandom; such pairs (H_1,H_2) are called forcing. Non-bipartite forcing pairs were first discovered by Conlon, Han, Person and Schacht [Weak quasi-randomness for uniform hypergraphs, Random Structures Algorithms 40 (2012), 1-38]: they showed that (K_t,F) is forcing where F is the graph that arises from K_t by iteratively doubling its vertices and edges in a prescribed way t times. Reiher and Schacht [Forcing quasirandomness with triangles, Forum of Mathematics, Sigma 7, 2019] strengthened this result for t=3 by proving that two doublings suffice and asked for the minimum number of doublings needed for t>3. We show that (t+2)/2 doublings always suffice.
قيم البحث
اقرأ أيضاً
A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of K_n is asymptotically minimized by a random coloring. For every k, we construct a connected non-bipartite k-common graph. This resolves a problem raised by Jagge
r, Stovicek and Thomason [Combinatorica 16 (1996), 123-141]. We also show that a graph H is k-common for every k if and only if H is Sidorenko and that H is locally k-common for every k if and only if H is locally Sidorenko.
In this paper, we classify the connected non-bipartite integral graphs with spectral radius three.
The global forcing number of a graph G is the minimal cardinality of an edge subset discriminating all perfect matchings of G, denoted by gf(G). For any perfect matching M of G, the minimal cardinality of an edge subset S in E(G)-M such that G-S has
a unique perfect matching is called the anti-forcing number of M,denoted by af(G, M). The maximum anti-forcing number of G among all perfect matchings is denoted by Af(G). It is known that the maximum anti-forcing number of a hexagonal system equals the famous Fries number. We are interested in some comparisons between the global forcing number and the maximum anti-forcing number of a graph. For a bipartite graph G, we show that gf(G)is larger than or equal to Af(G). Next we mainly extend such result to non-bipartite graphs, which is the set of all graphs with a perfect matching which contain no two disjoint odd cycles such that their deletion results in a subgraph with a perfect matching. For any such graph G, we also have gf(G) is larger than or equal to Af(G) by revealing further property of non-bipartite graphs with a unique perfect matching. As a consequence, this relation also holds for the graphs whose perfect matching polytopes consist of non-negative 1-regular vectors. In particular, for a brick G, de Carvalho, Lucchesi and Murty [4] showed that G satisfying the above condition if and only if G is solid, and if and only if its perfect matching polytope consists of non-negative 1-regular vectors. Finally, we obtain tight upper and lower bounds on gf(G)-Af(G). For a connected bipartite graph G with 2n vertices, we have that 0 leq gf(G)-Af(G) leq 1/2 (n-1)(n-2); For non-bipartite case, -1/2 (n^2-n-2) leq gf(G)-Af(G) leq (n-1)(n-2).
Zero forcing is a combinatorial game played on a graph with a goal of turning all of the vertices of the graph black while having to use as few unforced moves as possible. This leads to a parameter known as the zero forcing number which can be used t
o give an upper bound for the maximum nullity of a matrix associated with the graph. We introduce a new variation on the zero forcing game which can be used to give an upper bound for the maximum nullity of a matrix associated with a graph that has $q$ negative eigenvalues. This gives some limits to the number of positive eigenvalues that such a graph can have and so can be used to form lower bounds for the inertia set of a graph.
Let $G=(V,E)$ be a finite connected graph along with a coloring of the vertices of $G$ using the colors in a given set $X$. In this paper, we introduce multi-color forcing, a generalization of zero-forcing on graphs, and give conditions in which the
multi-color forcing process terminates regardless of the number of colors used. We give an upper bound on the number of steps required to terminate a forcing procedure in terms of the number of vertices in the graph on which the procedure is being applied. We then focus on multi-color forcing with three colors and analyze the end states of certain families of graphs, including complete graphs, complete bipartite graphs, and paths, based on various initial colorings. We end with a few directions for future research.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
