Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Spanning caterpillars with bounded diameter

100%

Faudree R., Gould R., Jacobson M., Lesniak L.

Discussiones Mathematicae Graph Theory

1995

tom 15

nr 2

111-118

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 $cn^{3/4}$ (at most n).

Potentially H-bigraphic sequences

100%

Ferrara M., Jacobson M., Schmitt J., Siggers M.

Discussiones Mathematicae Graph Theory

2009

tom 29

nr 3

583-596

We extend the notion of a potentially H-graphic sequence as follows. Let A and B be nonnegative integer sequences. The sequence pair S = (A,B) is said to be bigraphic if there is some bipartite graph G = (X ∪ Y,E) such that A and B are the degrees of the vertices in X and Y, respectively. If S is a bigraphic pair, let σ(S) denote the sum of the terms in A. Given a bigraphic pair S, and a fixed bipartite graph H, we say that S is potentially H-bigraphic if there is some realization of S containing H as a subgraph. We define σ(H,m,n) to be the minimum integer k such that every bigraphic pair S = (A,B) with |A| = m, |B| = n and σ(S) ≥ k is potentially H-bigraphic. In this paper, we determine $σ(K_{s,t},m,n)$, σ(Pₜ,m,n) and $σ(C_{2t},m,n)$.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Jacobson M.

1 Faudree R.

1 Ferrara M.

1 Gould R.

1 Lesniak L.

1 Schmitt J.

1 Siggers M.

1 2009

1 1995

Wyniki wyszukiwania

Spanning caterpillars with bounded diameter

Potentially H-bigraphic sequences