TITLE

DECOMPOSITIONS OF A COMPLETE MULTIDIGRAPH INTO ALMOST ARBITRARY PATHS

AUTHOR(S)
MESZKA, MARIUSZ; SKUPIÉ, ZDZISŁAW
PUB. DATE
May 2012
SOURCE
Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 2, p357
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
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.
ACCESSION #
86440299

 

Related Articles

  • Decomposition of Product Graphs into Paths and Cycles of Length Four. Jeevadoss, S.; Muthusamy, A. // Graphs & Combinatorics;Jan2016, Vol. 32 Issue 1, p199 

    Let $$P_{k}$$ and $$C_k$$ respectively denote a path and a cycle on $$k$$ vertices. In this paper we give necessary and sufficient conditions for the existence of $$\{P_{5}, C_4\}_{\{p, q\}}$$ -decomposition of tensor product and cartesian product of complete graphs. Further we extent such...

  • SYMMETRIC HAMILTON CYCLE DECOMPOSITIONS OF COMPLETE MULTIGRAPHS. CHITRA, V.; MUTHUSAMY, A. // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 4, p695 

    Let n ≥ 3 and λ ≥ 1 be integers. Let λK n denote the complete multi-graph with edge-multiplicity λ. In this paper, we show that there exists a symmetric Hamilton cycle decomposition of λK2m for all even λ ≥ 2 and m ≥ 2. Also we show that there exists a...

  • New Ore's Type Results on Hamiltonicity and Existence of Paths of Given Length in Graphs. Lichiardopol, Nicolas // Graphs & Combinatorics;Jan2013, Vol. 29 Issue 1, p99 

    The well-known Ore's theorem (see Ore in Am Math Mon 65:55, ), states that a graph G of order n such that d( x) + d( y) ≥ n for every pair { x, y} of non-adjacent vertices of G is Hamiltonian. In this paper, we considerably improve this theorem by proving that in a graph G of order n and...

  • SOME REMARKS ON THE STRUCTURE OF STRONG k-TRANSITIVE DIGRAPHS. HERNÁNDEZ-CRUZ, CÉSAR; MONTELLANO-BALLESTEROS, JUAN JOSÉ // Discussiones Mathematicae: Graph Theory;2014, Vol. 34 Issue 4, p651 

    A digraph D is k-transitive if the existence of a directed path (v0, v1, ..., vk), of length k implies that (v0, vk) ∈ & A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an...

  • Neighborhood Unions for the Existence of Disjoint Chorded Cycles in Graphs. Gao, Yunshu; Li, Guojun; Yan, Jin // Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1337 

    A chorded cycle is a cycle with at least one chord. We prove that if G is a simple graph with order n ≥ 4 k and $${|N_G(x)\cup N_G(y)|\geq 4k+1}$$ for each nonadjacent pair of vertices x and y, then G contains k vertex-disjoint chorded cycles. The degree condition is sharp in general.

  • The Existence of an Alternating Sign on a Spanning Tree of Graphs. KIM, DONGSEOK; KWON, YOUNG SOO; LEE, JAEUN // Kyungpook Mathematical Journal;Dec2012, Vol. 52 Issue 4, p513 

    For a spanning tree T of a connected graph .. and for a labelling Φ: E(T ) ! {+,-}, Φ is called an alternating sign on a spanning tree T of a graph ... if for any cotree edge e ∈ E(...)-E(T ), the unique path in T joining both end vertices of e has alternating signs. In the present...

  • Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments. Kühn, Daniela; Lapinskas, John; Osthus, Deryk; Patel, Viresh // Proceedings of the London Mathematical Society;Sep2014, Vol. 109 Issue 3, p733 

    A conjecture of Thomassen from 1982 states that, for every $k,$ there is an $f(k)$ so that every strongly $f(k)$-connected tournament contains $k$ edge-disjoint Hamilton cycles. A classical theorem of Camion, that every strongly connected tournament contains a Hamilton cycle, implies that...

  • Decomposing Various Graphs into Short Even-Length Cycles. Horsley, Daniel // Annals of Combinatorics;Sep2012, Vol. 16 Issue 3, p571 

    We prove that a complete bipartite graph can be decomposed into cycles of arbitrary specified lengths provided that the obvious necessary conditions are satisfied, the length of each cycle is at most the size of the smallest part, and the longest cycle is at most three times as long as the...

  • On Orthogonal Double Covers of Complete Bipartite Graphs by an Infinite Certain Graph-Path and Graph-Cycle. El-Shanawany, R. A. // British Journal of Mathematics & Computer Science;2014, Vol. 4 Issue 16, p2320 

    Let F be a certain graph, the graph F-Path denoted by â„™ d+1(F) path of length d with d + 1 vertices (i.e. Every edge of this path is one-to-one corresponding to an isomorphic to the graph F). In the same manner, we define the graph F-Cycle as â„‚d(F) cycle on d vertices. In this...

Share

Read the Article

Courtesy of VIRGINIA BEACH PUBLIC LIBRARY AND SYSTEM

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics