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

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

Wyniki wyszukiwania

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

A note on a new condition implying pancyclism

100%
Flandrin E., Li H., Marczyk A., Woźniak M.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 1
137-143
EN
We first show that if a 2-connected graph G of order n is such that for each two vertices u and v such that δ = d(u) and d(v) < n/2 the edge uv belongs to E(G), then G is hamiltonian. Next, by using this result, we prove that a graph G satysfying the above condition is either pancyclic or isomorphic to $K_{n/2,n/2}$.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Long cycles and neighborhood union in 1-tough graphs with large degree sums

100%
Hoa V.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 1
5-13
EN
For a 1-tough graph G we define σ₃(G) = min{d(u) + d(v) + d(w):{u,v,w} is an independent set of vertices} and $NC_{σ₃-n+5}(G)$ = $max{⋃_{i = 1}^{σ₃-n+5}$ $N(v_i) : {v₁, ..., v_{σ₃-n+5}}$ is an independent set of vertices}. We show that every 1-tough graph with σ₃(G) ≥ n contains a cycle of length at least $min{n,2NC_{σ₃-n+5}(G)+2}$. This result implies some well-known results of Faßbender [2] and of Flandrin, Jung & Li [6]. The main result of this paper also implies that c(G) ≥ min{n,2NC₂(G)+2} where NC₂(G) = min{|N(u) ∪ N(v)|:d(u,v) = 2}. This strengthens a result that c(G) ≥ min{n, 2NC₂(G)} of Bauer, Fan and Veldman [3].
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

2-factors in claw-free graphs

100%
Chen G., Faudree J., Gould R., Saito A.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 2
165-172
EN
We consider the question of the range of the number of cycles possible in a 2-factor of a 2-connected claw-free graph with sufficiently high minimum degree. (By claw-free we mean the graph has no induced $K_{1,3}$.) In particular, we show that for such a graph G of order n ≥ 51 with δ(G) ≥ (n-2)/3, G contains a 2-factor with exactly k cycles, for 1 ≤ k ≤ (n-24)/3. We also show that this result is sharp in the sense that if we lower δ(G), we cannot obtain the full range of values for k.
4
Content available remote

Decomposition of Complete Multigraphs Into Stars and Cycles

100%
Beggas F., Haddad M., Kheddouci H.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
629-639
EN
Let k be a positive integer, Sk and Ck denote, respectively, a star and a cycle of k edges. λKn is the usual notation for the complete multigraph on n vertices and in which every edge is taken λ times. In this paper, we investigate necessary and sufficient conditions for the existence of the decomposition of λKn into edges disjoint of stars Sk’s and cycles Ck’s.
5
Content available remote

On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges

100%
Abueida A. A., Lian C.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 1
113-125
EN
Let Cm and Sm denote a cycle and a star on m edges, respectively. We investigate the decomposition of the complete graphs, Kn, into cycles and stars on the same number of edges. We give an algorithm that determines values of n, for a given value of m, where Kn is {Cm, Sm}-decomposable. We show that the obvious necessary condition is sufficient for such decompositions to exist for different values of m.
6
Content available remote

On the Erdős-Gyárfás Conjecture in Claw-Free Graphs

100%
Nowbandegani P. S., Esfandiari H., Haghighi M. H. S., Bibak K.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
635-640
EN
The Erdős-Gyárfás conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of 2. Since this conjecture has proven to be far from reach, Hobbs asked if the Erdős-Gyárfás conjecture holds in claw-free graphs. In this paper, we obtain some results on this question, in particular for cubic claw-free graphs
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Edge maximal $C_{2k+1}$-edge disjoint free graphs

100%
Bataineh M., Jaradat M.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 2
271-278
EN
For two positive integers r and s, 𝓖(n;r,s) denotes to the class of graphs on n vertices containing no r of s-edge disjoint cycles and f(n;r,s) = max{𝓔(G):G ∈ 𝓖(n;r,s)}. In this paper, for integers r ≥ 2 and k ≥ 1, we determine f(n;r,2k+1) and characterize the edge maximal members in 𝓖(n;r,2k+1).
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Disjoint 5-cycles in a graph

100%
Wang H.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 2
221-242
EN
We prove that if G is a graph of order 5k and the minimum degree of G is at least 3k then G contains k disjoint cycles of length 5.
9
Content available remote

A Note on a Broken-Cycle Theorem for Hypergraphs

88%
Trinks M.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
641-646
EN
Whitney’s Broken-cycle Theorem states the chromatic polynomial of a graph as a sum over special edge subsets. We give a definition of cycles in hypergraphs that preserves the statement of the theorem there
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Chvátal-Erdos condition and pancyclism

88%
Flandrin E., Li H., Marczyk A., Schiermeyer I., Woźniak M.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
335-342
EN
The well-known Chvátal-Erdős theorem states that if the stability number α of a graph G is not greater than its connectivity then G is hamiltonian. In 1974 Erdős showed that if, additionally, the order of the graph is sufficiently large with respect to α, then G is pancyclic. His proof is based on the properties of cycle-complete graph Ramsey numbers. In this paper we show that a similar result can be easily proved by applying only classical Ramsey numbers.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Generalized total colorings of graphs

88%
Borowiecki M., Kemnitz A., Marangio M., Mihók P.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
209-222
EN
An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let P and Q be additive hereditary properties of graphs. A (P,Q)-total coloring of a simple graph G is a coloring of the vertices V(G) and edges E(G) of G such that for each color i the vertices colored by i induce a subgraph of property P, the edges colored by i induce a subgraph of property Q and incident vertices and edges obtain different colors. In this paper we present some general basic results on (P,Q)-total colorings. We determine the (P,Q)-total chromatic number of paths and cycles and, for specific properties, of complete graphs. Moreover, we prove a compactness theorem for (P,Q)-total colorings.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Variations on a sufficient condition for Hamiltonian graphs

75%
Ainouche A., Lapiquonne S.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 2
229-240
EN
Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition $N_G(x) ⊆ N_G[u] ∪ N_G[v]$, where $N_G[x] = N_G(x) ∪ {x}$. In particular, this condition is satisfied if x does not center a claw (an induced $K_{1,3}$). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = {x,y,z} we define σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|. Flandrin et al. proved that a 2-connected graph G is hamiltonian if [σ̅]₃(X) ≥ n holds for any independent triple X in G. Replacing X in G by X in the larger graph G*, Wu et al. improved recently this result. In this paper we characterize the nonhamiltonian 2-connected graphs G satisfying the condition [σ̅]₃(X) ≥ n-1 where X is independent in G*. Using the concept of dual closure we (i) give a short proof of the above results and (ii) we show that each graph G satisfying this condition is hamiltonian if and only if its dual closure does not belong to two well defined exceptional classes of graphs. This implies that it takes a polynomial time to check the nonhamiltonicity or the hamiltonicity of such G.
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ć.