Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: linear forest

Sortuj według:

Ogranicz wyniki do:

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

Partitions of some planar graphs into two linear forests

100%

Borowiecki P., Hałuszczak M.

Discussiones Mathematicae Graph Theory

1997

tom 17

nr 1

95-102

A linear forest is a forest in which every component is a path. It is known that the set of vertices V(G) of any outerplanar graph G can be partitioned into two disjoint subsets V₁,V₂ such that induced subgraphs ⟨V₁⟩ and ⟨V₂⟩ are linear forests (we say G has an (LF, LF)-partition). In this paper, we present an extension of the above result to the class of planar graphs with a given number of internal vertices (i.e., vertices that do not belong to the external face at a certain fixed embedding of the graph G in the plane). We prove that there exists an (LF, LF)-partition for any plane graph G when certain conditions on the degree of the internal vertices and their neighbourhoods are satisfied.

On a characterization of graphs by average labellings

100%

Harminc M.

Discussiones Mathematicae Graph Theory

1997

tom 17

nr 1

133-136

The additive hereditary property of linear forests is characterized by the existence of average labellings.

Partitions of a graph into cycles containing a specified linear forest

100%

Matsubara R., Matsumura H.

Discussiones Mathematicae Graph Theory

2008

tom 28

nr 1

97-107

In this note, we consider the partition of a graph into cycles containing a specified linear forest. Minimum degree and degree sum conditions are given, which are best possible.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

1 Borowiecki P.

1 Harminc M.

1 Hałuszczak M.

1 Matsubara R.

1 Matsumura H.

1 2008

2 1997

Wyniki wyszukiwania

Partitions of some planar graphs into two linear forests

On a characterization of graphs by average labellings

Partitions of a graph into cycles containing a specified linear forest