Neighborhood unions and the cycle cover number of a graph

For several years, the study of neighborhood unions of graphs has given rise to important structural consequences of graphs. In particular, neighborhood conditions that give rise to hamiltonian cycles have been considered in depth. In this paper we generalize these approaches to give a bound on the smallest number of cycles in G containing all the vertices of G. We show that if for all x, y ? V(G), |N(x) ∩ N(y)| ≧ 2n/5 + 1, then V(G) is coverable by at most two cycles. Several related results and extensions to t cycles are also given.     

Ramsey numbers for all linear forests

An (n, j) linear forest L is the disjoint union of nontrivial paths, such that j of the paths have an odd number of vertices and the union has n vertices. For L, an (n₁.j₁) linear forest and l₂ an (n.j₁) linear forest, we show that

$\text{r(L}{}_1\text{,L}{}_2\text{) = max{n}{}_1\text{·(n}{}_2\text{?j}{}_2\text{)/2 ? 1, n}{}_2\text{+ (n}{}_1\text{? j}{}_1\text{)/2 ? 1}.}$

This answers in the affirmative a conjecture of Burr and Roberts.     

Contractibility techniques as a closure concept

We introduce a closure concept in the class of line graphs and claw‐free graphs based on contractibility of certain subgraphs in the line graph preimage. The closure can be considered as a common generalization and strengthening of the reduction techniques of Catlin and Veldman and of the closure concept introduced by the first author. We show that the closure is uniquely determined and the closure operation preserves the circumference of the graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 37–48, 2003     

An extremal problem for paths in bipartite graphs

A formula is found for the maximum number of edges in a graph G ? K(a, b) which contains no path P_2l for l > c. A similar formula is found for the maximum number of edges in G ? K(a, b) containing no P_{2l + 1} for l > c. In addition, all extremal graphs are determined.     

Some connected ramsey numbers

A graph G is co-connected if both G and its complement ? are connected and nontrivial. For two graphs A and B, the connected Ramsey number r_c(A, B) is the smallest integer n such that there exists a co-connected graph of order n, and if G is a co-connected graph on at least n vertices, then A ? G or B ? ?. If neither A or B contains a bridge, then it is known that r_c(A, B) = r(A, B), where r(A, B) denotes the usual Ramsey number of A and B. In this paper r_c(A, B) is calculated for some pairs (A, B) when r(A, B) is known and at least one of the graphs A or B has a bridge. In particular, r_c(A, B) is calculated for A a path and B either a cycle, star, or complete graph, and for A a star and B a complete graph.     

Giant magnetoimpedance in FM/SiO2/Cu/SiO2/FM films at GHz frequencies

We study the magnetic properties at high frequency of new structures of the tri-layer samples. The magnetoimpedance effect was analyzed in FM/i/Cu/i/FM sandwiched layers, where the ferromagnetic layer (FM) is, in fact, a multilayered film [F (10 nm)+Cu (1 nm)]×50 and F is the amorphous ferromagnetic alloy Fe_73.5Cu₁Nb₃Si_13.5B₉ and i is an isolating layer produced by magnetron sputtering. The effect of, both, the probe current frequency (in the range 10 MHz–1.8 GHz) and the dimensions of the magnetic and non-magnetic layers of the MI response were investigated. A comparison between samples with and without the isolating layer is discussed. MI ratios of 220% were obtained for samples at 180 MHz with a ferromagnetic and Cu width layers of 2 and 1 mm, respectively.     

The number of cycle lengths in graphs of given minimum degree and girth

This paper determines lower bounds on the number of different cycle lengths in a graph of given minimum degree k and girth g. The most general result gives a lower bound of ck^g/8.     

On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs

Erdős has conjectured that every subgraph of the n‐cube Q_n having more than (1/2 + o(1))e(Q_n) edges will contain a 4‐cycle. In this note we consider ‘layer’ graphs, namely, subgraphs of the cube spanned by the subsets of sizes k − 1, k and k + 1, where we are thinking of the vertices of Q_n as being the power set of {1,…, n}. Observe that every 4‐cycle in Q_n lies in some layer graph. We investigate the maximum density of 4‐cycle free subgraphs of layer graphs, principally the case k = 2. The questions that arise in this case are equivalent to natural questions in the extremal theory of directed and undirected graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 66–82, 2000     

Some Ramsey–Turán type problems and related questions

In this paper the following Ramsey–Turán type problem is one of several addressed. For which graphs $G$ does there exist a constant $0<c<1$ such that when $H$ is a graph of order the Ramsey number $r\left(G\right)$ with $\delta \left(H\right)>c\left|H\right|$, then any 2-edge coloring of $H$ contains a monochromatic copy of $G$? Specific results, conjectures, and questions with suggested values for $c$ are considered when $G$ is an odd cycle, path, or tree of limited maximum degree. Another variant is to 2-edge color a replacement for the graph $K_{r\left(G\right)}$ by a balanced multipartite graph of approximately the same order with the same consequence, a monochromatic $G$.     

Hamiltonian graphs involving distances

Let G be a graph of order n. We show that if G is a 2-connected graph and max{d(u), d(v)} + |N(u) U N(v)| ≥ n for each pair of vertices u, v at distance two, then either G is hamiltonian or G ?3K_n/3 U T₁ U T₂, where n ? O (mod 3), and T₁ and T₂ are the edge sets of two vertex disjoint triangles containing exactly one vertex from each K_n/3. This result generalizes both Fan's and Lindquester's results as well as several others.