Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 8

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  planar graphs
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Short cycles of low weight in normal plane maps with minimum degree 5

100%
Borodin O., Woodall D.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 2
159-164
EN
In this note, precise upper bounds are determined for the minimum degree-sum of the vertices of a 4-cycle and a 5-cycle in a plane triangulation with minimum degree 5: w(C₄) ≤ 25 and w(C₅) ≤ 30. These hold because a normal plane map with minimum degree 5 must contain a 4-star with $w(K_{1,4}) ≤ 30$. These results answer a question posed by Kotzig in 1979 and recent questions of Jendrol' and Madaras.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Partitions of some planar graphs into two linear forests

80%
Borowiecki P., Hałuszczak M.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
95-102
EN
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.
3
Content available remote

Strong Chromatic Index Of Planar Graphs With Large Girth

80%
Jennhwa Chang G., Montassier M., Pêche A., Raspaud A.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 4
723-733
EN
Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6.
4
Content available remote

Triangle Decompositions of Planar Graphs

80%
Mynhardt C. M., Bommel C. M. v.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
643-659
EN
A multigraph G is triangle decomposable if its edge set can be partitioned into subsets, each of which induces a triangle of G, and rationally triangle decomposable if its triangles can be assigned rational weights such that for each edge e of G, the sum of the weights of the triangles that contain e equals 1. We present a necessary and sufficient condition for a planar multigraph to be triangle decomposable. We also show that if a simple planar graph is rationally triangle decomposable, then it has such a decomposition using only weights 0, 1 and 1/2 . This result provides a characterization of rationally triangle decomposable simple planar graphs. Finally, if G is a multigraph with K4 as underlying graph, we give necessary and sufficient conditions on the multiplicities of its edges for G to be triangle and rationally triangle decomposable.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Decompositions of quadrangle-free planar graphs

80%
Borodin O., Ivanova A., Kostochka A., Sheikh N.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 1
87-99
EN
W. He et al. showed that a planar graph not containing 4-cycles can be decomposed into a forest and a graph with maximum degree at most 7. This degree restriction was improved to 6 by Borodin et al. We further lower this bound to 5 and show that it cannot be improved to 3.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A characterization of planar median graphs

80%
Peterin I.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 1
41-48
EN
Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A note on Hamiltonian cycles in generalized Halin graphs

80%
Bojarska M.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 4
701-704
EN
We show that every 2-connected (2)-Halin graph is Hamiltonian.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Paths of low weight in planar graphs

70%
Fabrici I., Harant J., Jendrol' S.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 1
121-135
EN
The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are: 1. Every 3-connected simple planar graph G that contains a k-path, a path on k vertices, also contains a k-path P such that for its weight (the sum of degrees of its vertices) in G it holds $w_G(P): = ∑_{u∈ V(P)} deg_G(u) ≤ (3/2)k² + 𝓞(k)$ 2. Every plane triangulation T that contains a k-path also contains a k-path P such that for its weight in T it holds $w_T(P): = ∑_{u∈ V(P)} deg_T(u) ≤ k² +13 k$ 3. Let G be a 3-connected simple planar graph of circumference c(G). If c(G) ≥ σ| V(G)| for some constant σ > 0 then for any k, 1 ≤ k ≤ c(G), G contains a k-path P such that $w_G(P) = ∑_{u∈ V(P)} deg_G(u) ≤ (3/σ + 3)k$.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.