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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
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.
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.
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ć.