Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinimizing the number of complete bipartite graphs in a $K_s$-saturated graph
109
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph $G$ is $F$-saturated if it contains no copy of $F$ as a subgraph but the addition of any new edge to $G$ creates a copy of $F$. We prove that for $s geq 3$ and $t geq 2$, the minimum number of copies of $K_{1,t}$ in a $K_s$-saturated graph is $Theta ( n^{t/2})$. More precise results are obtained when $t = 2$ where the problem is related to Moore graphs with diameter 2 and girth 5. We prove that for $s geq 4$ and $t geq 3$, the minimum number of copies of $K_{2,t}$ in an $n$-vertex $K_s$-saturated graph is at least $Omega( n^{t/5 + 8/5})$ and at most $O(n^{t/2 + 3/2})$. These results answer a question of Chakraborti and Loh. General estimates on the number of copies of $K_{a,b}$ in a $K_s$-saturated graph are also obtained, but finding an asymptotic formula remains open.
rate research
Read More
This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite graph $G$ is $H$-saturated if $G$ does not contain a subgraph isomorphic to $H$ but adding any missing edge to $G$ creates a copy of $H$. More than half a century ago, Wessel and Bollobas independently solved the problem of minimizing the number of edges in $K_{(s,t)}$-saturated graphs, where $K_{(s,t)}$ is the `ordered complete bipartite graph with $s$ vertices from the first color class and $t$ from the second. However, the very natural `unordered analogue of this problem was considered only half a decade ago by Moshkovitz and Shapira. When $s=t$, it can be easily checked that the unordered variant is exactly the same as the ordered case. Later, Gan, Korandi, and Sudakov gave an asymptotically tight bound on the minimum number of edges in $K_{s,t}$-saturated $n$ by $n$ bipartite graphs, which is only smaller than the conjecture of Moshkovitz and Shapira by an additive constant. In this paper, we confirm their conjecture for $s=t-1$ with the classification of the extremal graphs. We also improve the estimates of Gan, Korandi, and Sudakov for general $s$ and $t$, and for all sufficiently large $n$.
A $t$-bar visibility representation of a graph assigns each vertex up to $t$ horizontal bars in the plane so that two vertices are adjacent if and only if some bar for one vertex can see some bar for the other via an unobstructed vertical channel of positive width. The least $t$ such that $G$ has a $t$-bar visibility representation is the bar visibility number of $G$, denoted by $b(G)$. For the complete bipartite graph $K_{m,n}$, the lower bound $b(K_{m,n})gelceil{frac{mn+4}{2m+2n}}rceil$ from Eulers Formula is well known. We prove that equality holds.
Let $mathrm{rex}(n, F)$ denote the maximum number of edges in an $n$-vertex graph that is regular and does not contain $F$ as a subgraph. We give lower bounds on $mathrm{rex}(n, F)$, that are best possible up to a constant factor, when $F$ is one of $C_4$, $K_{2,t}$, $K_{3,3}$ or $K_{s,t}$ when $t>s!$.
Total dominator total coloring of a graph is a total coloring of the graph such that each object of the graph is adjacent or incident to every object of some color class. The minimum namber of the color classes of a total dominator total coloring of a graph is called the total dominator total chromatic number of the graph. Here, we will find the total dominator chromatic numbers of wheels, complete bipartite graphs and complete graphs.
The Hadwiger number $h(G)$ is the order of the largest complete minor in $G$. Does sufficient Hadwiger number imply a minor with additional properties? In [2], Geelen et al showed $h(G)geq (1+o(1))ctsqrt{ln t}$ implies $G$ has a bipartite subgraph with Hadwiger number at least $t$, for some explicit $csim 1.276dotsc$. We improve this to $h(G) geq (1+o(1))tsqrt{log_2 t}$, and provide a construction showing this is tight. We also derive improved bounds for the topological minor variant of this problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
