Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new user$Z_2times Z_2$-cordial cycle-free hypergraphs
208
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Hovey introduced $A$-cordial labelings as a generalization of cordial and harmonious labelings cite{Hovey}. If $A$ is an Abelian group, then a labeling $f colon V (G) rightarrow A$ of the vertices of some graph $G$ induces an edge labeling on $G$, the edge $uv$ receives the label $f (u) + f (v)$. A graph $G$ is $A$-cordial if there is a vertex-labeling such that (1) the vertex label classes differ in size by at most one and (2) the induced edge label classes differ in size by at most one. The problem of $A$-cordial labelings of graphs can be naturally extended for hypergraphs. It was shown that not every $2$-uniform hypertree (i.e., tree) admits a $Z_2times Z_2$-cordial labeling cite{Pechnik}. The situation changes if we consider $p$-uniform hypetrees for a bigger $p$. We prove that a $p$-uniform hypertree is $Z_2times Z_2$-cordial for any $p>2$, and so is every path hypergraph in which all edges have size at least~3. The property is not valid universally in the class of hypergraphs of maximum degree~1, for which we provide a necessary and sufficient condition.
rate research
Read More
We prove that for any integer $kgeq 2$ and $varepsilon>0$, there is an integer $ell_0geq 1$ such that any $k$-uniform hypergraph on $n$ vertices with minimum codegree at least $(1/2+varepsilon)n$ has a fractional decomposition into tight cycles of length $ell$ ($ell$-cycles for short) whenever $ellgeq ell_0$ and $n$ is large in terms of $ell$. This is essentially tight. This immediately yields also approximate integral decompositions for these hypergraphs into $ell$-cycles. Moreover, for graphs this even guarantees integral decompositions into $ell$-cycles and solves a problem posed by Glock, Kuhn and Osthus. For our proof, we introduce a new method for finding a set of $ell$-cycles such that every edge is contained in roughly the same number of $ell$-cycles from this set by exploiting that certain Markov chains are rapidly mixing.
In this paper we show that the maximum number of hyperedges in a $3$-uniform hypergraph on $n$ vertices without a (Berge) cycle of length five is less than $(0.254 + o(1))n^{3/2}$, improving an estimate of Bollobas and GyH{o}ri. We obtain this result by showing that not many $3$-paths can start from certain subgraphs of the shadow.
In this note we show that the maximum number of edges in a $3$-uniform hypergraph without a Berge cycle of length four is at most $(1+o(1))frac{n^{3/2}}{sqrt{10}}$. This improves earlier estimates by GyH{o}ri and Lemons and by Furedi and Ozkahya.
Hovey introduced $A$-cordial labelings as a generalization of cordial and harmonious labelings cite{Hovey}. If $A$ is an Abelian group, then a labeling $f colon V (G) rightarrow A$ of the vertices of some graph $G$ induces an edge labeling on $G$; the edge $uv$ receives the label $f (u) + f (v)$. A graph $G$ is $A$-cordial if there is a vertex-labeling such that (1) the vertex label classes differ in size by at most one and (2) the induced edge label classes differ in size by at most one. Patrias and Pechenik studied the larger class of finite abelian groups $A$ such that all path graphs are $A$-cordial. They posed a conjecture that all but finitely many paths graphs are $A$-cordial for any Abelian group $A$. In this paper we solve this conjecture. Moreover we show that all cycle graphs are $A$-cordial for any Abelian group $A$ of odd order.
Given a family of graphs $mathcal{F}$, we define the $mathcal{F}$-saturation game as follows. Two players alternate adding edges to an initially empty graph on $n$ vertices, with the only constraint being that neither player can add an edge that creates a subgraph in $mathcal{F}$. The game ends when no more edges can be added to the graph. One of the players wishes to end the game as quickly as possible, while the other wishes to prolong the game. We let $textrm{sat}_g(n,mathcal{F})$ denote the number of edges that are in the final graph when both players play optimally. In general there are very few non-trivial bounds on the order of magnitude of $textrm{sat}_g(n,mathcal{F})$. In this work, we find collections of infinite families of cycles $mathcal{C}$ such that $textrm{sat}_g(n,mathcal{C})$ has linear growth rate.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
