We consider the question of the range of the number of cycles possible in a 2-factor of a 2-connected claw-free graph with sufficiently high minimum degree. (By claw-free we mean the graph has no induced $K_{1,3}$.) In particular, we show that for such a graph G of order n ≥ 51 with δ(G) ≥ (n-2)/3, G contains a 2-factor with exactly k cycles, for 1 ≤ k ≤ (n-24)/3. We also show that this result is sharp in the sense that if we lower δ(G), we cannot obtain the full range of values for k.

An edge of $G$ is singular if it does not lie on any triangle of $G$; otherwise, it is non-singular. A vertex $u$ of a graph $G$ is called locally connected if the induced subgraph $G\left[N\right(u\left)\right]$ by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph $G$ of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex $v$ of degree at least $3$ in $G,$ there is a nonnegative integer $s$ such that $v$ lies...

Let $G$ be a (finite undirected) connected graph (with no loop or multiple edge). The set $ℒ$ of all shortest paths in $G$ is defined as the set of all paths $\xi$, then the lenght of $\xi$ does not exceed the length of $\varsigma$. While the definition of $ℒ$ is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an “almost non-metric” characterization of $ℒ$: a characterization in which the length of a path greater than one is not considered. Two other theorems are derived from Theorem...

Let T be a hamiltonian tournament with n vertices and γ a hamiltonian cycle of T. In previous works we introduced and studied the concept of cycle-pancyclism to capture the following question: What is the maximum intersection with γ of a cycle of length k? More precisely, for a cycle Cₖ of length k in T we denote $I_{\gamma }\left(Cₖ\right)=\left|A\left(\gamma \right)\cap A\left(Cₖ\right)\right|$, the number of arcs that γ and Cₖ have in common. Let $f(k,T,\gamma )=max{I}_{\gamma }\left(Cₖ\right)|Cₖ\subset T$ and f(n,k) = minf(k,T,γ)|T is a hamiltonian tournament with n vertices, and γ a hamiltonian cycle of T. In previous papers we gave...

An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed trees...

Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] min⁡dG(u),dG(v)≥n+12 $min\{d_G\left(u\right),d_G\left(v\right)\}\ge \frac{n+1}{2}$ . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying pancyclicity...

The 'two paths problem' is stated as follows. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two vertex-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂ respectively. In this paper we give a linear (O(|V|+ |E|)) algorithm to solve the above problem on a permutation graph.

ACM Computing Classification System (1998): G.2.2.We propose an algorithm that computes the length of a longest path in a cactus graph. Our algorithm can easily be modified to output a longest path as well or to solve the problem on cacti with edge or vertex weights. The algorithm works on rooted cacti and assigns to each vertex a two-number label, the first number being the desired parameter of the subcactus rooted at that vertex. The algorithm applies the divide-and-conquer approach and computes...

The following result is proved: Let $G$ be a connected graph of order $geq4$. Then for every matching $M$ in $G^4$ there exists a hamiltonian cycle $C$ of $G^4$ such that $E\left(C\right)\bigcap M=0$.

The concept of median of a tree is modified, considering only distances from the terminal vertices instead of distances from all vertices.