All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 251

Showing per page

Decomposition of complete bipartite digraphs and even complete bipartite multigraphs into closed trails

Sylwia Cichacz (2007)

Discussiones Mathematicae Graph Theory

It has been shown [3] that any bipartite graph K a , b , where a, b are even integers, can be decomposed into closed trails with prescribed even lengths. In this article, we consider the corresponding question for directed bipartite graphs. We show that a complete directed bipartite graph ↔ K a , b is decomposable into directed closed trails of even lengths greater than 2, whenever these lengths sum up to the size of the digraph. We use this result to prove that complete bipartite multigraphs can be decomposed...

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

Shanmugasundaram Jeevadoss, Appu Muthusamy (2015)

Discussiones Mathematicae Graph Theory

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.

Decomposition of complete graphs into ( 0 , 2 ) -prisms

Sylwia Cichacz, Soleh Dib, Dalibor Fronček (2014)

Czechoslovak Mathematical Journal

R. Frucht and J. Gallian (1988) proved that bipartite prisms of order 2 n have an α -labeling, thus they decompose the complete graph K 6 n x + 1 for any positive integer x . We use a technique called the ρ + -labeling introduced by S. I. El-Zanati, C. Vanden Eynden, and N. Punnim (2001) to show that also some other families of 3-regular bipartite graphs of order 2 n called generalized prisms decompose the complete graph K 6 n x + 1 for any positive integer x .

Decomposition of complete graphs into factors of diameter two and three

Damir Vukicević (2003)

Discussiones Mathematicae Graph Theory

We analyze a minimum number of vertices of a complete graph that can be decomposed into one factor of diameter 2 and k factors of diameter at most 3. We find exact values for k ≤ 4 and the asymptotic value of the ratio of this number and k when k tends to infinity. We also find the asymptotic value of the ratio of the number of vertices of the smallest complete graph that can be decomposed into p factors of diameter 2 and k factors of diameter 3 and number k when p is fixed.

Decomposition of Complete Multigraphs Into Stars and Cycles

Fairouz Beggas, Mohammed Haddad, Hamamache Kheddouci (2015)

Discussiones Mathematicae Graph Theory

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.

Decomposition of multigraphs

Mekkia Kouider, Maryvonne Mahéo, Krzysztof Bryś, Zbigniew Lonc (1998)

Discussiones Mathematicae Graph Theory

In this note, we consider the problem of existence of an edge-decomposition of a multigraph into isomorphic copies of 2-edge paths K 1 , 2 . We find necessary and sufficient conditions for such a decomposition of a multigraph H to exist when (i) either H does not have incident multiple edges or (ii) multiplicities of the edges in H are not greater than two. In particular, we answer a problem stated by Z. Skupień.

Decomposition tree and indecomposable coverings

Andrew Breiner, Jitender Deogun, Pierre Ille (2011)

Discussiones Mathematicae Graph Theory

Let G = (V,A) be a directed graph. With any subset X of V is associated the directed subgraph G[X] = (X,A ∩ (X×X)) of G induced by X. A subset X of V is an interval of G provided that for a,b ∈ X and x ∈ V∖X, (a,x) ∈ A if and only if (b,x) ∈ A, and similarly for (x,a) and (x,b). For example ∅, V, and {x}, where x ∈ V, are intervals of G which are the trivial intervals. A directed graph is indecomposable if all its intervals are trivial. Given an integer k > 0, a directed graph G = (V,A) is called...

Decompositions into two paths

Zdzisław Skupień (2005)

Discussiones Mathematicae Graph Theory

It is proved that a connected multigraph G which is the union of two edge-disjoint paths has another decomposition into two paths with the same set, U, of endvertices provided that the multigraph is neither a path nor cycle. Moreover, then the number of such decompositions is proved to be even unless the number is three, which occurs exactly if G is a tree homeomorphic with graph of either symbol + or ⊥. A multigraph on n vertices with exactly two traceable pairs is constructed for each n ≥ 3. The...

Decompositions of a complete multidigraph into almost arbitrary paths

Mariusz Meszka, Zdzisław Skupień (2012)

Discussiones Mathematicae Graph Theory

For n ≥ 4, the complete n-vertex multidigraph with arc multiplicity λ is proved to have a decomposition into directed paths of arbitrarily prescribed lengths ≤ n - 1 and different from n - 2, unless n = 5, λ = 1, and all lengths are to be n - 1 = 4. For λ = 1, a more general decomposition exists; namely, up to five paths of length n - 2 can also be prescribed.

Currently displaying 21 – 40 of 251