Currently displaying 1 – 14 of 14

Showing per page

Order by Relevance | Title | Year of publication

Extremal problems for forbidden pairs that imply hamiltonicity

Ralph Faudree;  András Gyárfás — 1999

Discussiones Mathematicae Graph Theory

Let C denote the claw K 1 , 3 , N the net (a graph obtained from a K₃ by attaching a disjoint edge to each vertex of the K₃), W the wounded (a graph obtained from a K₃ by attaching an edge to one vertex and a disjoint path P₃ to a second vertex), and Z i the graph consisting of a K₃ with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a k-connected graph G of order n that is CY-free (does...

Pancyclism and small cycles in graphs

Ralph Faudree;  Odile Favaron;  Evelyne Flandrin;  Hao Li — 1996

Discussiones Mathematicae Graph Theory

We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (dC(u,v)+1, [(n+19)/13]), d C ( u , v ) being the distance of u and v on a hamiltonian cycle of G.

Spanning caterpillars with bounded diameter

Ralph Faudree;  Ronald Gould;  Michael Jacobson;  Linda Lesniak — 1995

Discussiones Mathematicae Graph Theory

A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most c n 3 / 4 (at most n).

Weak Saturation Numbers for Sparse Graphs

Ralph J. Faudree;  Ronald J. Gould;  Michael S. Jacobson — 2013

Discussiones Mathematicae Graph Theory

For a fixed graph F, a graph G is F-saturated if there is no copy of F in G, but for any edge e ∉ G, there is a copy of F in G + e. The minimum number of edges in an F-saturated graph of order n will be denoted by sat(n, F). A graph G is weakly F-saturated if there is an ordering of the missing edges of G so that if they are added one at a time, each edge added creates a new copy of F. The minimum size of a weakly F-saturated graph G of order n will be denoted by wsat(n, F). The graphs of order...

Forbidden triples implying Hamiltonicity: for all graphs

Ralph J. Faudree;  Ronald J. Gould;  Michael S. Jacobson — 2004

Discussiones Mathematicae Graph Theory

In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with G i = K 1 , 3 for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a K 1 , s , s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being K 1 , 3 , such that all G₁G₂G₃-free...

Potential forbidden triples implying hamiltonicity: for sufficiently large graphs

Ralph J. Faudree;  Ronald J. Gould;  Michael S. Jacobson — 2005

Discussiones Mathematicae Graph Theory

In [1], Brousek characterizes all triples of connected graphs, G₁,G₂,G₃, with G i = K 1 , 3 for some i = 1,2, or 3, such that all G₁G₂ G₃-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁,G₂,G₃, none of which is a K 1 , s , s ≥ 3 such that G₁G₂G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G₁,G₂,G₃ with none being K 1 , 3 , such that all G₁G₂G₃-free graphs are...

Chvátal-Erdös type theorems

Jill R. Faudree;  Ralph J. Faudree;  Ronald J. Gould;  Michael S. Jacobson;  Colton Magnant — 2010

Discussiones Mathematicae Graph Theory

The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1),...

Saturation Spectrum of Paths and Stars

Jill Faudree;  Ralph J. Faudree;  Ronald J. Gould;  Michael S. Jacobson;  Brent J. Thomas — 2017

Discussiones Mathematicae Graph Theory

A graph G is H-saturated if H is not a subgraph of G but the addition of any edge from G̅ to G results in a copy of H. The minimum size of an H-saturated graph on n vertices is denoted sat(n,H), while the maximum size is the well studied extremal number, ex(n,H). The saturation spectrum for a graph H is the set of sizes of H saturated graphs between sat(n,H) and ex(n,H). In this paper we completely determine the saturation spectrum of stars and we show the saturation spectrum of paths is continuous...

Linear forests and ordered cycles

Guantao Chen;  Ralph J. Faudree;  Ronald J. Gould;  Michael S. Jacobson;  Linda Lesniak;  Florian Pfender — 2004

Discussiones Mathematicae Graph Theory

A collection L = P ¹ ∪ P ² ∪ . . . ∪ P t (1 ≤ t ≤ k) of t disjoint paths, s of them being singletons with |V(L)| = k is called a (k,t,s)-linear forest. A graph G is (k,t,s)-ordered if for every (k,t,s)-linear forest L in G there exists a cycle C in G that contains the paths of L in the designated order as subpaths. If the cycle is also a hamiltonian cycle, then G is said to be (k,t,s)-ordered hamiltonian. We give sharp sum of degree conditions for nonadjacent vertices that imply a graph is (k,t,s)-ordered hamiltonian.

Page 1

Download Results (CSV)