Consistent cycles in 1/2-arc-transitive graphs.
The intersection graph of a graph has for vertices all the induced paths of order 3 in . Two vertices in are adjacent if the corresponding paths in are not disjoint. A -container between two different vertices and in a graph is a set of internally vertex disjoint paths between and . The length of a container is the length of the longest path in it. The -wide diameter of is the minimum number such that there is a -container of length at most between any pair of different...
The graph Ramsey number R(G,H) is the smallest integer r such that every 2-coloring of the edges of Kr contains either a red copy of G or a blue copy of H. The star-critical Ramsey number r∗(G,H) is the smallest integer k such that every 2-coloring of the edges of Kr − K1,r−1−k contains either a red copy of G or a blue copy of H. We will classify the critical graphs, 2-colorings of the complete graph on R(G,H) − 1 vertices with no red G or blue H, for the path-path Ramsey number. This classification...
We study two topological properties of the 5-ary -cube . Given two arbitrary distinct nodes and in , we prove that there exists an - path of every length ranging from to , where . Based on this result, we prove that is 5-edge-pancyclic by showing that every edge in lies on a cycle of every length ranging from to .
We study two topological properties of the 5-ary n-cube . Given two arbitrary distinct nodes x and y in , we prove that there exists an x-y path of every length ranging from 2n to 5n - 1, where n ≥ 2. Based on this result, we prove that is 5-edge-pancyclic by showing that every edge in lies on a cycle of every length ranging from 5 to 5n.
In this paper, we study the existence of cycle double covers for infinite planar graphs. We show that every infinite locally finite bridgeless k-indivisible graph with a 2-basis admits a cycle double cover.
Let G be a triangle-free graph with δ(G) ≥ 2 and σ₄(G) ≥ |V(G)| + 2. Let S ⊂ V(G) consist of less than σ₄/4+ 1 vertices. We prove the following. If all vertices of S have degree at least three, then there exists a cycle C containing S. Both the upper bound on |S| and the lower bound on σ₄ are best possible.
If is a vertex of a digraph , then we denote by and the outdegree and the indegree of , respectively. A digraph is called regular, if there is a number such that for all vertices of . A -partite tournament is an orientation of a complete -partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether...
The complete tripartite graph has edges. For any collection of positive integers with and for , we exhibit an edge-disjoint decomposition of into closed trails (circuits) of lengths .
Let denote the set of all lengths of closed trails that exist in an even graph . A sequence of elements of adding up to is -realisable provided there is a sequence of pairwise edge-disjoint closed trails in such that is of length for . The graph is arbitrarily decomposable into closed trails if all possible sequences are -realisable. In the paper it is proved that if is an odd integer and is a perfect matching in , then the graph is arbitrarily decomposable into closed...
We give necessary and sufficient conditions for the decomposition of complete bipartite multigraph Km,n(λ) into paths and cycles having k edges. In particular, we show that such decomposition exists in Km,n(λ), when λ ≡ 0 (mod 2), [...] and k(p + q) = 2mn for k ≡ 0 (mod 2) and also when λ ≥ 3, λm ≡ λn ≡ 0(mod 2), k(p + q) =λ_mn, m, n ≥ k, (resp., m, n ≥ 3k/2) for k ≡ 0(mod 4) (respectively, for k ≡ 2(mod 4)). In fact, the necessary conditions given above are also sufficient when λ = 2.