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