Page 1 Next

## Displaying 1 – 20 of 511

Showing per page

### 2-factors in claw-free graphs

Discussiones Mathematicae Graph Theory

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.

### 2-factors in claw-free graphs with locally disconnected vertices

Czechoslovak Mathematical Journal

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\left(u\right)\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...

### '3in1' enhanced: three squared ways to '3in1' GRAPHS

Discussiones Mathematicae Graph Theory

### A characterization of geodetic graphs

Czechoslovak Mathematical Journal

### A characterization of the set of all shortest paths in a connected graph

Mathematica Bohemica

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...

### A conjecture on cycle-pancyclism in tournaments

Discussiones Mathematicae Graph Theory

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)=|A\left(\gamma \right)\cap A\left(Cₖ\right)|$, the number of arcs that γ and Cₖ have in common. Let $f\left(k,T,\gamma \right)=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...

### A construction of geodetic blocks

Mathematica Slovaca

### A decomposition of gallai multigraphs

Discussiones Mathematicae Graph Theory

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...

### A density result for random sparse oriented graphs and its relation to a conjecture of Woodall.

The Electronic Journal of Combinatorics [electronic only]

### A Family of Path Properties for Graphs.

Mathematische Annalen

### A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs

Discussiones Mathematicae Graph Theory

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\left\{{d}_{G}\left(u\right),{d}_{G}\left(v\right)\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...

### A Gessel--Viennot-type method for cycle systems in a directed graph.

The Electronic Journal of Combinatorics [electronic only]

### A graph and its complement with specified properties. III: Girth and circumference.

International Journal of Mathematics and Mathematical Sciences

### A Hamiltonian property of connected sets in the alternative set theory.

Acta Mathematica Universitatis Comenianae. New Series

### A linear algorithm for the two paths problem on permutation graphs

Discussiones Mathematicae Graph Theory

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.

### A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

Serdica Journal of Computing

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...

### A lower bound for the number of edges in a graph containing no two cycles of the same length.

The Electronic Journal of Combinatorics [electronic only]

### A matching and a Hamiltonian cycle of the fourth power of a connected graph

Mathematica Bohemica

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$.

### A metric for graphs

Časopis pro pěstování matematiky

### A modification of the median of a tree

Mathematica Bohemica

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

Page 1 Next