Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSubdivisions of vertex-disjoint cycles in bipartite graphs
194
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $ngeq 6,kgeq 0$ be two integers. Let $H$ be a graph of order $n$ with $k$ components, each of which is an even cycle of length at least $6$ and $G$ be a bipartite graph with bipartition $(X,Y)$ such that $|X|=|Y|geq n/2$. In this paper, we show that if the minimum degree of $G$ is at least $n/2-k+1$, then $G$ contains a subdivision of $H$. This generalized an older result of Wang.
rate research
Read More
Lovasz (1965) characterized graphs without two vertex-disjoint cycles, which implies that such graphs have at most three vertices hitting all cycles. In this paper, we ask whether such a small hitting set exists for $S$-cycles, when a graph has no two vertex-disjoint $S$-cycles. For a graph $G$ and a vertex set $S$ of $G$, an $S$-cycle is a cycle containing a vertex of $S$. We provide an example $G$ on $21$ vertices where $G$ has no two vertex-disjoint $S$-cycles, but three vertices are not sufficient to hit all $S$-cycles. On the other hand, we show that four vertices are enough to hit all $S$-cycles whenever a graph has no two vertex-disjoint $S$-cycles.
Let $k$ be a positive integer. Let $G$ be a balanced bipartite graph of order $2n$ with bipartition $(X, Y)$, and $S$ a subset of $X$. Suppose that every pair of nonadjacent vertices $(x,y)$ with $xin S, yin Y$ satisfies $d(x)+d(y)geq n+1$. We show that if $|S|geq 2k+2$, then $G$ contains $k$ disjoint cycles covering $S$ such that each of the $k$ cycles contains at least two vertices of $S$. Here, both the degree condition and the lower bound of $|S|$ are best possible. And we also show that if $|S|=2k+1$, then $G$ contains $k$ disjoint cycles such that each of the $k$ cycles contains at least two vertices of $S$.
It is conjectured that every edge-colored complete graph $G$ on $n$ vertices satisfying $Delta^{mon}(G)leq n-3k+1$ contains $k$ vertex-disjoint properly edge-colored cycles. We confirm this conjecture for $k=2$, prove several additional weaker results for general $k$, and we establish structural properties of possible minimum counterexamples to the conjecture. We also reveal a close relationship between properly edge-colored cycles in edge-colored complete graphs and directed cycles in multi-partite tournaments. Using this relationship and our results on edge-colored complete graphs, we obtain several partial solutions to a conjecture on disjoint cycles in directed graphs due to Bermond and Thomassen.
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.
Let the bipartite Turan number $ex(m,n,H)$ of a graph $H$ be the maximum number of edges in an $H$-free bipartite graph with two parts of sizes $m$ and $n$, respectively. In this paper, we prove that $ex(m,n,C_{2t})=(t-1)n+m-t+1$ for any positive integers $m,n,t$ with $ngeq mgeq tgeq frac{m}{2}+1$. This confirms the rest of a conjecture of Gy{o}ri cite{G97} (in a stronger form), and improves the upper bound of $ex(m,n,C_{2t})$ obtained by Jiang and Ma cite{JM18} for this range. We also prove a tight edge condition for consecutive even cycles in bipartite graphs, which settles a conjecture in cite{A09}. As a main tool, for a longest cycle $C$ in a bipartite graph, we obtain an estimate on the upper bound of the number of edges which are incident to at most one vertex in $C$. Our two results generalize or sharpen a classical theorem due to Jackson cite{J85} in different ways.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
