Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn $2$-cycles of graphs
56
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $G=(V,E)$ be a finite undirected graph. Orient the edges of $G$ in an arbitrary way. A $2$-cycle on $G$ is a function $d : E^2to mathbb{Z}$ such for each edge $e$, $d(e, cdot)$ and $d(cdot, e)$ are circulations on $G$, and $d(e, f) = 0$ whenever $e$ and $f$ have a common vertex. We show that each $2$-cycle is a sum of three special types of $2$-cycles: cycle-pair $2$-cycles, Kuratowski $2$-cycles, and quad $2$-cycles. In case that the graph is Kuratowski connected, we show that each $2$-cycle is a sum of cycle-pair $2$-cycles and at most one Kuratowski $2$-cycle. Furthermore, if $G$ is Kuratowski connected, we characterize when every Kuratowski $2$-cycle is a sum of cycle-pair $2$-cycles. A $2$-cycles $d$ on $G$ is skew-symmetric if $d(e,f) = -d(f,e)$ for all edges $e,fin E$. We show that each $2$-cycle is a sum of two special types of skew-symmetric $2$-cycles: skew-symmetric cycle-pair $2$-cycles and skew-symmetric quad $2$-cycles. In case that the graph is Kuratowski connected, we show that each skew-symmetric $2$-cycle is a sum of skew-symmetric cycle-pair $2$-cycles. Similar results like this had previously been obtained by one of the authors for symmetric $2$-cycles. Symmetric $2$-cycles are $2$-cycles $d$ such that $d(e,f)=d(f,e)$ for all edges $e,fin E$.
rate research
Read More
In 1930, Kuratowski showed that $K_{3,3}$ and $K_5$ are the only two minor-minimal non-planar graphs. Robertson and Seymour extended finiteness of the set of forbidden minors for any surface. v{S}ir{a}v{n} and Kochol showed that there are infinitely many $k$-crossing-critical graphs for any $kge 2$, even if restricted to simple $3$-connected graphs. Recently, $2$-crossing-critical graphs have been completely characterized by Bokal, Oporowski, Richter, and Salazar. We present a simplified description of large 2-crossing-critical graphs and use this simplification to count Hamiltonian cycles in such graphs. We generalize this approach to an algorithm counting Hamiltonian cycles in all 2-tiled graphs, thus extending the results of Bodrov{z}a-Pantic, Kwong, Doroslovav{c}ki, and Pantic for $n = 2$.
Let $G$ be a finite group. We show that if $|G| = pqrs$, where $p$, $q$, $r$, and $s$ are distinct odd primes, then every connected Cayley graph on $G$ has a hamiltonian cycle.
Let $G = (V, E)$ be an $n$-vertex edge-colored graph. In 2013, H. Li proved that if every vertex $v in V$ is incident to at least $(n+1)/2$ distinctly colored edges, then $G$ admits a rainbow triangle. We prove that the same hypothesis ensures a rainbow $ell$-cycle $C_{ell}$ whenever $n ge 432 ell$. This result is sharp for all odd integers $ell geq 3$, and extends earlier work of the authors for when $ell$ is even.
Let $G$ be a graph of order $n$ with an edge-coloring $c$, and let $delta^c(G)$ denote the minimum color degree of $G$. A subgraph $F$ of $G$ is called rainbow if all edges of $F$ have pairwise distinct colors. There have been a lot results on rainbow cycles of edge-colored graphs. In this paper, we show that (i) if $delta^c(G)>frac{3n-3}{4}$, then every vertex of $G$ is contained in a rainbow triangle; (ii) $delta^c(G)>frac{3n}{4}$, then every vertex of $G$ is contained in a rainbow $C_4$; and (iii) if $G$ is complete, $ngeq 8k-18$ and $delta^c(G)>frac{n-1}{2}+k$, then $G$ contains a rainbow cycle of length at least $k$. Some gaps in previous publications are also found and corrected.
We prove that the number of Hamilton cycles in the random graph G(n,p) is n!p^n(1+o(1))^n a.a.s., provided that pgeq (ln n+ln ln n+omega(1))/n. Furthermore, we prove the hitting-time version of this statement, showing that in the random graph process, the edge that creates a graph of minimum degree 2 creates (ln n/e)^n(1+o(1))^n Hamilton cycles a.a.s.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
