Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNon-bipartite k-common graphs
119
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 Jagger, 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.
rate research
Read More
We study the problem of Minimum $k$-Critical Bipartite Graph of order $(n,m)$ - M$k$CBG-$(n,m)$: to find a bipartite $G=(U,V;E)$, with $|U|=n$, $|V|=m$, and $n>m>1$, which is $k$-critical bipartite, and the tuple $(|E|, Delta_U, Delta_V)$, where $Delta_U$ and $Delta_V$ denote the maximum degree in $U$ and $V$, respectively, is lexicographically minimum over all such graphs. $G$ is $k$-critical bipartite if deleting at most $k=n-m$ vertices from $U$ creates $G$ that has a complete matching, i.e., a matching of size $m$. We show that, if $m(n-m+1)/n$ is an integer, then a solution of the M$k$CBG-$(n,m)$ problem can be found among $(a,b)$-regular bipartite graphs of order $(n,m)$, with $a=m(n-m+1)/n$, and $b=n-m+1$. If $a=m-1$, then all $(a,b)$-regular bipartite graphs of order $(n,m)$ are $k$-critical bipartite. For $a<m-1$, it is not the case. We characterize the values of $n$, $m$, $a$, and $b$ that admit an $(a,b)$-regular bipartite graph of order $(n,m)$, with $b=n-m+1$, and give a simple construction that creates such a $k$-critical bipartite graph whenever possible. Our techniques are based on Halls marriage theorem, elementary number theory, linear Diophantine equations, properties of integer functions and congruences, and equations involving them.
In this paper, we classify the connected non-bipartite integral graphs with spectral radius three.
Let k, p, q be positive integers with k < p < q+1. We prove that the maximum spectral radius of a simple bipartite graph obtained from the complete bipartite graph Kp,q of bipartition orders p and q by deleting k edges is attained when the deleting edges are all incident on a common vertex which is located in the partite set of order q. Our method is based on new sharp upper bounds on the spectral radius of bipartite graphs in terms of their degree sequences.
A graph H is common if the number of monochromatic copies of H in a 2-edge-colouring of the complete graph is minimised by the random colouring. Burr and Rosta, extending a famous conjecture by Erdos, conjectured that every graph is common. The conjectures by Erdos and by Burr and Rosta were disproved by Thomason and by Sidorenko, respectively, in the late 1980s. Collecting new examples for common graphs had not seen much progress since then, although very recently, a few more graphs are verified to be common by the flag algebra method or the recent progress on Sidorenkos conjecture. Our contribution here is to give a new class of tripartite common graphs. The first example class is so-called triangle-trees, which generalises two theorems by Sidorenko and answers a question by Jagger, v{S}v{t}oviv{c}ek, and Thomason from 1996. We also prove that, somewhat surprisingly, given any tree T, there exists a triangle-tree such that the graph obtained by adding T as a pendant tree is still common. Furthermore, we show that adding arbitrarily many apex vertices to any connected bipartite graph on at most five vertices give a common graph.
A set of vertices X of a graph G is convex if it contains all vertices on shortest paths between vertices of X. We prove that for fixed p, all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
