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: 16

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

Wyniki wyszukiwania

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

Unavoidable set of face types for planar maps

100%
Horňák M., Jendrol S.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 2
123-141
EN
The type of a face f of a planar map is a sequence of degrees of vertices of f as they are encountered when traversing the boundary of f. A set 𝒯 of face types is found such that in any normal planar map there is a face with type from 𝒯. The set 𝒯 has four infinite series of types as, in a certain sense, the minimum possible number. An analogous result is applied to obtain new upper bounds for the cyclic chromatic number of 3-connected planar maps.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

An inequality concerning edges of minor weight in convex 3-polytopes

100%
Fabrici I., Jendrol' S.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 1
81-87
EN
Let $e_{ij}$ be the number of edges in a convex 3-polytope joining the vertices of degree i with the vertices of degree j. We prove that for every convex 3-polytope there is $20e_{3,3} + 25e_{3,4} + 16e_{3,5} + 10e_{3,6} + 6[2/3]e_{3,7} + 5e_{3,8} + 2[1/2]e_{3,9} + 2e_{3,10} + 16[2/3]e_{4,4} + 11e_{4,5} + 5e_{4,6} + 1[2/3]e_{4,7} + 5[1/3]e_{5,5} + 2e_{5,6} ≥ 120$; moreover, each coefficient is the best possible. This result brings a final answer to the conjecture raised by B. Grünbaum in 1973.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On light subgraphs in plane graphs of minimum degree five

100%
Jendrol' S., Madaras T.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 2
207-217
EN
A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars $K_{1,3}$ and $K_{1,4}$ and a light 4-path P₄. The results obtained for $K_{1,3}$ and P₄ are best possible.
4
Content available remote

Maximum Edge-Colorings Of Graphs

100%
Jendrol’ S., Vrbjarová M.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
117-125
EN
An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index [...] χr′(G) $\chi _r^\prime (G)$ is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that [...] χr′(G)≤3 $\chi _r^\prime (G) \le 3$ for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with [...] χ1′(G)=i $\chi _1^\prime (G) = i$ , i = 1, 2, 3 are characterized. The precise value of the r-maximum index, r ≥ 1, is determined for trees and complete graphs.
5
Content available remote

A note on face coloring entire weightings of plane graphs

100%
Jendrol S., Šugerek P.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 2
421-426
EN
Given a weighting of all elements of a 2-connected plane graph G = (V,E, F), let f(α) denote the sum of the weights of the edges and vertices incident with the face _ and also the weight of _. Such an entire weighting is a proper face colouring provided that f(α) ≠ f(β) for every two faces α and _ sharing an edge. We show that for every 2-connected plane graph there is a proper face-colouring entire weighting with weights 1 through 4. For some families we improved 4 to 3
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Total edge irregularity strength of trees

100%
Ivančo J., Jendrol' S.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 3
449-456
EN
A total edge-irregular k-labelling ξ:V(G)∪ E(G) → {1,2,...,k} of a graph G is a labelling of vertices and edges of G in such a way that for any different edges e and f their weights wt(e) and wt(f) are distinct. The weight wt(e) of an edge e = xy is the sum of the labels of vertices x and y and the label of the edge e. The minimum k for which a graph G has a total edge-irregular k-labelling is called the total edge irregularity strength of G, tes(G). In this paper we prove that for every tree T of maximum degree Δ on p vertices tes(T) = max{⎡(p+1)/3⎤,⎡(Δ+1)/2⎤}.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Light classes of generalized stars in polyhedral maps on surfaces

100%
Jendrol' S., Voss H.-J.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 1
85-107
EN
A generalized s-star, s ≥ 1, is a tree with a root Z of degree s; all other vertices have degree ≤ 2. $S_i$ denotes a generalized 3-star, all three maximal paths starting in Z have exactly i+1 vertices (including Z). Let 𝕄 be a surface of Euler characteristic χ(𝕄) ≤ 0, and m(𝕄):= ⎣(5 + √{49-24χ(𝕄 )})/2⎦. We prove: (1) Let k ≥ 1, d ≥ m(𝕄) be integers. Each polyhedral map G on 𝕄 with a k-path (on k vertices) contains a k-path of maximum degree ≤ d in G or a generalized s-star T, s ≤ m(𝕄), on d + 2- m(𝕄) vertices with root Z, where Z has degree ≤ k·m(𝕄) and the maximum degree of T∖{Z} is ≤ d in G. Similar results are obtained for the plane and for large polyhedral maps on 𝕄.. (2) Let k and i be integers with k ≥ 3, 1 ≤ i ≤ [k/2]. If a polyhedral map G on 𝕄 with a large enough number of vertices contains a k-path then G contains a k-path or a 3-star $S_i$ of maximum degree ≤ 4(k+i) in G. This bound is tight. Similar results hold for plane graphs.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Colouring vertices of plane graphs under restrictions given by faces

