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

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  path
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

On-line ranking number for cycles and paths

100%
Bruoth E., Horňák M.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
175-197
EN
A k-ranking of a graph G is a colouring φ:V(G) → {1,...,k} such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number $χ*_r(G)$ of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that $χ*_r(Pₙ) < 3log₂n$ for n ≥ 2. Here we show that $χ*_r(Pₙ) ≤ 2⎣log₂n⎦+1$. The same upper bound is obtained for $χ*_r(Cₙ)$,n ≥ 3.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths

100%
Bielak H., Dąbrowska K.
Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica
|
2015
|
tom 69
|
nr 2
EN
The Ramsey number \(R(G, H)\) for a pair of graphs \(G\) and \(H\) is defined as the smallest integer \(n\) such that, for any graph \(F\) on \(n\) vertices, either \(F\) contains \(G\) or \(\overline{F}\) contains \(H\) as a subgraph, where \(\overline{F}\) denotes the complement of \(F\). We study Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths and determine these numbers for some cases. We extend many known results studied in [5, 14, 18, 19, 20]. In particular we count the numbers \(R(K_1+L_n, P_m)\) and \(R(K_1+L_n, C_m)\) for some integers \(m\), \(n\), where \(L_n\) is a linear forest of order \(n\) with at least one edge.
3
Content available remote

Critical Graphs for R(Pn, Pm) and the Star-Critical Ramsey Number for Paths

100%
Hook J.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
689-701
EN
The graph Ramsey number R(G,H) is the smallest integer r such that every 2-coloring of the edges of Kr contains either a red copy of G or a blue copy of H. The star-critical Ramsey number r∗(G,H) is the smallest integer k such that every 2-coloring of the edges of Kr − K1,r−1−k contains either a red copy of G or a blue copy of H. We will classify the critical graphs, 2-colorings of the complete graph on R(G,H) − 1 vertices with no red G or blue H, for the path-path Ramsey number. This classification will be used in the proof of r∗(Pn, Pm).
4
Content available remote

Decomposition of Complete Bipartite Multigraphs Into Paths and Cycles Having k Edges

100%
Jeevadoss S., Muthusamy A.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
715-731
EN
We give necessary and sufficient conditions for the decomposition of complete bipartite multigraph Km,n(λ) into paths and cycles having k edges. In particular, we show that such decomposition exists in Km,n(λ), when λ ≡ 0 (mod 2), [...] and k(p + q) = 2mn for k ≡ 0 (mod 2) and also when λ ≥ 3, λm ≡ λn ≡ 0(mod 2), k(p + q) =λ_mn, m, n ≥ k, (resp., m, n ≥ 3k/2) for k ≡ 0(mod 4) (respectively, for k ≡ 2(mod 4)). In fact, the necessary conditions given above are also sufficient when λ = 2.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Cycles through specified vertices in triangle-free graphs

100%
Paulusma D., Yoshimoto K.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 1
179-191
EN
Let G be a triangle-free graph with δ(G) ≥ 2 and σ₄(G) ≥ |V(G)| + 2. Let S ⊂ V(G) consist of less than σ₄/4+ 1 vertices. We prove the following. If all vertices of S have degree at least three, then there exists a cycle C containing S. Both the upper bound on |S| and the lower bound on σ₄ are best possible.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Independent cycles and paths in bipartite balanced graphs

100%
Orchel B., Wojda A.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
535-549
EN
Bipartite graphs G = (L,R;E) and H = (L',R';E') are bi-placeabe if there is a bijection f:L∪R→ L'∪R' such that f(L) = L' and f(u)f(v) ∉ E' for every edge uv ∈ E. We prove that if G and H are two bipartite balanced graphs of order |G| = |H| = 2p ≥ 4 such that the sizes of G and H satisfy ||G|| ≤ 2p-3 and ||H|| ≤ 2p-2, and the maximum degree of H is at most 2, then G and H are bi-placeable, unless G and H is one of easily recognizable couples of graphs. This result implies easily that for integers p and k₁,k₂,...,kₗ such that $k_i ≥ 2$ for i = 1,...,l and k₁ +...+ kₗ ≤ p-1 every bipartite balanced graph G of order 2p and size at least p²-2p+3 contains mutually vertex disjoint cycles $C_{2k₁},...,C_{2kₗ}$, unless $G = K_{3,3} - 3K_{1,1}$.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Multicolor Ramsey numbers for some paths and cycles

100%
Bielak H.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
209-218
EN
We give the multicolor Ramsey number for some graphs with a path or a cycle in the given sequence, generalizing a results of Faudree and Schelp [4], and Dzido, Kubale and Piwakowski [2,3].
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Short paths in 3-uniform quasi-random hypergraphs

100%
Polcyn J.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
469-484
EN
Frankl and Rödl [3] proved a strong regularity lemma for 3-uniform hypergraphs, based on the concept of δ-regularity with respect to an underlying 3-partite graph. In applications of that lemma it is often important to be able to "glue" together separate pieces of the desired subhypergraph. With this goal in mind, in this paper it is proved that every pair of typical edges of the underlying graph can be connected by a hyperpath of length at most seven. The typicality of edges is defined in terms of graph and hypergraph neighborhoods, and it is shown that all but a small fraction of edges are indeed typical.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The crossing numbers of certain Cartesian products

88%
Klešč M.
Discussiones Mathematicae Graph Theory
|
1995
|
tom 15
|
nr 1
5-10
EN
In this article we determine the crossing numbers of the Cartesian products of given three graphs on five vertices with paths.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Minimal vertex degree sum of a 3-path in plane maps

88%
Borodin O.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 2
279-284
EN
Let wₖ be the minimum degree sum of a path on k vertices in a graph. We prove for normal plane maps that: (1) if w₂ = 6, then w₃ may be arbitrarily big, (2) if w₂ < 6, then either w₃ ≤ 18 or there is a ≤ 15-vertex adjacent to two 3-vertices, and (3) if w₂ < 7, then w₃ ≤ 17.
11
Content available remote

Vertex Colorings without Rainbow Subgraphs

88%
Goddard W., Xu H.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 4
989-1005
EN
Given a coloring of the vertices of a graph G, we say a subgraph is rainbow if its vertices receive distinct colors. For a graph F, we define the F-upper chromatic number of G as the maximum number of colors that can be used to color the vertices of G such that there is no rainbow copy of F. We present some results on this parameter for certain graph classes. The focus is on the case that F is a star or triangle. For example, we show that the K3-upper chromatic number of any maximal outerplanar graph on n vertices is [n/2] + 1.
12
Content available remote

Two Graphs with a Common Edge

88%
Badura L.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
497-507
EN
Let G = G1 ∪ G2 be the sum of two simple graphs G1,G2 having a common edge or G = G1 ∪ e1 ∪ e2 ∪ G2 be the sum of two simple disjoint graphs G1,G2 connected by two edges e1 and e2 which form a cycle C4 inside G. We give a method of computing the determinant det A(G) of the adjacency matrix of G by reducing the calculation of the determinant to certain subgraphs of G1 and G2. To show the scope and effectiveness of our method we give some examples
13
Content available remote

Packing Coloring of Some Undirected and Oriented Coronae Graphs

88%
Laïche D., Bouchemakh I., Sopena É.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
665-690
EN
The packing chromatic number χρ(G) of a graph G is the smallest integer k such that its set of vertices V(G) can be partitioned into k disjoint subsets V1, . . . , Vk, in such a way that every two distinct vertices in Vi are at distance greater than i in G for every i, 1 ≤ i ≤ k. For a given integer p ≥ 1, the p-corona of a graph G is the graph obtained from G by adding p degree-one neighbors to every vertex of G. In this paper, we determine the packing chromatic number of p-coronae of paths and cycles for every p ≥ 1. Moreover, by considering digraphs and the (weak) directed distance between vertices, we get a natural extension of the notion of packing coloring to digraphs. We then determine the packing chromatic number of orientations of p-coronae of paths and cycles.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The crossing numbers of join products of paths with graphs of order four

88%
Klešč M., Schrötter S.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
321-331
EN
Kulli and Muddebihal [V.R. Kulli, M.H. Muddebihal, Characterization of join graphs with crossing number zero, Far East J. Appl. Math. 5 (2001) 87-97] gave the characterization of all pairs of graphs which join product is planar graph. The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. There are only few results concerning crossing numbers of graphs obtained as join product of two graphs. In the paper, the exact values of crossing numbers for join of paths with all graphs of order four, as well as for join of all graphs of order four with n isolated vertices are given.
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The crossing numbers of products of a 5-vertex graph with paths and cycles

75%
Klešč M.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 1
59-69
EN
There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with "small" graphs. Let H be the 5-vertex graph defined from K₅ by removing three edges incident with a common vertex. In this paper, we extend the earlier results to the Cartesian products of H × Pₙ and H × Cₙ, showing that in the general case the corresponding crossing numbers are 3n-1, and 3n for even n or 3n+1 if n is odd.
16
Content available remote

The Crossing Numbers of Products of Path with Graphs of Order Six

75%
Klešč M., Petrillová J.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
571-582
EN
The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. For the path Pn of length n, the crossing numbers of Cartesian products G⃞Pn for all connected graphs G on five vertices are also known. In this paper, the crossing numbers of Cartesian products G⃞Pn for graphs G of order six are studied. Let H denote the unique tree of order six with two vertices of degree three. The main contribution is that the crossing number of the Cartesian product H⃞Pn is 2(n − 1). In addition, the crossing numbers of G⃞Pn for fourty graphs G on six vertices are collected
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Light classes of generalized stars in polyhedral maps on surfaces

75%
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.
18
Content available remote

Distinguished geodesics and jacobi fields on first order jet spaces

51%
Balan V., Voicu N.
Open Mathematics
|
2004
|
tom 2
|
nr 4
516-526
EN
In the framework of jet spaces endowed with a non-linear connection, the special curves of these spaces (h-paths, v-paths, stationary curves and geodesics) which extend the corresponding notions from Riemannian geometry are characterized. The main geometric objects and the paths are described and, in the case when the vertical metric is independent of fiber coordinates, the first two variations of energy and the extended Jacobi field equations are derived.
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ć.