Currently displaying 1 – 10 of 10

Showing per page

Order by Relevance | Title | Year of publication

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)