TITLE

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

AUTHOR(S)
Midori Kobayashi; Keiko Kotani; Nobuaki Mutoh; Gisaku Nakamura
PUB. DATE
February 2015
SOURCE
AIP Conference Proceedings;2015, Vol. 1648 Issue 1, p1
SOURCE TYPE
Conference Proceeding
DOC. TYPE
Article
ABSTRACT
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*.
ACCESSION #
101586262

 

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

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

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

Try another library?
Sign out of this library

Other Topics