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

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  graph decomposition
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

Decomposition of Certain Complete Bipartite Graphs into Prisms

100%
Froncek D.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
55-62
EN
Häggkvist [6] proved that every 3-regular bipartite graph of order 2n with no component isomorphic to the Heawood graph decomposes the complete bipartite graph K6n,6n. In [1] Cichacz and Froncek established a necessary and sufficient condition for the existence of a factorization of the complete bipartite graph Kn,n into generalized prisms of order 2n. In [2] and [3] Cichacz, Froncek, and Kovar showed decompositions of K3n/2,3n/2 into generalized prisms of order 2n. In this paper we prove that K6n/5,6n/5 is decomposable into prisms of order 2n when n ≡ 0 (mod 50).
2
Content available remote

On Decomposing Regular Graphs Into Isomorphic Double-Stars

100%
El-Zanati S. I., Ermete M., Hasty J., Plantholt M. J., Tipnis S.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 1
73-79
EN
A double-star is a tree with exactly two vertices of degree greater than 1. If T is a double-star where the two vertices of degree greater than one have degrees k1+1 and k2+1, then T is denoted by Sk1,k2 . In this note, we show that every double-star with n edges decomposes every 2n-regular graph. We also show that the double-star Sk,k−1 decomposes every 2k-regular graph that contains a perfect matching.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Product rosy labeling of graphs

100%
Fronček D.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
431-439
EN
In this paper we describe a natural extension of the well-known ρ-labeling of graphs (also known as rosy labeling). The labeling, called product rosy labeling, labels vertices with elements of products of additive groups. We illustrate the usefulness of this labeling by presenting a recursive construction of infinite families of trees decomposing complete graphs.
4
Content available remote

The Balanced Decomposition Number of TK4 and Series-Parallel Graphs

80%
Fujita S., Liu H.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
347-359
EN
A balanced colouring of a graph G is a colouring of some of the vertices of G with two colours, say red and blue, such that there is the same number of vertices in each colour. The balanced decomposition number f(G) of G is the minimum integer s with the following property: For any balanced colouring of G, there is a partition V (G) = V1 ∪˙ · · · ∪˙ Vr such that, for every i, Vi induces a connected subgraph of order at most s, and contains the same number of red and blue vertices. The function f(G) was introduced by Fujita and Nakamigawa in 2008. They conjectured that f(G) ≤ ⌊n 2 ⌋ + 1 if G is a 2-connected graph on n vertices. In this paper, we shall prove two partial results, in the cases when G is a subdivided K4, and a 2-connected series-parallel graph.
5
Content available remote

Decomposition of Complete Multigraphs Into Stars and Cycles

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

A ramsey-type theorem for multiple disjoint copies of induced subgraphs

80%
Nakamigawa T.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 2
249-261
EN
Let k and ℓ be positive integers with ℓ ≤ k − 2. It is proved that there exists a positive integer c depending on k and ℓ such that every graph of order (2k−1−ℓ/k)n+c contains n vertex disjoint induced subgraphs, where these subgraphs are isomorphic to each other and they are isomorphic to one of four graphs: (1) a clique of order k, (2) an independent set of order k, (3) the join of a clique of order ℓ and an independent set of order k − ℓ, or (4) the union of an independent set of order ℓ and a clique of order k − ℓ.
7
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.
8
Content available remote

On Double-Star Decomposition of Graphs

80%
Akbari S., Haghi S., Maimani H., Seify A.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
835-840
EN
A tree containing exactly two non-pendant vertices is called a double-star. A double-star with degree sequence (k1 + 1, k2 + 1, 1, . . . , 1) is denoted by Sk1,k2. We study the edge-decomposition of graphs into double-stars. It was proved that every double-star of size k decomposes every 2k-regular graph. In this paper, we extend this result by showing that every graph in which every vertex has degree 2k + 1 or 2k + 2 and containing a 2-factor is decomposed into Sk1,k2 and Sk1−1,k2, for all positive integers k1 and k2 such that k1 + k2 = k.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Decomposing complete graphs into cubes

80%
El-Zanati S., Eynden C.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 1
141-147
EN
This paper concerns when the complete graph on n vertices can be decomposed into d-dimensional cubes, where d is odd and n is even. (All other cases have been settled.) Necessary conditions are that n be congruent to 1 modulo d and 0 modulo $2^d$. These are known to be sufficient for d equal to 3 or 5. For larger values of d, the necessary conditions are asymptotically sufficient by Wilson's results. We prove that for each odd d there is an infinite arithmetic progression of even integers n for which a decomposition exists. This lends further weight to a long-standing conjecture of Kotzig.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Orthogonal double covers of complete graphs by fat caterpillars

80%
Froncek D., Leck U.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
343-349
EN
An orthogonal double cover (ODC) of the complete graph Kₙ by some graph G is a collection of n spanning subgraphs of Kₙ, all isomorphic to G, such that any two of the subgraphs share exactly one edge and every edge of Kₙ is contained in exactly two of the subgraphs. A necessary condition for such an ODC to exist is that G has exactly n-1 edges. We show that for any given positive integer d, almost all caterpillars of diameter d admit an ODC of the corresponding complete graph.
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ć.