The $P_3$ intersection graph of a graph $G$ has for vertices all the induced paths of order 3 in $G$. Two vertices in $P_3\left(G\right)$ are adjacent if the corresponding paths in $G$ are not disjoint. A $w$-container between two different vertices $u$ and $v$ in a graph $G$ is a set of $w$ internally vertex disjoint paths between $u$ and $v$. The length of a container is the length of the longest path in it. The $w$-wide diameter of $G$ is the minimum number $l$ such that there is a $w$-container of length at most $l$ 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 $n$-cube $Q_n^5$. Given two arbitrary distinct nodes $x$ and $y$ in $Q_n^5$, we prove that there exists an $x$-$y$ path of every length ranging from $2n$ to $5^n-1$, where $n\ge 2$. Based on this result, we prove that $Q_n^5$ is 5-edge-pancyclic by showing that every edge in $Q_n^5$ lies on a cycle of every length ranging from $5$ to $5^n$.

We study two topological properties of the 5-ary n-cube $Q_n^5$. Given two arbitrary distinct nodes x and y in $Q_n^5$, 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 $Q_n^5$ is 5-edge-pancyclic by showing that every edge in $Q_n^5$ 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 $x$ is a vertex of a digraph $D$, then we denote by $d^{+}\left(x\right)$ and $d^{-}\left(x\right)$ the outdegree and the indegree of $x$, respectively. A digraph $D$ is called regular, if there is a number $p\in \mathbb{N}$ such that $d^{+}\left(x\right)=d^{-}\left(x\right)=p$ for all vertices $x$ of $D$. A $c$-partite tournament is an orientation of a complete $c$-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...