100%
Czap J., Jendrol' S.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
521-543
EN
We consider a vertex colouring of a connected plane graph G. A colour c is used k times by a face α of G if it appears k times along the facial walk of α. We prove that every connected plane graph with minimum face degree at least 3 has a vertex colouring with four colours such that every face uses some colour an odd number of times. We conjecture that such a colouring can be done using three colours. We prove that this conjecture is true for 2-connected cubic plane graphs. Next we consider other three kinds of colourings that require stronger restrictions.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Distance coloring of the hexagonal lattice

100%
Jacko P., Jendrol' S.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
151-166
EN
Motivated by the frequency assignment problem we study the d-distant coloring of the vertices of an infinite plane hexagonal lattice H. Let d be a positive integer. A d-distant coloring of the lattice H is a coloring of the vertices of H such that each pair of vertices distance at most d apart have different colors. The d-distant chromatic number of H, denoted $χ_d(H)$, is the minimum number of colors needed for a d-distant coloring of H. We give the exact value of $χ_d(H)$ for any d odd and estimations for any d even.
10
Content available remote

On Maximum Weight of a Bipartite Graph of Given Order and Size

81%
Horňák M., Jendrol’ S., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
147-165
EN
The weight of an edge xy of a graph is defined to be the sum of degrees of the vertices x and y. The weight of a graph G is the minimum of weights of edges of G. More than twenty years ago Erd˝os was interested in finding the maximum weight of a graph with n vertices and m edges. This paper presents a complete solution of a modification of the above problem in which a graph is required to be bipartite. It is shown that there is a function w*(n,m) such that the optimum weight is either w*(n,m) or w*(n,m) + 1.
11
Content available remote

On Vertices Enforcing a Hamiltonian Cycle

81%
Fabrici I., Hexel E., Jendrol’ S.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
71-89
EN
A nonempty vertex set X ⊆ V (G) of a hamiltonian graph G is called an H-force set of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The H-force number h(G) of a graph G is defined to be the smallest cardinality of an H-force set of G. In the paper the study of this parameter is introduced and its value or a lower bound for outerplanar graphs, planar graphs, k-connected graphs and prisms over graphs is determined.
12
Content available remote

A Note On Vertex Colorings Of Plane Graphs

81%
Fabricia I., Jendrol’ S., Soták R.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 4
849-855
EN
Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.
13
Content available remote

3-Paths in Graphs with Bounded Average Degree

81%
Jendrol′ S., Maceková M., Montassier M., Soták R.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
339-353
EN
In this paper we study the existence of unavoidable paths on three vertices in sparse graphs. A path uvw on three vertices u, v, and w is of type (i, j, k) if the degree of u (respectively v, w) is at most i (respectively j, k). We prove that every graph with minimum degree at least 2 and average degree strictly less than m contains a path of one of the types [...] Moreover, no parameter of this description can be improved.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Paths of low weight in planar graphs

81%
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$.
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On long cycles through four prescribed vertices of a polyhedral graph

81%
Harant J., Jendrol' S., Walther H.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
441-451
EN
For a 3-connected planar graph G with circumference c ≥ 44 it is proved that G has a cycle of length at least (1/36)c+(20/3) through any four vertices of G.
16
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Parity vertex colouring of graphs

81%
Borowiecki P., Budajová K., Jendrol' S., Krajci S.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
183-195
EN
A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T), then ⌈log₂(2+diam(T))⌉ ≤ χₚ(T) ≤ 1+rad(T). Both bounds are tight. The second thread of this paper is devoted to relationships between parity vertex colourings and vertex rankings, i.e. a proper vertex colourings with the property that each path between two vertices of the same colour q contains a vertex of colour greater than q. New results on graphs critical for vertex rankings are also presented.
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ć.