For a 3-connected planar graph G with circumference c ≥ 44 it is proved that G has a cycle of length at least (1/36)c+(20/3) through any four vertices of G.

A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that [...] . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover,...

Consider an arc-colored digraph. A set of vertices N is a kernel by monochromatic paths if all pairs of distinct vertices of N have no monochromatic directed path between them and if for every vertex v not in N there exists n ∈ N such that there is a monochromatic directed path from v to n. In this paper we prove different sufficient conditions which imply that an arc-colored tournament has a kernel by monochromatic paths. Our conditions concerns to some subdigraphs of T and its quasimonochromatic...

A normal partition of the edges of a cubic graph is a partition into trails (no repeated edge) such that each vertex is the end vertex of exactly one trail of the partition. We investigate this notion and give some results and problems.

A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. In this paper we consider linear partitions of cubic simple graphs for which it is well known that la(G) = 2. A linear partition $L=(L_B,L_R)$ is said to be odd whenever each path of $L_B\cup L_R$ has odd length and semi-odd whenever each path of $L_B$ (or each path of $L_R$) has odd length. In [2] Aldred...

We study the inheritance of path-pairability in the Cartesian product of graphs and prove additive and multiplicative inheritance patterns of path-pairability, depending on the number of vertices in the Cartesian product. We present path-pairable graph families that improve the known upper bound on the minimal maximum degree of a path-pairable graph. Further results and open questions about path-pairability are also presented.

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on $n$ vertices with minimum outdegree $d$ contains a directed cycle of length at most $\lceil n/d\rceil$. In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that ${\alpha }_0$ is the smallest real such that every $n$-vertex digraph with minimum outdegree at least ${\alpha }_{0}n$ contains a directed triangle. Let $ϵ<(3-2{\alpha }_0)/(4-2{\alpha }_0)$ be a positive real. We show that if $D$ is an oriented graph without...

Guaranteed upper bounds on the length of a shortest cycle through k ≤ 5 prescribed vertices of a polyhedral graph or plane triangulation are proved.

By a signpost system we mean an ordered pair $(W,P)$, where $W$ is a finite nonempty set, $P\subseteq W\times W\times W$ and the following statements hold: $$\text{if}(u,v,w)\in P,\text{then}(v,u,u)\in P\text{and}(v,u,w)\notin P,\text{for}\text{all}u,v,w\in W;\text{if}u\ne v,i\text{then}\text{there}\text{exists}r\in W\text{such}\text{that}(u,r,v)\in P,\text{for}\text{all}u,v\in W.$$ We say that a signpost system $(W,P)$ is smooth if the folowing statement holds for all $u,v,x,y,z\in W$: if $(u,v,x),(u,v,z),(x,y,z)\in P$, then $(u,v,y)\in P$. We say thay a signpost system $(W,P)$ is simple if the following statement holds for all $u,v,x,y\in W$: if $(u,v,x),(x,y,v)\in P$, then $(u,v,y),(x,y,u)\in P$. By the underlying graph of a signpost system $(W,P)$ we mean the graph $G$ with $V\left(G\right)=W$ and such that the following statement holds for all distinct $u,v\in W$: $u$ and $v$ are adjacent in $G$ if and only if $(u,v,v)\in P$....