Uniform Coverings of 2-paths in the Complete Bipartite Directed Graph

Midori Kobayashi; Keiko Kotani; Nobuaki Mutoh; Gisaku Nakamura
February 2015
AIP Conference Proceedings;2015, Vol. 1648 Issue 1, p1
Conference Proceeding
Let G be a directed graph and H be a subgraph of G. A D(G, H, λ) design is a multiset D of subgraphs of G each isomorphic to H so that every directed 2-path in G lies in exactly λ subgraphs in D. In this talk, we show that there exists a D(Kn,n*, C2n, 1) design for every n ≥ 2, where Kn,n* is the complete bipartite directed graph and C2n is a directed Hamilton cycle in Kn,n*.


Related Articles

  • An Implicit Degree Condition for Pancyclicity of Graphs. Li, Hao; Cai, Junqing; Ning, Wantao // Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1459 

    Zhu, Li and Deng introduced in 1989 the definition of implicit degree of a vertex v in a graph G, denoted by id( v), by using the degrees of the vertices in its neighborhood and the second neighborhood. And they obtained sufficient conditions with implicit degrees for a graph to be hamiltonian....

  • On the Extremal Number of Edges in Hamiltonian Graphs. TUNG-YANG HO; CHENG-KUAN LIN; TAN, JIMMY J. M.; HSU, D. FRANK; LIH-HSING HSU // Journal of Information Science & Engineering;Sep2011, Vol. 27 Issue 5, p1659 

    Assume that n and δ are positive integers with 2 ≤ δ < n. Let h(n, δ) be the minimum number of edges required to guarantee an n-vertex graph with minimum degree δ(G) ≥ δ to be hamiltonian, i.e., any n-vertex graph G with δ(G) ≥ δ is hamiltonian if |E(G)|...

  • Hamilton Cycle Rich 2-Factorization of Complete Equipartite Graphs-II. Sangeetha, R.; Muthusamy, A. // Graphs & Combinatorics;Nov2012, Vol. 28 Issue 6, p877 

    For any given two 2-factors G and H of a complete p-partite graph K( m, p), with m vertices in each partite set, we prove the existence of a 2-factorization of K( m, p), in which one 2-factor is isomorphic to G, another 2-factor is isomorphic to H and the remaining 2-factors are hamilton cycles....

  • Characterization of Line Sidigraphs. Sampathkumar, E.; Subramanya, M. S.; Reddy, P. Siva Kota // Southeast Asian Bulletin of Mathematics;2011, Vol. 35 Issue 2, p297 

    A sigraph (sidigraph) is an ordered pair S = (G; σ) (S = (D; σ)), where G = (V, E) (D = (V, A) is a graph (digraph) called the underlying graph (underlying digraph) of S and σ : E → {+, -} (&sigma: A → {+, -}) is a function. The line sigraph (line sidigraph) of a sigraph...

  • HAMILTONIAN-COLORED POWERS OF STRONG DIGRAPHS. JOHN, GARRY; JONES, RYAN; KOLASINSKI, KYLE; ZHANG, PING // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 4, p705 

    For a strong oriented graph D of order n and diameter d and an integer k with 1≤ k ≤ d, the kth power Dk of D is that digraph having vertex set V(D) with the property that (u, v) is an arc of Dk if the directed distance dD(u, v) from u to v in D is at most k. For every strong digraph...

  • A NOTE ON BARNETTE'S CONJECTURE. HARANT, JOCHEN // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 1, p133 

    Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.

  • Large Sets of Hamilton Cycle and Path Decompositions of Complete Bipartite Graphs. Zhao, Hongtao; Kang, Qingde // Graphs & Combinatorics;Jan2013, Vol. 29 Issue 1, p145 

    In this paper, we determine the existence spectrums for large sets of Hamilton cycle and path (resp. directed Hamilton cycle and path) decompositions of λK (resp. $${\lambda K^{*}_{m,n}}$$).

  • Decomposition of Complete Bipartite Digraphs and Complete Digraphs into Directed Paths and Directed Cycles of Fixed Even Length. Shyu, Tay-Woei // Graphs & Combinatorics;Sep2015, Vol. 31 Issue 5, p1715 

    In this paper, we give some necessary and sufficient conditions for decomposing the complete bipartite digraphs $${\mathcal D}K_{m, n}$$ and complete digraphs $${\mathcal D}K_n$$ into directed paths $${\mathop {P}\limits ^{\rightarrow }}_{k+1}$$ and directed cycles $${\mathop {C}\limits...

  • 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...


Read the Article


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

Try another library?
Sign out of this library

Other Topics