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

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  cycle
help Sortuj według:

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

Pairs of forbidden class of subgraphs concerning $K_{1,3}$ and P₆ to have a cycle containing specified vertices

100%
Sugiyama T., Tsugaki M.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
645-650
EN
In [3], Faudree and Gould showed that if a 2-connected graph contains no $K_{1,3}$ and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair $K_{1,3}$ and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Connectivity of path graphs

80%
Knor M., Niepel L. u.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 2
181-195
EN
We prove a necessary and sufficient condition under which a connected graph has a connected P₃-path graph. Moreover, an analogous condition for connectivity of the Pₖ-path graph of a connected graph which does not contain a cycle of length smaller than k+1 is derived.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Pancyclism and small cycles in graphs

80%
Faudree R., Favaron O., Flandrin E., Li H.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 1
27-40
EN
We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (d_C(u,v)+1, [(n+19)/13]), $d_C(u,v)$ being the distance of u and v on a hamiltonian cycle of G.
4
Content available remote

On Vertices Enforcing a Hamiltonian Cycle

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

On-line ranking number for cycles and paths

80%
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.
6
Content available remote

A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs

80%
Wide W.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 2
477-499
EN
A graph G on n vertices is said to be pancyclic if it contains cycles of all lengths k for k ∈ {3, . . . , n}. A vertex v ∈ V (G) is called super-heavy if the number of its neighbours in G is at least (n+1)/2. For a given graph H we say that G is H-f1-heavy if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies that at least one of them is super-heavy. For a family of graphs H we say that G is H-f1-heavy, if G is H-f1-heavy for every graph H ∈H. Let D denote the deer, a graph consisting of a triangle with two disjoint paths P3 adjoined to two of its vertices. In this paper we prove that every 2-connected {K1,3, P7, D}-f1-heavy graph on n ≥ 14 vertices is pancyclic. This result extends the previous work by Faudree, Ryjáček and Schiermeyer.
7
Content available remote

Pairs Of Edges As Chords And As Cut-Edges

80%
McKee T. A.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 4
673-681
EN
Several authors have studied the graphs for which every edge is a chord of a cycle; among 2-connected graphs, one characterization is that the deletion of one vertex never creates a cut-edge. Two new results: among 3-connected graphs with minimum degree at least 4, every two adjacent edges are chords of a common cycle if and only if deleting two vertices never creates two adjacent cut-edges; among 4-connected graphs, every two edges are always chords of a common cycle.
8
Content available remote

On theH-Force Number of Hamiltonian Graphs and Cycle Extendability

80%
Hexel E.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
79-88
EN
The H-force number h(G) of a hamiltonian graph G is the smallest cardinality of a set A ⊆ V (G) such that each cycle containing all vertices of A is hamiltonian. In this paper a lower and an upper bound of h(G) is given. Such graphs, for which h(G) assumes the lower bound are characterized by a cycle extendability property. The H-force number of hamiltonian graphs which are exactly 2-connected can be calculated by a decomposition formula.
9
Content available remote

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

80%
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.
10
Content available remote

A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs

80%
Wideł W.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
173-184
EN
Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] min⁡{dG(u),dG(v)}≥n+12 $\min \{ d_G (u),d_G (v)\} \ge {{n + 1} \over 2}$ . In this paper we prove that every 2-connected {K1,3, P5}-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying pancyclicity of 2-connected graphs.
11
Content available remote

On entropy of patterns given by interval maps

80%
Bobok J.
Fundamenta Mathematicae
|
1999
|
tom 162
|
nr 1
1-36
EN
Defining the complexity of a green pattern exhibited by an interval map, we give the best bounds of the topological entropy of a pattern with a given complexity. Moreover, we show that the topological entropy attains its strict minimum on the set of patterns with fixed eccentricity m/n at a unimodal X-minimal case. Using a different method, the last result was independently proved in[11].
12
Content available remote

Disjoint triangles and quadrilaterals in a graph

80%
Wang H.
Open Mathematics
|
2008
|
tom 6
|
nr 4
543-558
EN
Let n, s and t be three integers with s ≥ 1, t ≥ 0 and n = 3s + 4t. Let G be a graph of order n such that the minimum degree of G is at least (n + s)/2. Then G contains a 2-factor with s + t components such that s of them are triangles and t of them are quadrilaterals.
13
Content available remote

On the uniqueness of continuous solutions of functional equations

80%
Gaweł B.
Annales Polonici Mathematici
|
1994-1995
|
tom 60
|
nr 3
231-239
EN
We consider the problem of the vanishing of non-negative continuous solutions ψ of the functional inequalities (1)   ψ(f(x)) ≤ β(x,ψ(x)) and (2)   α(x,ψ(x)) ≤ ψ(f(x)) ≤ β(x,ψ(x)), where x varies in a fixed real interval I. As a consequence we obtain some results on the uniqueness of continuous solutions φ :I → Y of the equation (3)  φ(f(x)) = g(x,φ(x)), where Y denotes an arbitrary metric space.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Cycles through specified vertices in triangle-free graphs

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

Independent cycles and paths in bipartite balanced graphs

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

The structure and existence of 2-factors in iterated line graphs

80%
Ferrara M., Gould R., Hartke S.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
507-526
EN
We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L²(G) contains a 2-factor with every possible number of cycles, and we give a sufficient condition for the existence of a 2-factor in L²(G) with all cycle lengths specified. We also give a characterization of the graphs G where $L^k(G)$ contains a 2-factor.
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Multicolor Ramsey numbers for some paths and cycles

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

On local structure of 1-planar graphs of minimum degree 5 and girth 4

80%
Hudák D., Madaras T.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
385-400
EN
A graph is 1-planar if it can be embedded in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree 5 and girth 4 contains (1) a 5-vertex adjacent to an ≤ 6-vertex, (2) a 4-cycle whose every vertex has degree at most 9, (3) a $K_{1,4}$ with all vertices having degree at most 11.
19
Content available remote

Forbidden Pairs and (k,m)-Pancyclicity

71%
Crane C. B.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
649-663
EN
A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ {m, m+1, . . . , n}. This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree, Gould, Jacobson, and Lesniak in 2004. The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. We consider pairs of subgraphs that, when forbidden, guarantee hamiltonicity for 2-connected graphs on n ≥ 10 vertices. There are exactly ten such pairs. For each integer k ≥ 1 and each of eight such subgraph pairs {R, S}, we determine the smallest value m such that any 2-connected {R, S}-free graph on n ≥ 10 vertices is guaranteed to be (k,m)-pancyclic. Examples are provided that show the given values are best possible. Each such example we provide represents an infinite family of graphs.
20
Content available remote

Two Graphs with a Common Edge

71%
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
first rewind previous Strona / 2 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ć.